AtCoder Beginner Contest 129 E - Sum Equals Xor

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