Codeforces #597 Div2 F. Daniel and Spring Cleaning

シンプルな問題。
http://codeforces.com/contest/1245/problem/F

問題

整数区間[L,R]が与えられる。
ここから2値a,bを取ったとき、a+b=a xor bとなるのは何通りか。

解法

a+b=a xor bとなる条件は、2進数表記でともに1になる桁がないことである。
a=bが成り立つのはa=b=0の時だけなので、以下a＜bの場合を求めよう。
bの最上位桁を定めると、aの同じ桁は0となる。
あとはL≦a＜b≦Rの範囲で桁DPをやればよい。
bの最上位桁の組み合わせ分O(logR)回程度で済む。

int T;
ll L,R;

ll memo[40][2][2];

ll dfs(int d,int Lmore,int Rless) {
	if(d==-1) return Lmore;
	if(memo[d][Lmore][Rless]>=0) return memo[d][Lmore][Rless];
	ll ret=0;
	
	if(Lmore==0 && (L&(1<<d))) {
		// L
		ret+=dfs(d-1,0,Rless || (R&(1<<d)));
	}
	else {
		// 0
		ret+=dfs(d-1,Lmore,Rless || (R&(1<<d)));
		// L
		ret+=dfs(d-1,Lmore || (L&(1<<d))==0,Rless || (R&(1<<d)));
		// R
		if(Rless||(R&(1<<d))) ret+=dfs(d-1,Lmore,Rless);
	}
	
	
	return memo[d][Lmore][Rless]=ret;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>L>>R;
		
		ll ret=0;
		if(L==0) {
			ret+=2*R+1;
			L++;
		}
		
		if(L<R) {
			L--;
			while(L<R) {
				int msb=0;
				while(1<<(msb+1)<=R) msb++;
				
				if(L+1>=1<<msb) break;
				MINUS(memo);
				ret+=2*dfs(msb-1,0,0);
				R=(1<<msb)-1;
			}
		}
		cout<<ret<<endl;
	}
	
}

まとめ

これもDiv2DかEでいい気がするんだよな。