[题解] P3589 [POI2015] KUR

· · 题解

Change log

\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 时，减去在其中的不合法值，此操作双指针扫描即可。

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

参考代码：

#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;
}