(∀x∀)

题目描述

求解 $T$ 个测试用例的问题。 给定一个整数 $N$ 和一个字符串 $S$，求满足下列所有条件的字符串 $X$ 的数量，对 $998244353$ 取模。

$X$ 是长度为 $N$ 的由大写英文字母组成的字符串。 $X$ 是回文串。 $X \le S$ 在字典序上成立。 也就是说，$X=S$ 或者 $X$ 在字典序上严格小于 $S$。

输入格式

输入从标准输入按如下格式给出： $T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

这里，$\mathrm{case}_i$ 表示第 $i$ 个测试用例。 每个测试用例的格式如下： $N$ $S$

输出格式

输出 $T$ 行。 第 $i$ 行应包含第 $i$ 个测试用例的答案（整数）。

5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW

24
29
212370247
36523399
231364016

提示

$1 \le T \le 250000$ $N$ 是一个在 $1$ 到 $10^6$（含）之间的整数。 在单个输入中，所有测试用例的 $N$ 之和至多为 $10^6$。 $S$ 是一个长度为 $N$ 的由大写英文字母组成的字符串。该输入包含五个测试用例。 测试用例 #1：
满足条件的 $24$ 个字符串是 $AAA$$,$ $ABA$$,$ $ACA$$,...,$ $AXA$。 测试用例 #2：
$S$ 可能不是回文串。 测试用例 #3：
注意结果要对 $998244353$ 取模。

标签: AtCoder|abc242E

来源

AtCoder|abc242E