正題

題目鏈接:https://www.luogu.com.cn/problem/P5404

---

題目大意

給出一個字符串$S$，然后求有多少個長度為$m$的串$T$滿足。無限多個串$T$拼接起來后能找出一個長度和$S$相等的子串字典序比$S$小。

$1\le |S|,m\le 2000$

---

解題思路

首先有一個小于的很難找，所以我們找有多少一直大于等于的減去就好了。

然后其實如果有一個大于位置大于$S$串匹配就可以直接不管，所以其實我們主要考慮前面都相等的情況，（根據(jù)題解）考慮用$KMP$。

設(shè)我們現(xiàn)在匹配到$[1,k]$，然后有$[1,nx{t}_k]=[k?nx{t}_k+1,k]$，然后加了一個字符如果有跳的邊而且是轉(zhuǎn)移邊里面字符最大的，因為我們顯然需要匹配出一個最大的前綴不然不能保證有小于的時候能直接找到。

而且如果我們現(xiàn)在在$KMP$上走了$T^{\infty }$之后節(jié)點是$i$，那么$T^{\infty }T$也是會匹配回到節(jié)點$i$的，所以相當于我們要找一個節(jié)點$p$使得它匹配了$T$之后仍然是回到節(jié)點$p$。

暴力枚舉節(jié)點來$dp$肯定是會$T$，考慮優(yōu)化一下。

不難發(fā)現(xiàn)如果一個點走$m$步之后沒有回到過$0$號節(jié)點的話方案只有一種（因為每個點連接$0$以外的出邊最多只有一條）。

所以設(shè)$f_{i,j}$表示從$0$出發(fā)走$j$步到達$i$的方案數(shù)。

然后對于起點枚舉多少步后走到$0$再用$f$統(tǒng)計答案就好了。

時間復(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; }

總結(jié)

以上是生活随笔為你收集整理的P5404-[CTS2019]重复【KMP,dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。