ABC129 E - Sum Equals Xor (500)

概要

整数Lが与えられる。下記の条件を満たす非負整数の組(a, b)がいくつあるかを求めよ。(mod 10^9+7 して出力)

• a+b ≦ L
• a+b = a xor b

制約

1 ≦ L < 2^100001

方針

a + b = a xor b
⇔ a & b = 0
⇔ a, bの2進表記でどちらも1となる桁がない（繰り上がりがない）

下記のような桁DPを作ると見通しがよい。
dp[i][eq]：上からi桁目(1-indexed)まで確定した(a, b)の組数、eq = 1 ならa+b = L、eq = 0ならa+b < L

スタートはdp[0][1] = 1

eqの遷移を見てゆく。
・0 ⇒ 0 の遷移
(a, b)の上の桁がどのようであっても、次の桁は(a, b)= (0, 0), (1, 0), (0, 1)のどれかになる
すなわち dp[i+1][0] += dp[i][0] * 3

・1 ⇒ 0 の遷移
Lの桁が1でなくてはならず、かつ(a, b) = (0, 0)である
すなわち if(L[i] == '1') dp[i+1][0] += dp[i][1]

・1 ⇒ 1 の遷移
Lの桁が0の場合は(a, b) = (0, 0) である
Lの桁が1の場合は(a, b) = (1, 0) , (0, 1)である
すなわち
if(L[i] == '0') dp[i+1][1] += dp[i][1]
if(L[i] == '1') dp[i+1][1] += dp[i][1] * 2

解答

Submission #5862286 - AtCoder Beginner Contest 129

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
ll MOD = 1e9 + 7;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	string L;
	cin >> L;
 
	int n = L.size();
	vector<vector<ll>> dp(n+1, vector<ll>(2, 0));
	dp[0][1] = 1;
 
	for(int i = 0; i < n; i++){
		// 1 -> 1
		if(L[i] == '0'){
			dp[i+1][1] += dp[i][1];
			dp[i+1][1] %= MOD;
		}else{
			dp[i+1][1] += dp[i][1] * 2;
			dp[i+1][1] %= MOD;
		}
 
		// 1 -> 0
		if(L[i] == '1'){
			dp[i+1][0] += dp[i][1];
			dp[i+1][0] %= MOD;
		}
 
		// 0 -> 0
		dp[i+1][0] += dp[i][0] * 3;
		dp[i+1][0] %= MOD;
	}
 
	cout << (dp[n][0] + dp[n][1]) % MOD << endl;
}