题目链接：Nun Heh Heh Aaaaaaaaaaa - HDU 7131 - Virtual Judge (vjudge.net)
题目描述：
解题思路：
快速幂+动态规划+排列组合+思维
把主串s分成前缀数组和后缀数组两部分，后缀数组记录a的个数，前缀数组保存每个位置前出现nunhehheh的个数（dp），那么答案就是：假设某个nunhehheh后面有n个a，这一组的个数就是2^(n-1)-1,所有情况个数就是算出每种可能然后求和。
快速幂：
直接上代码
//快速幂
ll powerMod(ll a,ll b)
{ll ans=1;a=a%mod;while(b>0){if(b%2==1) ans=(ans*a)%mod;b=b/2;a=(a*a)%mod;}return ans;
}
动态规划：
首先是后缀数组（求每个位置之后的a有多少个），简单dp，不做说明。
void get_a(int len)
{for(int i = len-1;i>=0;i--){s[i] = s[i+1];if(s[i] == 'a') s[i] += 1;}
}然后是前缀数组，这里有两种算法，一种空间复杂度O(mn)，一种空间复杂度O(n),时间复杂度都是O(mn)。前缀数组这儿卡了好久，其实和LCS有点像，可以先去学LCS。
第一种，空间复杂度O(mn):
s串为用户输入，t串为nunhehheh。
二维动态规划，定义一个dp[10] [MAX_N], dp[j] [i]的意思是s的前i-1个字符中有多少个子串和t中的1~j-1字符串相同。
动态规划：如果s的前i-1个字符中有x个子串与t中的1~j-1字符串相同，那么s的前i个字符中一定有x个子串与t中的1~j-1字符串相同。如果s[i] == t[j-1],那么s的前i个字符中还会多出 s的前i-2个字符的子串与t中1~j-2子符串相同时个数的个数。（绕的要死，建议看公式）
换成公式就是：
dp[j][i] = dp[j][i-1]%mod;if(s[i] == t[j])dp[j][i] += dp[j-1][i-1]%mod;当找出完整字符串时，直接计算一次答案。
if(j == len_t){dp[j][i] = (dp[j-1][i-1]%mod)*(s[i] == t[j]);//如果是完整串，单次计算，只需要上一位的所有可能就行了if(dp[j][i]){//计算ans = ans%mod + dp[j][i]*(powerMod(2,a[i+1])-1)%mod;}}该模块代码：
void Dp(int len_s,int len_t)
{for(int i = 0;i<=len_s;i++) dp[0][i] = 1;//s的第i个字符之前（包括自己）与 t一个都不匹配的数量是1for(int i = 1;i<=len_s;i++){for(int j = 1;j<=len_t;j++){dp[j][i] = dp[j][i-1]%mod;if(s[i] == t[j])dp[j][i] += dp[j-1][i-1]%mod;//如果该位相同，会多出上一位匹配的总可能数。if(j == len_t){dp[j][i] = (dp[j-1][i-1]%mod)*(s[i] == t[j]);//如果是完整串，单次计算，只需要上一位的所有可能就行了if(dp[j][i]){//计算ans = ans%mod + dp[j][i]*(powerMod(2,a[i+1])-1)%mod;}}}}
}AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<string>
using namespace std;
typedef long long int ll;const int MAX_N = 1e5+10;
const ll mod = 998244353;
ll a[MAX_N];
ll dp[10][MAX_N];
ll ans = 0;
string s;
string t= "$nunhehheh";inline void init()
{ans = 0;memset(a,0,sizeof(a));memset(dp,0,sizeof(dp));
}void get_a(int len)
{for(int i = len;i>0;i--){a[i] = a[i+1];if(s[i] == 'a') a[i] += 1;}
}//快速幂
ll powerMod(ll a,ll b)
{ll ans=1;a=a%mod;while(b>0){if(b%2==1) ans=(ans*a)%mod;b=b/2;a=(a*a)%mod;}return ans;
}void Dp(int len_s,int len_t)
{for(int i = 0;i<=len_s;i++) dp[0][i] = 1;//s的第i个字符之前（包括自己）与 t一个都不匹配的数量是1for(int i = 1;i<=len_s;i++){for(int j = 1;j<=len_t;j++){dp[j][i] = dp[j][i-1]%mod;if(s[i] == t[j])dp[j][i] += dp[j-1][i-1]%mod;//如果该位相同，会多出上一位匹配的总可能数。if(j == len_t){dp[j][i] = (dp[j-1][i-1]%mod)*(s[i] == t[j]);//如果是完整串，单次计算，只需要上一位的所有可能就行了if(dp[j][i]){//计算ans = ans%mod + dp[j][i]*(powerMod(2,a[i+1])-1)%mod;}}}}
}int main()
{int T;cin>>T;while(T--){init();cin>>s;s = "$"+s;int len_s = s.length()-1;int len_t = t.length()-1;get_a(len_s);Dp(len_s,len_t);cout<<ans%mod<<endl;}return 0;
}第二种之后再写思路，先贴个AC代码（朋友写的）
空间复杂度:O(n)
AC代码：
#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
ll num[100050];
ll numa[100050];
const ll mod = 998244353;inline ll PowerMod(ll a, ll b, ll c){ll ans = 1;a = a % c;while(b>0){if(b % 2 == 1)ans = ((ans % c) * (a % c)) % c;b = b/2;a = (a * a) % c;}return ans;
}int main(void){string aim = "nunhehheh";int len = aim.length();int t;cin>>t;while(t--){ll ans = 0;string str;cin>>str;int l = str.length();memset(num, 0, sizeof(num));memset(numa, 0, sizeof(numa));for(int i = l-1;i >= 0;i--){if(str[i] == 'a') numa[i] = numa[i + 1] + 1;else numa[i] = numa[i + 1];}num[0] = 1;for(int i = 0;i < l;i++){for(int j = len;j>0;j--){if(str[i] == aim[j-1]){if(j == len) ans = (ans + (((PowerMod(2, numa[i], mod) - 1) % mod) * num[len-1]) % mod) % mod;else{num[j] = (num[j] + num[j-1]) % mod;}}}}cout<<ans % mod<<endl;}return 0;
}