8VC Venture Cup 2016 - Final Round A. XOR Equation

問題

codeforces.com

解法

dp で解きます。

a の 2^0 の位が決まれば, b の 2^0 の位も決まります。なぜなら, a^b = x より, x の 2^0 の位を見れば b のそれも決定するからです。このようにして a と b の 2^0 の位を決めた際, a+b は偶数になるか奇数になるかのいずれかです。s が偶数なのに a+b が奇数になる, といったようなものは除外しなければなりません。

このようなことを考えると, dp で行ける気がします。まず, 基本的には dp[i] = (a と b が i 桁目まで条件を満たすような場合の数) といった dp です。ですが, a と b の 2^i の位を足し算した時 2^(i+1) に繰り上がりがくる可能性があるので, 実際には dp[i][c] = (i 桁目まで条件を満たし, キャリーが c であるようなものの場合の数)とすれば良いです。

positive integer じゃないとダメ, という条件がついてますが, a^b = x, a+b = s を満たし, a か b が 0 になるようなものは, s=x の場合以外ありえないので, これは dp のところでは特に考慮せず, s=x になってたら最後に 2 引く, というのが良いと思います。

const int MAX = 50;
ll dp[MAX+1][2];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll s, x;
    cin >> s >> x;
    dp[0][0] = 1;
    for (int i = 0; i < MAX; i++) {
        int y = (x>>i)&1;
        int tar = (s>>i)&1;
        for (int c = 0; c < 2; c++) {
            for (int a = 0; a < 2; a++) {
                int b = a^y;
                int next = a+b+c;
                if (next%2 != tar) continue;
                dp[i+1][next/2] += dp[i][c];
            }
        }
    }
    cout << dp[MAX][0] - (s==x ? 2 : 0) << endl;
    return 0;
}