观察题目,我们发现直接计算是困难的,先构造单个合法的 \(T\) 分析其性质。
为了构造出 \(T\),先考虑构造时 \(T\) 时什么时候会出现不合法的情况,此时 \(T\) 会有一段和 \(S\) 相同的前缀,且这段前缀后面跟着的字符比 \(S\) 所跟的小。
为了避免这种情况出现,我们需要在每次添加字符时进行检查,具体而言,我们需要保证当前字符串的任意一个为 \(S\) 前缀的后缀在 \(S\) 中的下一个字符小于等于当前的字符。
这个约束条件显然与 KMP 有点关联,我们边加字符边维护当前字符串的一个最长的为 \(S\) 前缀的后缀,相当于建出 \(S\) 的 KMP 自动机,维护当前所在节点,每次直接跳向上的转移边查找约束后即可合法构造。
接下来考虑 \(T\) 开始循环后在自动机上会怎样转移,考察在输入无穷次 \(T\) 后走到的一个节点,由于 KMP 自动机的节点主要代表当前字符串与 \(S\) 的一个前缀相同的最大后缀的长度,且输入的长度无穷大,因此如果我们再输入一次 \(T\),此串与 \(S\) 的一个前缀相同的最大后缀的长度不改变,即还会回到原本的节点,故此过程构成了一个环,直接硬 dp \(m\) 次找环的个数可以做到 \(O(n^2m)\)。
如何优化呢?考察我们 dp 找环时每次转移往待定 \(T\) 的末尾添加字符,先找到我能放置的最小的字符,即待定 \(T\) 与 \(S\) 的一个前缀相同的所有后缀中下一个字符最大的那个,如果更小就不合法,要么添加此字符要么再添加更大的。
如果添加此字符,则继续往下转移,否则因为 \(S\) 中没有对应的前缀,我们会回到根节点。
故此过程对于以每个节点为起点的环,不过根节点的环最多只有一个(沿唯一的路径一直走,因此我们可以暴力判断存不存在此环,并枚举走到根节点的最小时间,在此时间之前我们沿着既定路线走,之后跳到根节点再走回来,走回来的方案数可以 dp 预处理,设 \(f_{i,j}\) 表示到达第 \(i\) 个节点走了 \(j\) 步的方案数,转移是容易的。
两个部分综合起来时间复杂度 \(O(nm)\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 3005
#define mod 998244353
#define ll long long
using namespace std;
char s[N];
ll nex[N],maxpos[N],ch[N][27],f[N][N];
int main(){
ll m;cin>>m;cin>>(s+1);ll n=strlen(s+1);
ll sum=1;
for(ll i=1;i<=m;i++)sum=(sum*26)%mod;
for(ll i=2,j=0;i<=n;i++){
while(j && s[i]!=s[j+1])j=nex[j];
if(s[i]==s[j+1])j++;
nex[i]=j;
}
for(ll i=0;i<=n;i++){
for(ll j=1;j<=26;j++){
if(s[i+1]-'a'+1==j)ch[i][j]=i+1;
else ch[i][j]=ch[nex[i]][j];
if(ch[i][j])maxpos[i]=j;
}
}
f[0][0]=1;
for(ll j=0;j<=m;j++){
for(ll i=0;i<=n;i++){
for(ll k=maxpos[i];k<=26;k++)f[ch[i][k]][j+1]=(f[ch[i][k]][j+1]+f[i][j])%mod;
}
}
ll ans=0;
for(ll i=0;i<=n;i++){
ll now=i;
for(ll j=1;j<=m;j++){
ans=(ans*1ll+(26-maxpos[now])*1ll*f[i][m-j])%mod;
now=ch[now][maxpos[now]];
if(!now)break;
}
if(now==i)ans=(ans+1)%mod;
}
cout<<(((sum-ans)%mod)+mod)%mod;
}
标签:字符,前缀,后缀,题解,ll,P5404,CTS2019,include,节点
From: https://www.cnblogs.com/eastcloud/p/17800409.html