Codeforces - Reachable Strings

题目链接：Codeforces - Reachable Strings

---

我们可以发现每次0的移动都是不改变当前0的位置的左右1的奇偶性。

并且0是不可能改变相对位置的，所以我们对0的个数以及位置的左边1的奇偶性哈希即可。

代码当中((i&1)+1)*base) ，加上1是为了保证1的个数的哈希，位运算是对于不同左端点的奇偶位置哈希。

---

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
mt19937 rnd(time(0));
const int N=2e5+10;
const int base=rnd()%1333331+10,mod=rnd()%1000000019+10;
int n,cnt[N],h1[N],h2[N],q,pw[N]; char str[N];
inline int get(int l,int r){
	if(l&1) return (h1[r]-h1[l-1]*pw[cnt[r]-cnt[l-1]]%mod+mod)%mod;
	else return (h2[r]-h2[l-1]*pw[cnt[r]-cnt[l-1]]%mod+mod)%mod;
}
signed main(){
	scanf("%lld %s",&n,str+1); pw[0]=1;
	for(int i=1;i<=n;i++){
		pw[i]=pw[i-1]*base%mod;
		cnt[i]=cnt[i-1]+(str[i]=='0');
		if(str[i]=='0'){
			h1[i]=(h1[i-1]*base+((i&1)+1)*base)%mod;
			h2[i]=(h2[i-1]*base+((i%2==0)+1)*base)%mod;
		}else h1[i]=h1[i-1],h2[i]=h2[i-1];
	}
	scanf("%lld",&q);
	for(int i=1,x,y,l;i<=q;i++){
		scanf("%lld %lld %lld",&x,&y,&l);
		puts(get(x,x+l-1)==get(y,y+l-1)?"Yes":"No");
	}
	return 0;
}