CSAcademy Round #12 : D. Bitwise And Queries

これ系は面倒なだけで好みではないな…。
https://csacademy.com/contest/round-12/#task/bitwise-and-queries

問題

以下のクエリQ個に答えよ。
各クエリは３整数a,b,xからなる。
a≦y≦bとなる整数yのうち、x and y == xとなるものの個数を答えよ。

解法

f(c,x) := 1≦y≦cとなる整数yのうち、x and y == xとなるものの個数
とすると、f(b,x)-f(a-1,x)が解となる。

あとは2進数に対し上の桁から桁DPするだけ。

int Q;
ll X,A,B;
map<pair<ll,ll>,ll> M[61];

ll dodo(int d,ll x,ll a) {
	if(d==-1) return 1;
	if(M[d].count({x,a})) return M[d][{x,a}];
	ll D=1LL<<d;
	ll ret;
	if(x&D) {
		if(a&D) ret = dodo(d-1,x^D,a^D);
		else ret = 0;
	}
	else {
		if(a&D) ret = dodo(d-1,x,a^D) + dodo(d-1,x,D-1);
		else ret = dodo(d-1,x,a);
	}
	
	return M[d][{x,a}]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>A>>B>>X;
		
		FOR(i,60) M[i].clear();
		cout<<dodo(60,X,B)-dodo(60,X,A-1)<<endl;
	}
}

まとめ

うーん。