Description：

给定 $n,a,b,p$ ，其中 $n,a$ 互质。定义一个长度为 $n$ 的01串 $c[0\dots n)$ ，其中 $c[i]=0$ 当且仅当 $(a\times i+b) \mod n < p$ 。给定一个长为 $m$ 的小 $01$ 串，求出小串在大串中出现了几次。

$1\leqslant n\leqslant 10^9,1\leqslant m\leqslant 10^6$

Solution：

$n,a$ 互质告诉我们 $(a\times i+b)\mod n$ 是两两不同的，也就是说我们可以通过 $f(i)=(a\times i+b)\mod n$ 来代表每个 $i$ ，要想从 $p$ 开始 $m$ 和原串能匹配， $0$ 的位置要满足 $0\leqslant (f(p)+a\times p')\%n<p$ ，其他位置满足 $p\leqslant (f(p)+a\times p')\% n<n$ ，移个项会发现是一个关于 $f(p)$ 的模意义下的不等式，注意有些 $l>r$ 的情况要分裂成两部分，最后把所有区间做区间交即可，但区间交不是很好做，转化为补集的区间补再用 $n$ 减即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,a,b,p,m;

#define MAXM 1000010

int v[MAXM];

inline int getc()

{

	register char c = getchar();

	while(c != '0' && c != '1')c = getchar();

	return c - '0';

}

struct seg

{

	int l,r;

}s[MAXM * 3];

bool cmp_r(seg a,seg b){return a.l < b.l;}

int cnt = 0;

int main()

{

	scanf("%d%d%d%d%d",&n,&a,&b,&p,&m);

	for(int i = 1;i <= m;++i)v[i] = getc();

	for(int i = 1;i <= m;++i)

	{

		int l,r;

		if(v[i])

		{

			l = (0 - (1ll * a * (i - 1) % n) + n) % n;

			r = (p - (1ll * a * (i - 1) % n) + n - 1) % n;

		}

		else

		{

			l = (p - (1ll * a * (i - 1) % n) + n) % n;

			r = (n - (1ll * a * (i - 1) % n) + n - 1) % n;

		}

		if(l <= r)

		{

			++cnt;s[cnt].l = l;s[cnt].r = r;

		}

		else

		{

			++cnt;s[cnt].l = 0;s[cnt].r = r;

			++cnt;s[cnt].l = l;s[cnt].r = n - 1;

		}

	}

	for(int i = n - m + 1;i < n;++i)

	{

		++cnt;

		s[cnt].l = (1ll * a * i + b) % n;

		s[cnt].r = (1ll * a * i + b) % n;

	}

	sort(s + 1,s + 1 + cnt,cmp_r);

	int cur = -1,ans = 0;

	for(int i = 1;i <= cnt;++i)

	{

		if(s[i].l > cur)

		{

			ans += s[i].l - cur - 1;

		}

		cur = max(cur,s[i].r);

	}

	ans += n - 1 - cur;

	cout << ans << endl;

	return 0;

}