Change log

• 2023.9.22 修改少量 LaTeX 的使用。

$\color{red}博客内食用效果更佳（点我）$

复杂度：$O(n\log n)$

完整思路

纯纯的思维好题。考虑对所求答案的转化。

设小串为 $t$，其出现的起始位置为 $q+1$（是众多出现位置的其中一个），即使得 $c_{q+i}=t_i(1\le i\le m)$，显然有对于 $q>n-m$ 是不合法的。

我们将题意转化为求合法 $q$ 的数量，考虑枚举每一个 $t_i$。

当 $t_i=0$ 时，有 $0\le\left(a(q+i)+b\right)\ \mathrm{mod}\ n<p$。
当 $t_i=1$ 时，有 $p\le\left(a(q+i)+b\right)\ \mathrm{mod}\ n<n$。

接下来以 $t_i=0$ 为例，有 $0\le\left(aq+ai+b\right)\ \mathrm{mod}\ n<p$，其中 $ai+b$ 可以看做常数，对于此不等式组可以解出 $aq$ 的范围，是连续的一或两个区间（因为 $\mathrm{mod}\ n$ 后求出的区间可看做环上一段区间，可能是 $[0,x],[y,n-1]$ 的形式）。

于是我们得到了 $m$ 个不等式限制 $aq$ 的范围（在 $\mathrm{mod}\ n$ 意义下），题目中给出了 $a\perp n$ 的条件，所以一个 $aq$ 也只对应一个 $q$。所以我们求所有满足不等式限制的 $aq$ 个数减去不合法 $q$ 的个数即可。

考虑到值域很大，所以把每个 $l,r$ 离散化，差分地对于每个不等式解集区间加，最后前缀和还原，值等于 $m$ 的位置就是满足不等式的 $aq$。至于不合法解，我们考虑预处理 $[n-m+1,n-1]$ 的不合法 $q$ 对应的 $aq$，在统计 $aq$ 时，减去在其中的不合法值，此操作双指针扫描即可。

代码实现需要注意的地方：

• 在差分过程中注意 $l>r$ 的情况，这就是上文所说的两个区间的解集。
• 求 $l,r$ 的时候进行减法可能出现负数，要加上 $n$ 后再对其取模。

参考代码：

#include<bits/stdc++.h>
#define LL long long
#define UN unsigned
using namespace std;
//--------------------//
const int N=1e6+5,N2=2e6+5;

int n,a,b,p,m,s[N];
char str[N];
int tcnt,sum[N2],de[N];
LL tp[N2];
LL l[N],r[N];
//--------------------//
int main()
{
    scanf("%d%d%d%d%d%s",&n,&a,&b,&p,&m,str+1);
    for(int i=1;i<=m;i++)
    {
        s[i]=str[i]-'0';
        if(s[i])//求 l,r
        {
            l[i]=((p-1LL*a*(i-1)%n-b)%n+n)%n;
            r[i]=((n-1LL*a*(i-1)%n-b)%n+n)%n;
        }
        else
        {
            l[i]=((0-1LL*a*(i-1)%n-b)%n+n)%n;
            r[i]=((p-1LL*a*(i-1)%n-b)%n+n)%n;
        }
        tp[++tcnt]=l[i],tp[++tcnt]=r[i];
    }
    tp[++tcnt]=0,tp[++tcnt]=n;
    sort(tp+1,tp+tcnt+1);
    tcnt=unique(tp+1,tp+tcnt+1)-tp-1;
    for(int i=1;i<=m;i++)
    {
        l[i]=lower_bound(tp+1,tp+tcnt+1,l[i])-tp;
        r[i]=lower_bound(tp+1,tp+tcnt+1,r[i])-tp;
        sum[l[i]]++,sum[r[i]]--,sum[1]+=(l[i]>r[i]);//离散后差分
    }
    int ans=0,cnt=0;
    for(int i=2;i<=tcnt;i++)
        sum[i]+=sum[i-1];
    for(int i=n-m+1;i<n;i++)
        de[++cnt]=1LL*a*i%n;//预处理不合法解
    sort(de+1,de+cnt+1);
    for(int now=0,las,i=1;i<tcnt;i++)
    {
        las=now;
        while(now+1<=cnt&&de[now+1]<tp[i+1])//双指针扫描在符合条件 aq 中的不合法区间
            now++;
        if(sum[i]==m)
            ans+=tp[i+1]-tp[i]-(now-las);
    }
    printf("%lld",ans);
    return 0;
}