題意 ：

• 給一字符串，求其有多少個子序列為𝚗𝚞𝚗𝚑𝚎𝚑𝚑𝚎𝚑加上若干個a（大于等于1），最后%998244353

思路 ：

• 由非連續子序列聯想到dp
• 預處理，cnta數組代表第i個后面出現的字母a的個數
• 對于第i個后面的所有的a每一個選與不選一共有$2^n$種情況，因為不能是空集，所以是$2^n?1$種情況
• $f[i,j]$表示前i個字符中以numhehheh中第j個結尾的個數
• 將它們相乘就是位置i的貢獻，再從前往后遍歷相加每一個點的貢獻就是總的方案數

#include <iostream> #include <cstring>using namespace std;typedef long long ll;const ll mod = 998244353; const int N = 1e5 + 10;ll cnta[N], f[N][10];ll qmi(ll a, ll b, ll p) {ll res = 1 % p;while (b){if (b & 1) res = res * a % p;a = a * (ll)a % p;b >>= 1;}return res; }int main() {int T;cin >> T;while (T -- ){string s;cin >> s;s = " " + s;// 多組輸入memset(f, 0, sizeof f);memset(cnta, 0, sizeof cnta);// 預處理，i及之后出現a的個數for (int i = s.size(); i; i -- ) cnta[i] = cnta[i + 1] + (s[i] == 'a');ll res = 0;for (int i = 1; i <= s.size(); i ++ ){f[i][1] = (f[i - 1][1] + (s[i] == 'n')) % mod;f[i][2] = (f[i - 1][2] + f[i - 1][1] * (s[i] == 'u')) % mod;f[i][3] = (f[i - 1][3] + f[i - 1][2] * (s[i] == 'n')) % mod;f[i][4] = (f[i - 1][4] + f[i - 1][3] * (s[i] == 'h')) % mod;f[i][5] = (f[i - 1][5] + f[i - 1][4] * (s[i] == 'e')) % mod;f[i][6] = (f[i - 1][6] + f[i - 1][5] * (s[i] == 'h')) % mod;f[i][7] = (f[i - 1][7] + f[i - 1][6] * (s[i] == 'h')) % mod;f[i][8] = (f[i - 1][8] + f[i - 1][7] * (s[i] == 'e')) % mod;// 輪到匹配串中的最后一個位置時，與總方案res直接相關，就不用加上f[i - 1][9]，因為循環在i - 1的時候，已經加到res中去了，現在不需要加，否則會重復f[i][9] = (f[i - 1][8] * (s[i] == 'h')) % mod;if (f[i][9]) res = (res + f[i][9] * (qmi(2, cnta[i + 1], mod) - 1) % mod) % mod;}cout << res << endl;}return 0; }

總結

以上是生活随笔為你收集整理的Nun Heh Heh Aaaaaaaaaaa 字符串，dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。