Forested’s diary

ABC050-D Xor Sum

公式解説と（多分）違ったのでメモ　あくまでメモなのでかなり適当です

考察

非負整数 $x$ の $2^ d$ の位の値を $x _ d$ で表します。

どのような非負整数の組 $(u, v)$ を数え上げれば良いのかを考えます。

まず、 $a+b=(a \ \mathrm{xor} \ b) + 2(a \ \mathrm{and} \ b)$ より $a \ \mathrm{xor} \ b \leq a + b$ なので $u \leq v \leq N$ です。

$2^ 0$ の位には他の位からの繰り上がりが無いので、 $u _ 0 = v _ 0$ が言えます。

さらに、任意の $i$ についてついて以下が言えます。

$(u _ i, v _ i) = (0, 0)$ のとき、 $(u _ {i+1}, v _ {i+1}) = (0, 0), (0, 1), (1, 0), (1, 1)$
$(u _ i, v _ i) = (0, 1)$ のとき、 $(u _ {i+1}, v _ {i+1}) = (0, 0), (0, 1), (1, 0), (1, 1)$
$(u _ i, v _ i) = (1, 0)$ のとき、 $(u _ {i+1}, v _ {i+1}) = (0, 1), (1, 0)$
$(u _ i, v _ i) = (1, 1)$ のとき、 $(u _ {i+1}, v _ {i+1}) = (0, 0),(1, 1)$

逆に、これらを満たしていれば $a \ \mathrm{xor} \ b = u, a + b = v$ となる非負整数の組 $(a, b)$ が存在します。ここのあたりの説明は省略します。（それぞれどのような $(a _ i, b _ i)$ が条件を満たすかを考えると示せます。おそらく。）

あとは桁 DP によって答えが計算できます。

Submission #22272214 - AtCoder Beginner Contest 050