E – (∀x∀)(思维 + 字符串)

发布于 2022-03-13  1218 次阅读


题目传送门: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;
}