CF 635 C - XOR Equation
問題
問題概要
2つの正の整数に関して、との和を、とのビットごとのXORをで表す。とが与えられる時、の組としてあり得る組合せの数を求めよ。
アイデア
まず、に関しての全探索はサイズ的に間に合わない。そこで桁DPで試みる。
小さい方の桁から順番に見ていく。その桁のがかによって、その桁のとのビットの組合せが決まってくる。
のときは、かがあり得る組み合わせになる。これはどちらも足し算を考えた時にはこの桁の部分はになる。つまり、この桁のがなら前の桁からの繰り上がりはなく、ならば繰り上がりがある必要がある事になることが分かる。
のときは、かがあり得る組み合わせになる。これはどちらも足し算を考えた時にはこの桁の部分はになる。つまり、この桁のがなら前の桁からの繰り上がりがあり、ならば繰り上がりがある必要がある事になることが分かる。
これをメモ化再帰によって実装することで時間内に計算することが出来る。
また、注意として、とが一致する時にの候補としてが挙げられてしまうので、この場合にはこの再帰によって求まった解からこの組合せぶんを除いておく必要がある。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(i=0;i<n;++i) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define mp make_pair #define pb push_back #define fi first #define sc second ll s,x; ll dp[42][2]; //下からdigit桁目に注目、繰り上がりの有無 ll rec(int digit, int carry){ if(dp[digit][carry]>=0) return dp[digit][carry]; ll ret=0; if(digit==41){ if(carry) return 0; else return 1; } if((x>>digit)&1){ if((s>>digit)&1){ if(!carry) ret+=2*rec(digit+1,0); } else{ if(carry) ret+=2*rec(digit+1,1); } } else{ if((s>>digit)&1){ if(carry) ret+=rec(digit+1,0)+rec(digit+1,1); } else{ if(!carry) ret+=rec(digit+1,0)+rec(digit+1,1); } } return dp[digit][carry]=ret; } int main(int argc, char const *argv[]) { cin >>s >>x; memset(dp,-1,sizeof(dp)); ll ans=rec(0,0); if(s==x){//(0,s)と(s,0)を除外 ans-=2; } std::cout << ans << std::endl; return 0; }