分数: 500 点
问题陈述
解决以下问题 T 测试用例。
给定一个整数 N 和一个字符串 S,查找字符串的数量 X 满足以下所有条件,模 998244353.
- X 是一个长度为的字符串 N 由大写英文字母组成。
- X 是一个回文。
- X \le S 按字典顺序排列。
- 也就是说, X=S or X 按字典顺序小于 S.
约束
- 1 \le T \le 250000
- N 是介于 1 和 10^6 (含)。
- 在单个输入中,总和 N 测试用例最多为 10^6.
- S 是一个长度为的字符串 N 由大写英文字母组成。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
在这里, \mathrm{case}_i 代表 i- 第一个测试用例。
每个测试用例均采用以下格式:
N S
输出
打印 T 行。 的 i- 第行应包含以下问题的答案 i- 第一个测试用例作为整数。
样本输入 1
5 3 AXA 6 ABCZAZ 30 QWERTYUIOPASDFGHJKLZXCVBNMQWER 28 JVIISNEOXHSNEAAENSHXOENSIIVJ 31 KVOHEEMSOZZASHENDIGOJRTJVMVSDWW
示例输出 1
24 29 212370247 36523399 231364016
此输入包含五个测试用例。
测试用例#1:
的 24 满足条件的字符串是 AAA, ABA, ACA,..., AXA.
测试用例#2:
S 可能不是回文。
测试用例#3:
一定要找到计数模数 998244353.