方針に戸惑ってちょっと遠回りしてしまった。
https://atcoder.jp/contests/abc138/tasks/abc138_f
問題
整数区間[L,R]が与えられる。
L≦x≦y≦Rとなる整数対(x,y)のうち、y mod x = y xor xとなる組み合わせを求めよ。
解法
まずy mod x = y xor xとなる条件を考える。
これはyとxのMSBが一致し、かつy-x=y xor xとなることである。
後者はさらにいうと、2進数の各桁において、yの値はxの値以上でなければならない。
yの値がx未満の場合、繰り下がりが発生してしまいy-x=y xor xでなくなってしまう。
さて、ここまで踏まえたうえで、x,yを2進数表記の上の桁から決定していこう。
あとは良くある2進数表記のDPである。LとR2つの値を考慮しながら決めていくのが特徴的。
- f(d,msb,l,r)を以下の時のx,yのd桁目より下の値の組み合わせ数とする。
- msb : d桁目より上ですでにMSBとなる桁があったかどうか
- l : d桁目より上を決めた段階で、xがLより真に大きいかまだLと一致しているかどうか
- r : d桁目より上を決めた段階で、yがRより真に小さいかまだRと一致しているかどうか
上記を踏まえ、x,yのd桁目として0,1を取りえるか見ていく。
x≦yは常時保つようにするので、xがRを超えたりyがLを下回ったりすることは気にしなくてよい。
ll L,R; ll mo=1000000007; ll dp[2][2][2][63]; ll hoge(int d,int S,int LT,int RT) { if(d==-1) return S==1; if(dp[S][LT][RT][d]>=0) return dp[S][LT][RT][d]; ll ret=0; int a,b; FOR(a,2) FOR(b,2) { if(a==0 && LT && (L&(1LL<<d))>0) continue; if(b==1 && RT && (R&(1LL<<d))==0) continue; if(a>b) continue; if(S==0 && a!=b) continue; int NLT=LT&&(((L>>d)&1)==a); int NRT=RT&&(((R>>d)&1)==b); int NS=S || (a==1 && b==1); ret+=hoge(d-1,NS,NLT,NRT); } return dp[S][LT][RT][d]=ret%mo; } void solve() { int i,j,k,l,r,x,y; string s; cin>>L>>R; MINUS(dp); cout<<hoge(61,0,1,1)<<endl; }
まとめ
よくある桁DPなんだけど、2つの値を同時に見ていくのは珍しいかも。