fork download
copy 
  1. #pragma GCC optimize("O3", "unroll-loops")
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<iomanip>
  5. #include<cstring>
  6. #include<vector>
  7. #include<map>
  8. #include<set>
  9. #include<queue>
  10. #include<stack>
  11. #include<cmath>
  12. #include<climits>
  13. #include<numeric>
  14. using namespace std;
  15. #define fastio() ios::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
  16. #define int long long
  17. #define SZ(x) (int)x.size()
  18. #define ALL(x) (x).begin(), (x).end()
  19. #define RALL(x) (x).rbegin(), (x).rend()
  20. #define trav(a) for(auto p:a)cout<<p<<" ";cout<<"\n";
  21. const int MOD = 998244353;
  22. const long long INF = 1e18 + 42;
  23. //••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••
  24. /*Theorems reminder:
  25. Wilson : (p-1)! mod p = -1 or p-1, p is prime
  26. Fermet : a^-1 mod p = a^(p-2) mod p, p is prime,a^(p-1) = 1 mod p
  27. exteuclid, modInverse, matrixExp., sieve
  28. */
  29. inline void read (int*a, int n) {
  30.       for (int i = 0; i < n; i++) cin >> a[i];
  31. }
  32. inline void read (vector<int>&a) {
  33.       for (auto &x : a) cin >> x;
  34. }
  35. inline int add (int a, int b, int mod = MOD) {
  36.       a += b; return a >= mod ? a - mod : a;
  37. }
  38. inline int sub (int a, int b, int mod = MOD) {
  39.       a -= b; return a < 0 ? a + mod : a;
  40. }
  41. inline int mul (int a, int b, int mod = MOD) {
  42.       return (int) ( (long long) ((a % mod) * (b % mod)) % mod);
  43. }
  44. inline int mpow (long long base, long long ex, int mod = MOD) {
  45.       int res = 1;
  46.       for (; ex > 0; ex >>= 1) {
  47.             if (ex & 1) res = mul (res, base, mod);
  48.             base = mul (base, base, mod);
  49.       }
  50.       return res;
  51. }
  52. inline int inv (int a, int mod = MOD) {
  53.       return mpow (a, mod - 2, mod);
  54. }
  55. inline int __ceil (int n, int d) {
  56.       return (n + d - 1) / d;
  57. }
  58. //••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••
  59.  
  60.  
  61.  
  62.  
  63. int dp[1000001][2][2];
  64. int getAns(int i, string &s, int n, int f, int r) {
  65.       if (i >= (n + 1) / 2) {
  66.             return f == 1 || r == 1;
  67.       }
  68.  
  69.  
  70.       if (dp[i][f][r] != -1)return dp[i][f][r];
  71.  
  72.       int ans = 0;
  73.       if (f) {
  74.             if (n % 2 == 1)
  75.                   ans = mpow(26LL, n / 2 - i + 1) % MOD;
  76.             else {
  77.                   ans = mpow(26LL, n / 2 - i) % MOD;
  78.             }
  79.       }
  80.       else {
  81.             for (char c = 'A'; c <= s[i]; c++) {
  82.                   if (c < s[i]) {
  83.                         ans = add(ans, getAns(i + 1, s, n, 1, r) % MOD);
  84.                   }
  85.                   else {
  86.                         if (s[n - i - 1] < s[i]) {
  87.                               ans = add(ans, getAns(i + 1, s, n, f, 0) % MOD);
  88.                         }
  89.                         else
  90.                               ans = add(ans, getAns(i + 1, s, n, f, r | (s[i] < (s[n - i - 1]))) % MOD);
  91.                   }
  92.  
  93.             }
  94.       }
  95.       return dp[i][f][r] = ans;
  96. }
  97. bool isPal(string &s) {
  98.       for (int i = 0; i < SZ(s) / 2; i++) {
  99.             if (s[i] != s[SZ(s) - i - 1])return false;
  100.       }
  101.       return true;
  102. }
  103. void SolveCase() {
  104.  
  105.  
  106.  
  107.       int n;
  108.       cin >> n;
  109.       string s;
  110.       cin >> s;
  111.  
  112.       int f = 0;
  113.       if (isPal(s))f = 1;
  114.       for (int i = 0; i <= n; i++) {
  115.             dp[i][0][0] = dp[i][1][0] = -1;
  116.             dp[i][0][1] = dp[i][1][1] = -1;
  117.       }
  118.  
  119.       cout << getAns(0, s, n, 0, 0) + f << "\n";
  120. }
  121. signed main()
  122. {
  123.       fastio()
  124.       int tt = 1; cin >> tt;
  125.       for (int t = 1; t <= tt; t++) {
  126.             // cout << "Case #" << t << ": ";
  127.             SolveCase();
  128.       }
  129.       // cerr << "Time : " << 1000 * ( (double) clock() ) / (double) CLOCKS_PER_SEC << "ms\n";
  130. }
  131.  
  132.  
Runtime error #stdin #stdout 0.01s 34608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7YDmwL
5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!