题目：AXA(我个人觉得很难得题）
2024-07-30 17:25:23
发布于：广东
9阅读
0回复
0点赞
问题描述
解决以下问题，共有T个测试用例。
给定整数N和字符串S，找到满足以下所有条件的字符串X的数量，取模998244353。
X是由大写英文字母组成的长度为N的字符串。X是一个回文字符串。X≤S按字典顺序排列。也就是说，X=S或X按字典顺序小于S。约束条件1≤T≤250000。N是介于1和106之间的整数（包括边界）。在单个输入中，所有测试用例中的N的总和最多为106。S是由大写英文字母组成的长为N的字符串。输入以以下格式从标准输入中给出：T case1 case2...caseT
这里，casei代表第i个测试用例。
每个测试用例的格式如下：
N
S
输出T行。 第i行应当包含第i个测试用例的答案，以整数形式呈现。
示例1
5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW
输出
24
29
212370247
36523399
231364016
解题
#include<bits/stdc++.h>
using namespace std;
const long long m=998244353;
long long p[20231004]={1};
void dfs(){
int n;
long long a=1;
cin>>n;
for(int i=1;i<=n;i++){
p[i]=p[i-1]*26;
p[i]%=m;
}
string s;
cin>>s;
long long len=(n+1)/2;
for(int i=n/2+n%2,j=n/2-1;i<n;i++,j--){
if(s[i]<s[j]){
a=0;
break;
}
if(s[i]>s[j]){
a=1;
break;
}
}
for(int i=0;i<n/2+n%2;i++){
a=a+(p[len-i-1]*(s[i]-65))%m;
a%=m;
}
cout<<a%m<<'\n';
}
int main(){
int t;
cin>>t;
while(t--){
dfs();
}
return 0;
}
这里空空如也
有帮助，赞一个