裏紙

ほぼ競プロ、たまに日記

CF 635 C - XOR Equation

問題

Problem - C - Codeforces

問題概要

2つの正の整数a,bに関して、abの和をsabのビットごとのXORをxで表す。sxが与えられる時、(a,b)の組としてあり得る組合せの数を求めよ。

  •  2 \le s \le 10^{12}
  •  0 \le x \le 10^{12}

イデア

まず、aに関しての全探索はサイズ的に間に合わない。そこで桁DPで試みる。

小さい方の桁から順番に見ていく。その桁のx01によって、その桁のabのビットの組合せが決まってくる。

x=0のときは、(0,0)(1,1)があり得る組み合わせになる。これはどちらも足し算を考えた時にはこの桁の部分は0になる。つまり、この桁のs0なら前の桁からの繰り上がりはなく、1ならば繰り上がりがある必要がある事になることが分かる。

x=1のときは、(0,1)(1,0)があり得る組み合わせになる。これはどちらも足し算を考えた時にはこの桁の部分は1になる。つまり、この桁のs0なら前の桁からの繰り上がりがあり、1ならば繰り上がりがある必要がある事になることが分かる。

これをメモ化再帰によって実装することで時間内に計算することが出来る。

また、注意として、sxが一致する時に(a,b)の候補として(0,s)と(s,0)が挙げられてしまうので、この場合にはこの再帰によって求まった解からこの組合せぶんを除いておく必要がある。

実装(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;
}