更差的阅读体验
这也太深刻了。
我们考虑一个 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\)。那么我们可以先求出总方案数，然后求出不合法的方案数。那么无非就是两种情况：
- \(S\) 在 \([1: i - |S|]\) 这一部分有出现。枚举第一次出现的位置就可以转移。
- \(S\) 在 \([1: i - |S|]\) 这一部分没有出现，但是存在一次和 \([i - |S| + 1: i]\) 这一段部分重合的匹配。那么需要满足重合部分的长度是 \(S\) 的一个 \(\operatorname{border}\)。
\[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;
}