ABC242 E – (∀x∀)

题目连接：https://atcoder.jp/contests/abc242/tasks/abc242_e

翻译一下题目大意就是给定一个只包含大写字母的字符串S，输出所有字典序比S小且是回文串的字符串的数量

这道题直接枚举判断回文串不太好做而且会超时

我们可以从回文串入手，在S的基础上将前一般的子串翻转构造出一个回文串，这个回文串可能比S大，也可能比S小，

比如： S = "ABCZAZ", 那么我们第一步得到的回文串是: ABCCBA是比S字典序小的，那么这个回文串ABCCBA就是答案之一而且是字典序最大的

由于回文串是由前一半的字符串确定的，所以前一半字符串字典序小于ABC的字符串的数量就是答案（等于的情况后面再说）

那么如何求字典序小于ABC的的字符串的数量呢？

我们可以将只由大小字母构成的字符串看作一个26进制的数值， 那么这个26进制的数就是答案

比如：ABC的26进制值：0('A'-'A') * 26^2 + 1('B'-'A') * 26^1 + 2('C'-A') * 26^0 = 28

还有一些特殊情况：

1. 如果S的长度是奇数，那么当取前一半字符串的时候将中间的一并带上，拼接另一半时将第一个字符再删掉就可以了
2. 如果在S的基础上获得的回文串小于等于S，那么答案还要加1

代码：

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a;i < b;i++)
#define per(i,a,b) for(int i = b - 1;i >= a;i--)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int mod = 998244353;
int q;

int main() {
    scanf("%d", &q);
    rep(_,0,q) {
        int n;
        string s;
        cin >> n >> s;
        string ss = s.substr(0,(n+1)/2);
        string ss2 = ss;
        reverse(all(ss2));
        if(n % 2) ss2.erase(ss2.begin());
        ll c = 0;
        rep(i,0,(int)ss.size()) {
            c = (c * 26 + (ss[i] - 'A')) % mod;
        }
        if((ss + ss2) <= s) c = (c + 1) % mod;
        printf("%lld\n", c);
    }
    return 0;
}