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