0w1

CFR 635 C. XOR Equation ( 桁DP )

DP Digit

Problem - B - Codeforces
pekempey.hatenablog.com
pekempeyさんの記事見てやっと通りました。ありがとうございます。これも桁DPが通用するとは思いませんでした、自分もまだまだだなぁ。大きい数のなんとかの方法数を数える時は桁DPをよく考えてみよう。以下にあるのは pekempeyさんの記事を元に整理したものです。
まずXORの計算が簡単になるように、入力をバイナリにしてからDPをします。
dp[ i ][ j ]: 今 i桁までが計算済みで前の桁による桁上がりが ある( j == 1 ) / ない( j == 0 ) の状態の時の方法数
2 ≤ s, x ≤ 1e12 により、iの最大値はおよそ 50で大丈夫です。はみ出した leading zeroは影響がないのでなんであろうと 50回ループでDPを更新します。特に注意が必要なのは、aと bはどちらも必ず正整数出あって欲しいと決められてるので、s == xの場合だけには s ^ 0 == x && s + 0 = sが無駄に方法数に含まれます。
pekempeyさんのコードとほぼ同じです m( _ _ )m。bitsetは慣れないけど悪くないみたい。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXS = 1e12 + 2;
const ll MAXX = 1e12 + 2;
#define rep( i, a ) for(int i = 0; i < (int)( a ); ++i)

ll s, x;
ll way[ 50 ][ 2 ]; // pow( 2, 50 ) > MAXS

void solve(){
    way[ 0 ][ 0 ] = 1LL;
    rep( i, 50 ) rep( carry, 2 ) rep( ai, 2 ){
        int bi = ( ( ( s >> i ) & 1LL ) + ai + carry ) & 1LL;
        int next_carry = ( ai + bi + carry ) / 2;
        if( ( ai ^ bi ) == ( ( x >> i ) & 1LL ) )
            way[ i + 1 ][ next_carry ] += way[ i ][ carry ];
        // printf("%d %d %d %d: %d\n", i, carry, ai, bi, way[ i ][ carry ]);
    }
    if( s == x ) way[ 49 ][ 0 ] -= 2LL;
    cout << way[ 49 ][ 0 ] << endl;
}

int main(){
    ios::sync_with_stdio( false );
    cin >> s >> x;
    solve();
    return 0;
}