AtCoder Beginner Contest 129 E - Sum Equals Xor
問題ページ
愚直解
L以下の全a,bに対して、
a + b <= L
a xor b = a + b
になるか見ていって、条件にあうものを数え上げる。
計算量は O(N^2) で、最大でa,bそれぞれ 10^5 通りぐらいあるので、間に合わない
愚直解の良くない点として、例えば
L = 111100001111111、a = 11111~~, b = 00000~~
のような場合に、左から５文字目を調べた段階で、a xor b > L が決まり条件を満たさないことが確定するのに、6文字目以降も全パターン調べてしまう。
なので、左から徐々に幅を増やして（小さい問題から大きい問題へ）、条件を満たすものだけ拾っていく形に変更する。メモ化を利用した処理（DPなど）
また、xor は桁ごとに処理するので、桁DPが使えそう
xor には桁上がりがないので、 a, b で同じbitに1が立っている場合は、 a+b = a xor b が満たせない。
DP[i+1][j] : Lの左からi番目まで見たときに、条件を満たすa,bの組。j=1のとき、L未満である。
遷移
dp[i][1] -> dp[i+1][1] : a+b = a xor b となる組合わせならOK
dp[i][0] -> dp[i+1][1] : L[i] = 1 のときに、a xor b = 0 かつ a+b = a xor b になるようにとればよい
dp[i][1] -> dp[i+1][0] : L[i] = a xor b のi桁目、a xor b = 0 かつ a+b = a xor b になるようにとればよい
解答
