Codeforces #822 : Div2 F. Zeros and Ones

3250ptなのになんか本番すんなり解いてるな…。
https://codeforces.com/contest/1734/problem/F

問題

以下の文字列Sを考える。
S="0"から始め、以下を無限大繰り返す。

• Sの後ろに、Sの01反転した文字列を連結する。

以下のクエリに答えよ。
正整数N,Mが与えられる。
S[0...(M-1)]と、S[N...(N+M-1)]が何文字異なるか。

解法

S[i]は、iのbitcountの偶奇で決まる。
とするとS[2*n+k] = k xor S[n]となる。

f(N,M)を解とすると、メモ化再帰でN,Mを半分ずつにしていくことができる。

int T;
ll N,M;

map<pair<ll,ll>,ll> memo;

ll hoge(ll N,ll M) {
	if(M<=0) return 0;
	if(memo.count({N,M})) return memo[{N,M}];
	
	if(M==1) {
		return __builtin_popcount(N)%2;
	}
	ll ret=0;
	if(N%2==0) {
		ret=hoge(N/2,M/2)+hoge(N/2,(M+1)/2);
	}
	else {
		ret=M-hoge(N/2+1,M/2)-hoge(N/2,(M+1)/2);
	}
	
	return memo[{N,M}]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		cout<<hoge(N,M)<<endl;
	}
}

まとめ

考察ができるとコードは短い。