题目传送门：E - (∀x∀) (atcoder.jp)

题目大意

给定一个字符串S，求出所有符合条件的字符串 X 的数量，要求x.length = s.length = N，X <= S（字典序），X 是回文串。

思路

因为要求X是回文串，所以只需要考虑左半部分，右半部分会自动补齐。

令mid = (n + 1) / 2，我们的 S 从 1 开始计数。

要求X <= S，所以我们将X分为两类：

第一类：X(left) == S(left)。

第二类：X(left) < S(left)。

判断第一类是否符合条件，只需要根据S(left)来构造回文串 b ，再判断b是否小于等于s即可。

重点在判断第二类，要让X(left)字典序小于S(left)，就需要从左往右有X[i] < S[i]，且j > i没有限制，j < i要求X[j] == S[j]。

假如X[1]小于S[1]，那么后面的数字都可以任选，那么方案数一共是(s[1] - x[1]) * (26 ^ (mid - 1))，最终将会形成一个26进制的数字，转换成10进制即可。

具体看代码。

代码

/*Copyright (C) Eriktse 2022*/
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <bitset>
#include <utility>
#define fi first
#define se second
#define gc getchar
#define pr printf
#define sc scanf
#define pb push_back
#define int long long
//用%lld输出long long类型数据
using namespace std;
inline int readInt()
{
	int s = 0,w = 1;char c = gc();
	while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();}
	while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
	return s * w;
}
inline string readString()
{
	string s;char c = gc();
	while(c == '\r' || c == '\n')c = gc();
	while(c != '\r' && c != '\n'){s += c,c = gc();}
	return s;
}
/*--------全局变量--------*/
const int mod = 998244353;

/*--------自定义函数-------*/

inline void solve()
{
	int n = readInt();
	string s = '0' + readString();
	string bps = s;
	int ans = 0;
	int mid = (n + 1) / 2; 
	for(int i = 1;i <= mid; ++ i)ans = (ans * 26 + s[i] - 'A' + mod) % mod;
	//将s构造成自身回文 
	string b = s.substr(1, mid);
	reverse(b.begin(), b.end());
	if(n & 1)s.erase(mid, n + 1);
	else s.erase(mid + 1,n + 1);
	s += b;
	//构造完毕 
	if(s <= bps)ans = (ans + 1) % mod;//这里不能写ans ++，会被hack 
	pr("%lld\n",ans);
}

signed main()
{
	int T = readInt();
	while(T --)solve();
	return 0;
}