AtCoder ABC #138 : F - Coincidence

方針に戸惑ってちょっと遠回りしてしまった。
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つの値を同時に見ていくのは珍しいかも。