https://atcoder.jp/contests/abc129/tasks/abc129_e
前提知識
解説
https://atcoder.jp/contests/abc129/submissions/5869998
a + b = a xor b
これを読み替えると、a & b = 0となる。
つまり、
a + b ≦ L かつ a & b = 0を満たすa,bの組を数えればいい。
Lの制約を見ると、桁毎に決定していきそうな感じがする。
しかもmod10^9+7なので、桁DPかなとなる。
dp[dgt][isLess] := 上位dgt桁まで確定していて、
今後どうa,bを作ってもa+b<LとなるならisLess=trueであるときの組み合わせ
これを使って、計算していこう。
基本、(a,b) = (1,0), (0,1), (0,0)であればいい。
だが、isLessがfalseであり、Lのdgt桁目が0であるときは、a+bがLを超えてしまうので、
(a,b) = (1,0), (0,1)には遷移できない。
これを繰り返して、dp[N][0] + dp[N][1]が答え。
string L; int N; mint dp[101010][2]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> L; N = L.length(); dp[0][0] = 1; rep(dgt, 0, N) rep(isLess, 0, 2) { // (a,b) = (0,0) if (L[dgt] == '1') dp[dgt + 1][1] += dp[dgt][isLess]; else dp[dgt + 1][isLess] += dp[dgt][isLess]; // (a,b) = (1,0), (0,1) if (!(L[dgt] == '0' and !isLess)) dp[dgt + 1][isLess] += dp[dgt][isLess] * 2; } mint ans = dp[N][0] + dp[N][1]; cout << ans << endl; }