← 返回题目列表

AtCoder · abc242_e

H. 全称量词

中文机器翻译题面 查看原题

分数: 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.