ARC066-D:Xor Sum
ある意味有名な(?)問題。解説と少し違ったので思うので書いてみる。
問題
考察
とりあえず、xorと和の関係を表す式であるところのを書いてみる。この式は、2つの自然数の足し算というのは、桁ごとの和(xor)と繰上がりに分解できるということを言っている。この式からがわかり、つまり問題文でいうところのがわかる。つまり、ということだけ考えれば、以下ということは自動的に満たされる。
を固定したときに、条件を満たすの数を数えたい。当然をすべて試すわけにはいかないので、うまい方法を考える。(*)式を見ると、との値を決めれば、の値も決まることがわかる。そこで、の値を決めたときに、としてあり得るものを数えることを考えてみる。これはの2進数表記の各桁が、0か1かを決めながら数えられそうである。そこで、の上位の桁から決めていく桁dpを考えることにする。ところが、上から決めるにあたって、の各桁の値を決めていくだけでは正しく数えることができない。それは、足し算に繰り上がりがあるからである。そこで、今の桁は下の桁からの繰上あがりを考慮するか?という情報を持つことにする。dp定義をまとめれば
- : の値を上から桁目まで決めたときのの通り数。ここで、はが確定しているかどうかのフラグ、は桁目からの繰り上がりを考慮しているかどうかのフラグ。
dpの遷移は難しくない(実装参照)。例えばの上から桁目をにするときを考える。を1にしたい場合、上から桁目に繰り上がりが生じるので、からの遷移が行われることになる。を0にしたい場合、上から桁目への繰り上がりを考慮するかどうかで、遷移を場合分けすることになる。答えはが2進数表記で桁であったとして、となる。
実装
この解法は思いつきやすいと思う。