A16853 | $ABBA Counting$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个长度为 $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$ 取模后的结果。

每组测试数据包含多组测试用例。第一行是测试用例个数 $t$（$1 \le t \le 10^4$）。 每个测试用例的第一行为一个整数 $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

C++ 编辑器

输入

输出