A16853. ABBA Counting
编程题
省选/NOI-
知识点
题目描述
给定一个长度为 $n$（$n$ 为偶数）的字符串 $T$，该字符串仅包含 'a'、'b' 和 '?' 字符。
请计算有多少个字符串 $S$ 满足以下条件：
- $|S|=n$；
- 对所有 $1 \le i \le n$，$S_i$ 只能为 'a' 或 'b'；
- 对所有 $1 \le i \le n$ 且 $T_i$ 不为 '?' 的下标 $i$，都有 $S_i=T_i$；
- 存在两个（可能为空的）字符串 $A$ 和 $B$，使得 $S=A+B+B+A$，其中 $+$ 表示字符串拼接。
由于答案可能过大，只需输出对 $998\,244\,353$ 取模后的结果。
请计算有多少个字符串 $S$ 满足以下条件：
- $|S|=n$；
- 对所有 $1 \le i \le n$，$S_i$ 只能为 'a' 或 'b'；
- 对所有 $1 \le i \le n$ 且 $T_i$ 不为 '?' 的下标 $i$，都有 $S_i=T_i$；
- 存在两个（可能为空的）字符串 $A$ 和 $B$，使得 $S=A+B+B+A$，其中 $+$ 表示字符串拼接。
由于答案可能过大，只需输出对 $998\,244\,353$ 取模后的结果。
输入格式
每组测试数据包含多组测试用例。第一行是测试用例个数 $t$（$1 \le t \le 10^4$）。
每个测试用例的第一行为一个整数 $n$（$2 \le n \le 400\,000$，$n$ 为偶数）。
第二行为一个长度为 $n$ 的字符串 $T$，只包含 'a'、'b' 和 '?'。
保证所有测试用例中 $n$ 的总和不超过 $400\,000$。
每个测试用例的第一行为一个整数 $n$（$2 \le n \le 400\,000$，$n$ 为偶数）。
第二行为一个长度为 $n$ 的字符串 $T$，只包含 'a'、'b' 和 '?'。
保证所有测试用例中 $n$ 的总和不超过 $400\,000$。
输出格式
每个测试用例输出一行答案，对 $998\,244\,353$ 取模。
输入输出样例
输入 #1
6 2 a? 2 ?? 4 a??a 4 ab?? 12 ??a?b??a??ba 12 ?ab???b??a??
输出 #1
1 2 2 2 10 22
说明/提示
对于第五个测试用例，共有 $10$ 个满足条件的字符串，如下：
1. "aaaabaaaaaba"
2. "aaaabbaaabba"
3. "aaabbaaaabba"
4. "aaabbbaabbba"
5. "abaabbbaabba"
6. "ababbbbabbba"
7. "baaabaaababa"
8. "baaababaaaba"
9. "baaabbaabbba"
10. "baabbabaabba"
1. "aaaabaaaaaba"
2. "aaaabbaaabba"
3. "aaabbaaaabba"
4. "aaabbbaabbba"
5. "abaabbbaabba"
6. "ababbbbabbba"
7. "baaabaaababa"
8. "baaababaaaba"
9. "baaabbaabbba"
10. "baabbabaabba"