Score : $500$ points

问题描述

对于 $T$ 个测试用例，解决以下问题。

给定一个整数 $N$ 和一个字符串 $S$，求满足以下所有条件的字符串 $X$ 的个数，结果对 $998244353$ 取模。

• $X$ 是一个长度为 $N$ 的由大写英文字母组成的字符串。
• $X$ 是回文串。
• 按字典序排列时，$X \le S$。
  • 即 $X=S$ 或者 $X$ 在字典序上小于 $S$。

以上为通义千问 qwen-max 翻译，仅供参考。

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$.

update @ 2024/3/10 10:25:36