102424: [AtCoder]ABC242 E - (∀x∀)
Description
Score : $500$ points
Problem Statement
Solve the following problem for $T$ test cases.
Given an integer $N$ and a string $S$, find the number of strings $X$ that satisfy all of the conditions below, modulo $998244353$.
- $X$ is a string of length $N$ consisting of uppercase English letters.
- $X$ is a palindrome.
- $X \le S$ in lexicographical order.
- That is, $X=S$ or $X$ is lexicographically smaller than $S$.
Constraints
- $1 \le T \le 250000$
- $N$ is an integer between $1$ and $10^6$ (inclusive).
- In a single input, the sum of $N$ over the test cases is at most $10^6$.
- $S$ is a string of length $N$ consisting of uppercase English letters.
Input
Input is given from Standard Input in the following format:
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Here, $\mathrm{case}_i$ represents the $i$-th test case.
Each test case is in the following format:
$N$ $S$
Output
Print $T$ lines. The $i$-th line should contain the answer for the $i$-th test case as an integer.
Sample Input 1
5 3 AXA 6 ABCZAZ 30 QWERTYUIOPASDFGHJKLZXCVBNMQWER 28 JVIISNEOXHSNEAAENSHXOENSIIVJ 31 KVOHEEMSOZZASHENDIGOJRTJVMVSDWW
Sample Output 1
24 29 212370247 36523399 231364016
This input contains five test cases.
Test case #1:
The $24$ strings satisfying the conditions are AAA$,$ ABA$,$ ACA$,...,$ AXA.
Test case #2:
$S$ may not be a palindrome.
Test case #3:
Be sure to find the count modulo $998244353$.
Input
题意翻译
给定正整数 $N$ 和长度为 $N$ 的字符串 $S$，你的任务是计算有多少个长度为 $N$ 的回文字符串 $X$，使得 $X \leq S$。计算结果对 $998244353$ 取模。$S$ 和 $T$ 均只包含大写英文字母。 总共有 $T$ 组数据。$T \leq 250000$, $N \leq 10^6$，所有 $S$ 的字母总数不超过 $10^6$。Output
问题描述
为$T$个测试用例解决以下问题。
给定一个整数$N$和一个字符串$S$，找出满足以下所有条件的字符串$X$的数量，模$998244353$。
- $X$是一个由大写英文字母组成的长度为$N$的字符串。
- $X$是回文串。
- $X \le S$按字典序排列。
- 也就是说，$X=S$或$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$的计数。