AtCoder Beginner Contest 242

E - (∀x∀)

https://atcoder.jp/contests/abc242/tasks/abc242_e

Time Limit: 2 sec / Memory Limit: 1024 MB

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

我的笔记

  • 若回文串 $X$ 前半截的字典序就已经比 $S$ 小了，那么可以直接得出结论 $X<S$。

    • 如：$X=ABCBA$ 和 $S=AZZZZ$，回文串前半截 $ABC$ 已经比 $AZZ$ 小了，因此 $X<S$。

  • 若回文串 $X$ 前半截等于 $S$ 的前半截，那么需要比对后半截才能知道字典序的情况。

    • 如：$X=ABCBA$ 和 $S=ABCAA$，不比对这俩的后半截是没法知道字典序情况的。

  • 若回文串 $X$ 前半截的字典序就已经比 $S$ 大了，那么可以直接得出结论 $X>S$，即不符合该题要求。

    • 如：$X=ABCBA$ 和 $S=AAAAA$，回文串前半截 $ABC$ 已经比 $AAA$ 大了，因此 $X>S$。

依靠上面第一条性质，可以先求出 $X$ 的前半截（就干脆写成 $X/2$ 吧）就已经比 $S/2$ 小的情况。

例如字符串 $S=BCADBABDDC$，先只考虑前半截 $S/2=BCADB$。我们要计算有多少种 $X/2$ 比 $S/2$ 小的情况：

$BCAD?$：第五位可选 $A$，共 $1\times26^0$ 种。
$BCA??$：第四位可选 $A,B,C$，第五位可选 $A\sim Z$，共 $3\times26^1$ 种。
$BC???$：第三位没法选，第四位可选 $A\sim Z$，第五位可选 $A\sim Z$，共 $0\times26^2$ 种
$B????$：第二位可选 $A,B$，第三位可选 $A\sim Z$，第四位可选 $A\sim Z$，第五位可选 $A\sim Z$，共 $2\times26^3$ 种。
$?????$：第一位可选 $A$，第二位可选 $A\sim Z$，第三位可选 $A\sim Z$，第四位可选 $A\sim Z$，第五位可选 $A\sim Z$，共 $1\times26^4$ 种。

将这些情况数目加起来，便是 $X/2<S/2$ 的情况。

那么还有一种情况有可能成立，不能忽略。就是上面第二条性质，回文串 $X$ 前半截等于 $S$ 的前半截的情况。这种情况只有一种，因此直接比较即可。算出 $X=BCADBBDACB$ 和 $S=BCADBABDDC$ 比较，$X>S$ 不满足题目要求。如果满足题目要求，答案 $+1$即可。

代码

#include <bits/stdc++.h>
#define MOD 998244353

using namespace std;

int main(void)
{
    int T;
    cin >> T;
    while (T--)
    {
        int N;
        string S;
        cin >> N >> S;
        long long ans = 0, p = 1;
        for (int i = (N - 1) / 2; i >= 0; i--)
        {
            ans += p * (S[i] - 'A');
            ans %= MOD;
            p *= 26;
            p %= MOD;
        }
        string palindrome = S;
        for (int i = 0, j = N - 1; i <= j; i++, j--)
            palindrome[j] = palindrome[i];
        if (palindrome <= S)
        {
            ans++;
            ans %= MOD;
        }
        cout << ans << endl;
    }
    return 0;
}