読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

AtCoder Regular Contest 066: D - Xor Sum

よくわからないまま通してしまったのでメモ。


問題文:
D: Xor Sum - AtCoder Regular Contest 066 | AtCoder

pekempeyさんのブログを参考にしました(というかコードはほぼ同じ。
AtCoder Regular Contest 066: D - Xor Sum - pekempeyのブログ


以下ネタバレ注意。


遷移がイメージできなかったのでいくつかの例を挙げてみる。
b=(n>>i)&1とし、dp[i+1][nj]+=dp[i][j]と遷移することにする。

【b=0,j=0,x=0,y=0のとき】

j+x+y-b=0なのでぴったりで
nj=0

【b=1,j=0,x=0,y=0のとき】

j+x+y-b=-1なので余って
nj=0
余ってしまっても上位ビットの方が影響が強いのでN-a-b>=0とは関係なく、問題ない。
 \sum_{k=0}^{i-1} N[k]*2^k < N[i]*2^i

【b=0,j=2,x=1,y=1のとき】

j+x+y-b=4なので4足りない。
桁が繰り上がると倍になるので
nj=2

【b=1,j=2,x=1,y=1のとき】

j+x+y-b=3なので3足りない。
桁が繰り上がると倍になるので
nj=2


こう見てくるとceil((j+x+y-b)/2)で求められることがわかる。(+方向への切り上げ
ceil((j+x+y-b)/2)=floor((j+x+y-b+1)/2)と変形すると実装しやすい。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,mod=1000000007LL;
  cin>>n;
  ll dp[64][4]={};
  dp[0][0]=1LL;
  for(int i=0;i<61;i++){
    for(int j=0;j<3;j++){
      for(int x=0;x<2;x++){
	for(int y=x;y<2;y++){
	  ll b=(n>>i)&1;
	  dp[i+1][(x+y+j-b+1)/2]=
	    (dp[i+1][(x+y+j-b+1)/2]+dp[i][j])%mod;
	}
      }
    }
  }
  cout << dp[61][0] << endl;
  return 0;
}

なんとなくわかったような?