题目：Nun Heh Heh Aaaaaaaaaaa

题意：给出一个串s，求出s的子序列中满足前缀为"nunhehheh"，后缀为若干个（至少一个）'a'（不能包含其他的字符）组成的串的个数，该串仅仅由前缀和后缀组成。例如："nunhehheha"，"nunhehhehaaaa"满足条件，而"nunhehhehba"，"nunhehheh"则不满足条件。

思路：假设t = "nunhehheh"，s和t的长度为n和m，首先预处理（i ~ n）a的个数（后缀和），接着利用子序列匹配的dp进行匹配，最后遍历一遍s，当出现'h'时候可能前缀的个数进行更新，则通过前缀个数 * a的贡献(\(2^x\)（a的个数） - 1)即可。

解析：

• \(f_{i, j}\)表示s的前i个字符的子序列中与t的前j个字符相同的个数，dp转移方程如下：
  • \(f_{i,0} = 1\);
  • 若\(s_i == t_j\), \(f_{i, j} = f_{i-1, j-1} + f_{i - 1, j}\)（\(s_i\)与\(t_j\)进行匹配，也可以不选择其进行匹配）;
  • 若\(s_i \neq t_j\), \(f_{i, j} = f_{i-1, j}\)（\(s_i与t_j\)无法进行匹配）。
• s子序列中更新一次"nunhehheh"的个数则可以计算一次其之后所有a的贡献，即\(C_x^1 + C_x^2 + .. + C_x^x = 2^x - 1\)。
• 因为最后结果需要取模，所以\(f_{i, j}\)的值不一定是递增的，可能取模后比之前的值小，那么\(f_{i,j}\)在与上一次计算前缀个数发生变化的值\(f_{x, y}\)相减时可能出现负值，所以这里可以利用取模的同余性质：$x % mod = (x % mod + mod) % mod $，这样就能保证不出现负值。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 15;
const ll mod = 998244353;
int T;
ll f[N][M]; //s到第i位, t到第j位, s的子序列与t相同的个数
ll num[N]; //从n->i a的个数

ll qpow(ll n) //2^n
{
    ll ans = 1, a = (ll)2;
    while(n)
    {
        if(n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans % mod;
}

int main()
{
    cin >> T;
    while(T --)
    {
        string s, t = "nunhehheh";
        memset(f, 0, sizeof f);
        memset(num, 0, sizeof num);
        cin >> s;
        int n = s.length(), m = t.length();
        s = " " + s, t = " " + t;
        for(int i = n; i >= 1; i--)
        {
            if(s[i] == 'a') num[i] = num[i + 1] + 1;
            else num[i] = num[i + 1];
        }
        for(int i = 0; i <= n; i++) f[i][0] = 1;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                if(j > i) continue;
                if(s[i] == t[j])
                    f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;
                else f[i][j] = f[i - 1][j] % mod;
            }
        }
        ll res = 0;
        ll lastVal = 0; //上一次s序列中的子序列为t的个数
        for(int i = 1; i < n; i++)
        {
            if(s[i] == 'h')
            {
                res = ( (res % mod) + ( (f[i][m] - lastVal + mod) % mod * (qpow( num[i + 1]) - 1) % mod ) % mod ) % mod;
                lastVal = f[i][m];
            }
        }
        cout << res % mod << endl;
    }
    return 0;
}