BZOJ 4377 Kurs szybkiego czytania

发表于 | 更新于

Link

一看到这个式子，可以找循环节啊！ 再一看互质……2333

Solution

一个等差数列膜掉一个数字之后再和另一个数字比较 假设小串出现在了大串的位置p∣p∈[1,n]p|p\in[1,n]，那么有 ...... 每个条件都可以转化为一个不等式，发现每个不等式可以看成对a(p−1)a(p-1)的限制，也就是对在大串中匹配上的第一个位置的数值的限制。 因为n,an,a互质，所以 与每个位置pp是一一对应的。 那就要解得到的这一堆不等式，找到满足要求的值的个数。 每个不等式形如 可能在膜意义下移项之后l>rl>r，那也无所谓，只需要添加两个不等式即可。因为 的值可以看成一个环，每个不等式限制了必须取环的一段。显然，l>rl>r添加两个不等式是符合意义的。 发现区间交集并不好求，那就转化一下，求不合法位置的并集，用总个数减去即可。

Tips

区间操作不好做，考虑补集转化 膜的不等关系可以类比在环上区间的限制

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include "lucida"
using std::sort;
const int MAXN=1e9+11,MAXM=1e6+11;
struct Limit {
	int l,r;
	Limit(){}
	Limit(int p):l(p),r(p){}
	Limit(int l,int r):l(l),r(r){}
	bool operator <(const Limit &a)const {
		return l<a.l || (l==a.l && r<a.r);
	}
}lim[(MAXM<<1)+MAXM];int limc;
int Union() {
	sort(lim+1,lim+1+limc);
	int l=lim[1].l,r=lim[1].r,res=0;
	for(int i=2;i<=limc;++i) {
		if(lim[i].l>r) {
			res+=r-l+1;
			l=lim[i].l;
			r=lim[i].r;
		} else
			chkmx(r,lim[i].r);
	}
	res+=r-l+1;
	return res;
}
int main() {
//	freopen("input","r",stdin);
	int n,a,b,p,m;
	is>>n>>a>>b>>p>>m;
	for(int i=1;i<=m;++i) {
		char digit;is>>digit;
		int64 l,r,d=(int64)a*(i-1)%n;
		if(digit=='1') {
			l=-d;
			r=p-1-d;
		} else {
			l=p-d;
			r=n-1-d;
		}
		((l%=n)+=n)%=n;((r%=n)+=n)%=n;
		if(l<=r) 
			new(&lim[++limc]) Limit(l,r);
		else {
			new(&lim[++limc]) Limit(l,n-1);
			new(&lim[++limc]) Limit(0,r);
		}
	}
	for(int i=n-m+1;i<n;++i)
		new(&lim[++limc]) Limit(((int64)a*i%n+b)%n);
	int Ans=n-Union();
	os<<Ans<<'\n';
	return 0;
}