Connie 题解(dp+kmp)

题目链接

题目思路

设(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
",ans);
    return 0;
}