AtCoder Regular Contest 066: D - Xor Sum

http://arc066.contest.atcoder.jp/tasks/arc066_b

a+b=u, a⊕b=v となる (a,b) が複数あると扱いづらいので a∧b=a, a∨b=b とする。こうすると (a,b) と (u,v) が一対一に対応する。

a⊕b ≤ a+b なので N-a-b≥0となる (a,b) が何通りあるかが求まればいい。下の桁から a と b の数字を決めていくと、次の桁の繰り下がりが決まるので、繰り下がりだけ覚えて DP できる。