Nun Heh Heh Aaaaaaaaaaa（dp+数学规律）

传送门

题目描述

输入描述

输出描述

输入样例

2
nunhehhehahaahahahahahahaahaahahahahha
nunhehhehhehhahaahahahaahaahahaaaahaa

输出样例

114514
1919810

题目大意： 给定一个字符串，可删去其中任意字符（也可不删），使其满足前缀为 “ nunhehheh ” ，后缀不少于一个 “ a ” ，问共有多少种删法。（删除不同位置的字符，但得到相同子串也算不同方法）。

好臭！好臭的题！

本题由非连续子串很快能联想到 dp ，入门题可见牛客的 iloveyou ：传送门

对于后缀 a 的个数，通过手模后不难发现以下规律：

a 的个数为 1 时，删除的方法为 1 种；

a 的个数为 2 时，删除的方法为 3 种；

a 的个数为 3 时，删除的方法为 7 种；

a 的个数为 4 时，删除的方法为 15 种；

……

即 a 的个数与方法的关系是：2 ^ a - 1；（ 求 2 的幂次方时注意使用快速幂优化复杂度 ）

因此对于每种前缀方法，仅需统计其后 a 的个数并代入公式即可，并累计到答案中。而本题的难点在于每个 h 对答案均有贡献值（即该 h 能够与先前的字符组成几个合法前缀 ），在 dp 时注意记录即可。

参考代码

#include 
typedef long long ll;
const int mod=998244353;
const int maxn=2e5+10;
using namespace std;

const int N=1e5+10;
string str1;
string str2="nunhehheh";
ll dp[15];
int f[N];

ll qmi(int a,int b,int p){
	ll ch=1%p;
	while(b){
		if(b&1)
			ch=ch*a%p;
			a=a*(ll)a%p;
			b>>=1;
	}
	return ch;
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;
	cin>>t; 
    while(t--)
    {	
    	map mp;
    	cin>>str1;
    	ll ans=0;
        memset(dp,0,sizeof(dp));
        int temp=dp[8]; 
        int k=0,m=0;
        for(ll i=0;i=0;j--){		
				dp[j]=(dp[j]+(str1[i]==str2[j])*(j==0?1:dp[j-1]))%mod;
			}
			if(temp!=dp[8]){
				f[k++]=i;
				mp[i]=dp[7];
				temp=dp[8];
			}
		}
        if(k==0){
        	cout<<"0"<