ABC 129
Table of Contents
https://atcoder.jp/contests/abc129
A. Airplane
https://atcoder.jp/contests/abc129/tasks/abc129_a
B. Balance
https://atcoder.jp/contests/abc129/tasks/abc129_b
C. Typical Stairs
https://atcoder.jp/contests/abc129/tasks/abc129_c
D. Lamp
https://atcoder.jp/contests/abc129/tasks/abc129_d
E. Sum Equals Xor
https://atcoder.jp/contests/abc129/tasks/abc129_e
桁 DP の問題ということをわかった状態で自力 AC.
$a+b = a XOR b$ の条件から $a$ と $b$ の各桁において同時に 1 にならないことがわかる.
$i$ 桁目が 0 のとき, $a_i, b_i$ は (0,0) のみ、$i$ 桁目が 1 のとき, $a_i, b_i$ は (0,1), (1,0) の 2 通りある。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string L;
cin >> L;
// dp[is_less]
vector<mint> dp(2);
dp[0] = 1;
int N = L.size();
rep(i, N) {
int t = L[i] - '0';
vector<mint> dpn(2);
rep(d, 2) rep(is_less, 2) {
if (!is_less && d > t) continue;
int is_less_n = is_less || d < t;
ll mul = d == 0 ? 1 : 2;
dpn[is_less_n] += dp[is_less] * mul;
}
swap(dp, dpn);
}
cout << (dp[0] + dp[1]).val() << endl;
}