生活随笔
收集整理的这篇文章主要介绍了
Nun Heh Heh Aaaaaaaaaaa 字符串，dp
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
题意 ：
- 给一字符串，求其有多少个子序列为𝚗𝚞𝚗𝚑𝚎𝚑𝚑𝚎𝚑加上若干个a（大于等于1），最后%998244353
思路 ：
- 由非连续子序列联想到dp
- 预处理，cnta数组代表第i个后面出现的字母a的个数
- 对于第i个后面的所有的a每一个选与不选一共有2n2^n2n种情况，因为不能是空集，所以是2n−12^n-12n−1种情况
- f[i,j]f[i, j]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
);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
;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的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
