Sum Equals Xor [AtCoder Beginner Contest 129 E]

https://atcoder.jp/contests/abc129/tasks/abc129_e

前提知識

• 桁DP

解説

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;
}