正題
題目連結:https://www.luogu.com.cn/problem/P5404
題目大意
給出一個字元串\(S\)，然後求有多少個長度為\(m\)的串\(T\)滿足。無限多個串\(T\)拼接起來後能找出一個長度和\(S\)相等的子串字典序比\(S\)小。
\(1\leq |S|,m\leq 2000\)
解題思路
首先有一個小于的很難找，是以我們找有多少一直大于等于的減去就好了。
然後其實如果有一個大于位置大于\(S\)串比對就可以直接不管，是以其實我們主要考慮前面都相等的情況，（根據題解）考慮用\(KMP\)。
設我們現在比對到\([1,k]\)，然後有\([1,nxt_k]=[k-nxt_k+1,k]\)，然後加了一個字元如果有跳的邊而且是轉移邊裡面字元最大的，因為我們顯然需要比對出一個最大的字首不然不能保證有小于的時候能直接找到。
而且如果我們現在在\(KMP\)上走了\(T^{\infty}\)之後節點是\(i\)，那麼\(T^{\infty}T\)也是會比對回到節點\(i\)的，是以相當于我們要找一個節點\(p\)使得它比對了\(T\)之後仍然是回到節點\(p\)。
暴力枚舉節點來\(dp\)肯定是會\(T\)，考慮優化一下。
不難發現如果一個點走\(m\)步之後沒有回到過\(0\)号節點的話方案隻有一種（因為每個點連接配接\(0\)以外的出邊最多隻有一條）。
是以設\(f_{i,j}\)表示從\(0\)出發走\(j\)步到達\(i\)的方案數。
然後對于起點枚舉多少步後走到\(0\)再用\(f\)統計答案就好了。
時間複雜度\(O(nm)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=2100,P=998244353;
ll n,m,ans,nxt[N],ch[N][26],f[N][N],mx[N];
char s[N];
signed main()
{
scanf("%lld%s",&m,s+1);
n=strlen(s+1);ans=1;
for(ll i=1;i<=m;i++)ans=ans*26ll%P;
for(ll i=2,j=0;i<=n;i++){
while(j&&s[i]!=s[j+1])j=nxt[j];
j+=(s[i]==s[j+1]);nxt[i]=j;
}
for(ll i=0;i<=n;i++)
for(ll c=0;c<26;c++){
if(s[i+1]==c+'a')ch[i][c]=i+1;
else ch[i][c]=ch[nxt[i]][c];
if(ch[i][c])mx[i]=c;
}
f[0][0]=1;
for(ll i=0;i<m;i++)
for(ll j=0;j<=n;j++)
for(ll c=mx[j];c<26;c++)
(f[ch[j][c]][i+1]+=f[j][i])%=P;
for(ll i=0;i<=n;i++){
ll x=i;
for(ll j=1;j<=m;j++){
(ans-=(25-mx[x])*f[i][m-j]%P)%=P;
x=ch[x][mx[x]];
if(!x)break;
}
if(i&&x==i)(ans+=P-1)%=P;
}
printf("%lld\n",(ans+P)%P);
return 0;
}