AtCoder Beginner Contest 129 ABC129 E - Sum Equals Xor
AtCoder Begginer Contest 129 E - Sum Equals Xor
解説
a + b = a xor b a + b = a xor b + 2 * (a & b) より a & b = 0 と読み替える
a + b <= L
以下で、a & b = 0
となるa
とb
の組み合わせの個数を答える問題に変わる。
桁DPをする。
a + b
がL
未満かどうかのFlagを持ちながら、桁を上から決めていき
1
にする場合は、その1
をa
とb
のどちらに割り当てるかで2通りできる
提出
//桁DP //上からi桁目まで見たときに以下flagの有無による個数 mint dp[100010][2]; int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); string L; cin >> L; int N = L.size(); dp[0][0] = 1; for(int i = 0; i < N; i++){ int d = L[i] - '0'; rep(j,2){ for(int k = 0; k <= ((j) ? 1: d); k++){ dp[i+1][j || k < d] += dp[i][j] * (k ? 2:1); } } } cout << (dp[N][0] + dp[N][1]).x << endl; }