Connie

NC222522. Connie

描述

Connie在一个人打电动。
游戏开始时Connie会给游戏机一个长度为m的字符串S，游戏机会随机生成一个长度为n的，由c,o,n,i,e组成的字符串T，假设S在T中作为子串总共出现了k次，那么这一轮游戏的得分就为 $2^k$ ,例如，当T="cococ",S="coc"，有K=2，得分为4。
Connie想知道她的期望得分是多少，答案对998244353取模。
可以证明，最终答案一定可以表示成q/p的有理数形式，即 $q*p^{-1}$ ，其中q,p为互质的整数，输出的期望得分（记为ans）需要保证 $0\leq ans<998244353$ ，且 $ans*p \equiv q\pmod{998244353}$ 。

输入描述

第一行，两个正整数，分别代表字符串T,S的长度。
第二行，一个长度为m的字符串，表示字符串S, 保证S只由c,o,n,i,e组成。

输出描述

总共一行，一个整数，表示Connie的期望得分在模998244353下的值。

示例1

输入:

3 2
cc

输出:

503115155

说明:

样例1的答案为136/125=503115155。

示例2

输入:

5 3
coc

输出:

345951564

说明:

样例2的答案为3201/3125=345951564。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 484K, 提交时间: 2022-09-03 15:17:08

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=110,mod=998244353;
ll qmi(ll a,ll k) {
	ll res=1;
	while(k) {
		if(k&1) res=res*a%mod;
		k>>=1;
		a=a*a%mod;
	}
	return res;
}
char s[N],ch[]={'c','o','n','i','e'};
int ne[N];
ll dp[N][N];

int main() {
//	ios::sync_with_stdio(false);

	int n,m;
	scanf("%d%d%s",&n,&m,s+1);
	
	for(int i=2,j=0;i<=m;i++){
		while(j&&s[i]!=s[j+1]) j=ne[j];
		if(s[i]==s[j+1]) j++;
		ne[i]=j;
	}
	dp[0][0]=1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int k=0;k<5;k++){
				int pos=j;if(pos==m) pos=ne[pos];
				while(pos&&ch[k]!=s[pos+1]) pos=ne[pos];
				if(ch[k]==s[pos+1]) pos++;
				dp[i+1][pos]=(dp[i+1][pos]+dp[i][j]*(pos==m?2:1))%mod;
			}
		}
	}
	ll res=0;
	for(int i=0;i<=m;i++) res=(res+dp[n][i])%mod;
	ll ans=qmi(5,n);
	ans=qmi(ans,mod-2);
	cout<<res*ans%mod;
}