E – (∀x∀)

题目描述：

给你一个长度为n的串s，问满足如下条件的串的数量mod 998244353的结果

• 长度为n
• 是一个回文串
• 字典序小于等于s

思路：

长度相等的情况下，两个字符串的字典序大小取决于第一个不相等的字符，所以我们可以只考虑s的前半部分，对于每个字符s[i]，当他作为第一个不想等的字符能产生的答案是 $26^{\lceil\frac{n}{2}\rceil-i}*(s[i]-'A')$,当他作为一个想等的字符的时候能产生的答案就由后面的字符决定，这就可以使用递归求解。

而递归的结束条件就是计算到了串的中间的位置，这个位置的要格外注意，想等的时候，要判断字典序的大小了就，因为前半部分都想等，决定字典序的只能看后面的了，这里我是分奇偶手动判了一个，其实可以调用函数的

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 1000000 + 50
ll n, m, k, op;
char tr[MAX];

ll q_pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll dfs(int id){
    if(id == k){
        int p = 1;
        if(n % 2 == 1){
            for(int i = 1; i < k; ++i){
                if(tr[k + i] == tr[k - i])continue;
                else if(tr[k - i] < tr[k + i]){
                    p = 1;
                    break;
                }
                else {
                    p = 0;
                    break;
                }
            }
        }
        else {
            for(int i = 1; i <= k; ++i){
                if(tr[k - i + 1] == tr[i + k])continue;
                else if(tr[k - i + 1] < tr[i + k]){
                    p = 1;
                    break;
                }
                else{
                    p = 0;
                    break;
                }
                
            }
        }
        return (ll)(tr[id] - 'A' + p);
    }
    ll num = ((ll)(tr[id] - 'A') * (ll)q_pow(26, k - id)) % mod;
    num = (num + dfs(id + 1)) % mod;
    return num;
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    k = (n + 1) / 2;
    cout << dfs(1) << endl;
}

int main(){
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}