ABC129 E - Sum Equals Xor (500)
桁DPでの考え方はよく分っていない
和とxorの結果が等しくなるには、2進数で考えて繰り上がりがあると駄目
0以上
$ 2^n
未満のLで条件を満たすa,bの組は
$ 3^n
個
上からi桁目が0の場合は何もしない
上からi桁目が1の場合は
$ 3^{残りの桁数} \times 2^{i桁目までのまでの1の数}
を加える
上の計算で
$ a+b < L
の場合が求められたので、最後に
$ a+b = L
の場合を計算して加える
問題:
https://atcoder.jp/contests/abc129/tasks/abc129_e
提出:
https://atcoder.jp/contests/abc129/submissions/5847044
#AtCoder
#ABC
#ABC129
#E
#500pt
#O(L)