【题解】LOJ#6500. 「雅礼集训 2018 Day2」操作 / tiramisu【20201030 CSP 模拟赛】

题目链接

题目链接

题意

今有一 01 串。现 \(q\) 次独立地询问,对于一个子串:

  • 一次操作可以把其一个长为 \(k\) 的子串取反,问多少次操作可以将这个串清零(无法清零输出 -1)。

\(n\leq 2\times 10^6\),\(q\leq 5\times 10^5\)。

题解

先异或差分,把位置按照 \(\bmod k\) 的结果分类,每一类都会有很多个为 \(1\) 的位置,这些为 \(1\) 的位置必须两两配对消掉。

于是给每个为 \(1\) 的位置按 \(\bmod k\) 的结果分配一个随机的值,异或和为零就代表着所有 \(1\) 都配对了。所有为 \(1\) 的位置的贡献是一正一负的。注意边界上的值为 \(1\) 的情况。

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
const int N=2e6+10;
int Rand(){
	return rand()^(rand()<<15)^23333333;
}
int a[N],hsh[N],sd[N],pre[N],c[N];
int ll[N],rr[N];
int main(){
	int n,k,m;
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=n;i++)scanf("%1d",a+i);
	for(int i=0;i<k;i++)sd[i]=Rand();
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1]; hsh[i]=hsh[i-1];
		if(a[i]^a[i-1]){
			hsh[i]^=sd[i%k];
			pre[i]+=i-2*c[i%k];
			c[i%k]=i-c[i%k];
		}
		ll[i]=c[i%k];
		rr[i]=c[(i+1)%k];
	}
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		if(hsh[l]^hsh[r]^(a[l]*sd[l%k])^(a[r]*sd[(r+1)%k]))puts("-1");
		else printf("%d\n",(pre[r]-pre[l]+a[l]*(2*ll[l]-l)+a[r]*(r+1-2*rr[r]))/k);
	}
	return 0;
}

上一篇:类欧几里得算法


下一篇:【数论】中国剩余定理(CRT)