题目链接
题目思路
设\(dp[i][j]\)表示已经构造了\(T\)的前\(i\)位，用\(S\)去\(kmp\)匹配\(T\)，到第\(i\)位时，\(kmp\)匹配到\(S\)的第\(j\)位，枚举\(i+1\)位选了啥
然后用\(nxt\)数组往回跳，这个最差暴力往回跳的复杂度为\(O(m)\) 可以维护一个\(nx[i][j]\)表示第\(i\)个位置后面如果接\(j\)会
跳到哪里，这样维护\(j\)的复杂度为\(O(1)\)
但数据小暴力\(nxt\)复杂度可以过去
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e2+5,inf=0x3f3f3f3f,mod=998244353;
const double eps=1e-6;
int n,m;
int nxt[maxn];
ll dp[maxn][maxn];
char s[maxn],c[]={‘ ‘,‘c‘,‘o‘,‘n‘,‘i‘,‘e‘};
ll qpow(ll a,ll b){
ll ans=1,base=a;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod;
b=b>>1;
}
return ans;
}
void getnext(){
for(int i=2,j=0;i<=m;i++){
while(j&&s[i]!=s[j+1]){
j=nxt[j];
}
if(s[i]==s[j+1]) j++;
nxt[i]=j;
}
}
signed main(){
scanf("%d%d",&n,&m);
scanf("%s",s+1);
getnext();
dp[0][0]=1;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=1;k<=5;k++){
int pos=j;
while(pos&&(s[pos+1]!=c[k])) pos=nxt[pos];
if(c[k]==s[pos+1]) pos++;
dp[i+1][pos]=(dp[i+1][pos]+dp[i][j]*(pos==m?2:1))%mod;
}
}
}
ll ans=0;
for(int i=0;i<=m;i++){
ans+=dp[n][i];
}
ans=ans%mod*qpow(qpow(5,n),mod-2)%mod;
printf("%lld\n",ans);
return 0;
}