题目链接：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一个都不匹配的数量是1
for(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一个都不匹配的数量是1
for(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;
}