ABC129 E - Sum Equals Xor - あっとのTECH LOG

問題原文

問題要旨

非負整数からなる組 $(a, b)$ であって、以下の条件を満たすものの通り数を求めよ。

$a + b \leq L$
$a + b$ == $a XOR b$
$1 \leq L \leq 2^{100001}$

解法

ここから出てくる1111~とかは全部２進数です。

制約が桁dpをしろと言っている。。。
こういう場合には、「 $L$ 以下であることがまだ未確定にdpテーブル」と「 $L$ 以下であることがすでに確定しているdpテーブル」を考えるとうまくいく。
ところで、 $a, b$ のある桁のbitに注目した時には４通りの状態が取りうるが、与えられた条件や、繰り上がり等を考慮すると以下のように分類できる。

$L$ 以下であることが未確定 & $L$ の $i$ ビット目が１
→ $(1, 0), (0, 1)$ の２通り
$L$ 以下であることが未確定 & $L$ の $i$ ビット目が０
→ $(0, 0)$ の１通り
$L$ 以下であることが確定 & $L$ の $i$ ビット目が１
→ $(0, 0), (1, 0), (0, 1)$ の３通り
$L$ 以下であることが確定 & $L$ の $i$ ビット目が０
→ $(0, 0), (1, 0), (0, 1)$ の３通り

また、 $L$ の $i$ ビット目が１の場合には、そのビットを０に確定させることで、「 $L$ 以下であることがすでに確定しているdpテーブル」へ遷移できる。
イメージとしては、 $L = 11111$ の上で、 $110xx$ と確定させる感じかな。。。
$L = 11$ においては、 $(a, b) = (10, 00), (00, 10)$ みたいなパターンがこれにあたる。

実装

dp問は先に遷移とかをしっかり理解しておけば、楽にかける気がする。。。？
サンプルが弱いので、愚直を書いてチェックするようにするとデバッグが楽になります。

L = input()
MOD = 10 ** 9 + 7

# dp[i][flg] := 上からi番目の桁まで見た時に、L以下であることがflg（未確定/確定）であるような、条件を満たす組み合わせの通り数
dp = [[0] * 2 for i in range(len(L) + 1)]
dp[0][0] = 1
for i, l in enumerate(L, start=1):
    if l == '0':
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = (3 * dp[i - 1][1]) % MOD
    else:
        dp[i][0] = (2 * dp[i - 1][0]) % MOD
        dp[i][1] = (3 * dp[i - 1][1] + dp[i - 1][0]) % MOD

print(sum(dp[-1]) % MOD)

余談

桁dp使わなくても解けるらしい。。。むぅ drken1215.hatenablog.com

（さすがけんちょんさん）

感想

前はdpは不可能、桁dpなんでとんでもないという感じだったんですが、復習はすっとできて嬉しさ。

先に紙の上で遷移を整理する（dpテーブルを書くのもおすすめ）
いいサンプルを愚直を書いて自作する

とかが大事そうだなぁと思いました。