题解：P1393 Mivik 的标题

· · 题解

更好的阅读体验

这也太深刻了。

我们考虑一个 dp。我们假设 f_i 表示考虑前 i 个字符，[i - |S| + 1: i] 这一段存在一个 S 的匹配，并且前 i 个字符不存在别的位置有 S 匹配的方案数。

那么我们就相当于确定了 S 第一次出现的位置，后面可以乱填，所以

\operatorname{answer} \cdot m^n = \sum\limits_{i = |S|}^{n}m^{n-i} \cdot f_i

接下来考虑怎么求这个 f。那么我们可以先求出总方案数，然后求出不合法的方案数。那么无非就是两种情况：

f_{i} = \sum_{j = 0}^{i-|S|}f_j \cdot m^{i-|S|-j} + \sum_{j \in \operatorname{border}_i}f_{i-|S|+j}

直接做复杂度 O(n^2)。

首先很显然地，第一部分可以前缀和来求。但是第二部分不太好优化。

如果你知道 Border Theory 的一点点东西的话，你就知道一个串 S 的 \operatorname{border} 可以划分成 O(\log |S|) 个等差数列。这方面的内容可以去阅读这篇文章。

那么我们就会这个题目了。我们对每个等差数列分别统计答案，维护前缀和。具体地，假设公差为 d，我们维护模 d 意义下的前缀和，也就是 s_{d, i} = s_{d, i-d} + f_i。然后我们枚举这些等差数列，一个一个把前缀和取出来计算就可以了。

然后这道题就做完了。假设 n, |S| 同阶，复杂度 O(n \log n)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 200006
#define M 36
#define MOD 998244353
using namespace std;
int n,m,pw[N],len,tot,a[N],nxt[N];
int lb[M],rb[M],d[M],f[N],g[M][N];
int qpow(int x,int y=MOD-2)
{
    int ret=1;
    for(;y;y>>=1,x=x*x%MOD)if(y&1)ret=ret*x%MOD;
    return ret;
}
main()
{
    scanf("%lld%lld%lld",&n,&m,&len),pw[0]=1;
    for(int i=1;i<N;i++)pw[i]=pw[i-1]*m%MOD;
    for(int i=1;i<=len;i++)scanf("%lld",&a[i]);
    for(int i=2,j=0;i<=len;nxt[i]=j,i++)
    {
        for(;a[j+1]!=a[i]&&j;j=nxt[j]);
        if(a[j+1]==a[i])j++;
    }
    for(int i=nxt[len];i;rb[tot]=len-i,i=nxt[i])
    {
        d[++tot]=i-nxt[i],lb[tot]=len-i;
        for(;nxt[i]&&i-nxt[i]==d[tot];i=nxt[i]);
    }
    f[len]=1;
    for(int i=1;i<=tot;i++)g[i][len]=1;
    for(int i=len+1,sum=0;i<=n;i++)
    {
        sum=(sum*m+f[i-len])%MOD,f[i]=(pw[i-len]-sum+MOD)%MOD;
        for(int j=1;j<=tot;j++)
            f[i]=(f[i]-g[j][i-lb[j]]+g[j][max(0ll,i-rb[j]-d[j])]+MOD)%MOD;
        for(int j=1;j<=tot;j++)
            g[j][i]=(g[j][i-d[j]]+f[i])%MOD;
    }
    int ans=0;
    for(int i=len;i<=n;i++)
        ans+=f[i]*pw[n-i]%MOD,ans%=MOD;
    printf("%lld\n",ans*qpow(pw[n])%MOD);
    return 0;
}