TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

(∀x∀)

問題

E – (∀x∀)
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 998244353;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

int main() {
  int T;
  cin >> T;

  while(0 < T) {
    int N;
    string S;
    cin >> N >> S;

    if(N == 1) {
      cout << (int)(S[0] - 'A') + 1 << endl;
      T--;
      continue;
    }

    int center = (N + 1) / 2;
    mint ans = 0;
    rep(i, center) {
      int c = S[i] - 'A';
      mint cnt = mint(26).pow(center - (i + 1));
      ans += c * cnt;
    }
    string s1 = S.substr(0, center);
    string s2 = s1;
    reverse(s2.begin(), s2.end());
    string res = "";
    if(N % 2 == 0) {
      res = s1 + s2;
    } else {
      s1.erase(s1.end() - 1);
      res = s1 + s2;
    }
    if(res <= S) {
      ans += 1;
    }
    cout << ans.val() << endl;

    T--;
  }
  return 0;
}