[ABC242] E - (∀x∀)

[Q] https://atcoder.jp/contests/abc242/tasks/abc242_e

かわいい顔文字してる。
桁DP[アルファベット26文字][ぴったり文字かどうか] = 何通り
に当てはめればいい感じ。

実装

int main() {
 ll T;
 cin >> T;
 rep(i, T) {
   ll N;
   string S;
   cin >> N >> S;
   // 桁DP
   mint DP[30][2];  // alphabet, bool
   ll mid = (N + 1) / 2;
   rep(j, mid) {
     // 交換用の新しい桁DP
     mint nDP[30][2]{};
     ll c = S[j] - 'A';
     // 初期だけ
     if (j == 0) {
       rep(k, c) { ++nDP[k][false]; }
       ++nDP[c][true];
     } else {
       // false->false
       rep(k, 26) {
         rep(x, 26) { nDP[x][false] += DP[k][false]; }
       }
       // true->false
       rep(k, 26) {
         if (DP[k][true] > 0) {
           rep(x, c) { nDP[x][false] += DP[k][true]; }
           // true->true
           nDP[c][true] += DP[k][true];
           break;
         }
       }
     }
     swap(nDP, DP);
   }
   mint ans = 0;
   // こたえは、ありうるパターンの総和
   rep(i, 26) rep(j, 2) { ans += DP[i][j]; }

   // 最後ぴったりの回文を作ったときに、採用されるかだけ確認
   // S="ABCDD" なら T="ABCBA" は採用。
   // S="ABCAA" なら T="ABCBA" は不採用。
   string T = S.substr(0, N / 2);
   reverse(all(T));
   string nT = S.substr(0, N / 2);
   if (N % 2) nT += S[N / 2];
   nT += T;
   if (nT > S) --ans;
   cout << ans << endl;
 }
}

https://atcoder.jp/contests/abc242/submissions/29888967