ABC242のA,B,C,D,E問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッター、マシュマロ、Discordサーバーまでお気軽にどうぞ！
Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー（質問や記事の感想・リクエストなどどうぞ！） : https://discord.gg/jZ8pkPRRMT
よかったらLGTMや拡散していただけると喜びます！
目次
ABC242 まとめ
A問題『T-shirt』
B問題『Minimize Ordering』
C問題『1111gal password』
D問題『ABC Transform』
E問題『(∀x∀)』 ←記号のせいでリンクが機能していないので、右にあるQiita公式のリンクから飛んでください
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC242 まとめ
全提出人数: 10462人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 45分 | 6928(6678)位 |
| 400 | AB------ | 300 | 17分 | 5580(5330)位 |
| 600 | AB------ | 300 | 6分 | 4586(4336)位 |
| 800 | ABC----- | 600 | 49分 | 3492(3250)位 |
| 1000 | ABC----- | 600 | 24分 | 2556(2319)位 |
| 1200 | ABCD---- | 1000 | 94分 | 1790(1565)位 |
| 1400 | ABC-E--- | 1100 | 81分 | 1234(1016)位 |
| 1600 | ABCDE--- | 1500 | 85分 | 815(618)位 |
| 1800 | ABCDE--- | 1500 | 44分 | 528(357)位 |
| 2000 | ABCDE-G- | 2100 | 98分 | 292(183)位 |
| 2200 | ABCDE-G- | 2100 | 69分 | 181(88)位 |
| 2400 | ABC-EFG- | 2200 | 84分 | 125(42)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | Ex |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 3626 | 91.1 % | 86.9 % | 20.2 % | 1.9 % | 1.2 % | 0.0 % | 0.3 % | 0.0 % |
| 茶 | 1578 | 97.7 % | 98.5 % | 64.6 % | 7.9 % | 4.8 % | 0.1 % | 1.5 % | 0.0 % |
| 緑 | 1206 | 97.6 % | 97.7 % | 92.0 % | 25.5 % | 19.2 % | 0.1 % | 5.6 % | 0.2 % |
| 水 | 717 | 97.8 % | 97.8 % | 97.3 % | 57.6 % | 53.0 % | 1.9 % | 15.8 % | 0.6 % |
| 青 | 408 | 97.5 % | 97.8 % | 97.8 % | 81.4 % | 86.0 % | 13.0 % | 36.0 % | 1.2 % |
| 黄 | 192 | 84.9 % | 84.4 % | 83.8 % | 75.5 % | 80.2 % | 40.1 % | 51.6 % | 6.8 % |
| 橙 | 41 | 87.8 % | 87.8 % | 87.8 % | 87.8 % | 87.8 % | 80.5 % | 73.2 % | 29.3 % |
| 赤 | 20 | 85.0 % | 85.0 % | 90.0 % | 90.0 % | 85.0 % | 85.0 % | 90.0 % | 60.0 % |
※表示レート、灰に初参加者は含めず
A問題『T-shirt』
問題ページ：A - T-shirt
灰コーダー正解率：91.1 %
茶コーダー正解率：97.7 %
緑コーダー正解率：97.6 %
入力
$A$ : 上位 $A$ 位までの参加者は必ずTシャツをもらえる
$B,\ C$ : $A+1$ 位から $B$ 位 までの参加者のうち、ランダムに選ばれた $C$ 人もTシャツをもらえる
$X$ : いろはちゃんの順位
考察
答えは以下の通りです。<と<=を間違えないように気をつけましょう。
$X\le{A}$ : $1$ （必ずもらえるため）
${A+1}\le{X}\le{B}$ : $\dfrac{C}{B-A}$ （$B-A$ 人のうち $C$ 人がもらえるため）
$B\lt{X}$ : $0$ （もらえない）
コード
def solve():
A, B, C, X = map(int, input().split())
if X <= A:
return 1
if A + 1 <= X <= B:
return C / (B - A)
return 0
print(solve())
B問題『Minimize Ordering』
問題ページ：B - Minimize Ordering
灰コーダー正解率：86.9 %
茶コーダー正解率：98.5 %
緑コーダー正解率：97.7 %
入力
$S$ : 英小文字のみからなる文字列
考察
$S$ をソートして出力するだけです。
実装
sorted(S) で $S$ を $1$ 文字ずつバラバラにしてソートしたリストが得られます。
これを空白・改行なしで出力するか、再び文字列に戻して出力すればいいです。
コード
リストのまま
S = input()
print(*sorted(S), sep='')
文字列に戻す
S = input()
print(''.join(sorted(S)))
C問題『1111gal password』
問題ページ：C - 1111gal password
灰コーダー正解率：20.2 %
茶コーダー正解率：64.6 %
緑コーダー正解率：92.0 %
入力
$N$ : 正の整数（$ 2\le{N}\le{10^6}$ ）
$998244353$ で割った余りを答える
考察
先に解法のアルゴリズムを書くと、この問題は 動的計画法（DP） で解きます。
問題文の意味を十分に理解している方は、問題自体の考察は飛ばして構いません。この項の次に動的計画法で解く方法を解説します
問題自体の考察
$2$ つの条件を満たす $N$ 桁の整数はいくつあるかを求める問題です。上から $i$ 桁目の数字を $X_i$ とすると、条件は以下の $2$ つです。
- 全ての整数 $1\le{i}\le{N}$ に対して、$1\le{X_i}\le{9}$
- 全ての整数 $1\le{i}\le{N-1}$ に対して、$|X_i-X_{i+1}| \le 1$ .
以下、これら $2$ つの条件について説明します。
条件1
単に、どの桁も使える数字は $1$ ～ $9$ の $9$ 種類というだけです。$0$ は使えません。
一番上の桁が $0$ では $N$ 桁の整数にならないという理由で設定されているだけだと思われるので、とくに深い意味はないです。
条件2
$|X_i-X_{i+1}| \le 1$ です。
$X_i$ は 『 $1$ つ 前の桁の数字』 、$X_{i+1}$ は 『その次の桁の数字』 です。例えば $i=5$ なら、$5$ 桁目の数字と $6$ 桁目の数字の間にこの制限があります。
条件の絶対値を外すと、$-1\le{X_i}-X_{i+1}\le1$ です。
つまり、『前の桁の数字』と『次の桁の数字』の差は、$-1,0,1$ のいずれかでなければいけません。
例えば $X_i=4$ なら、$X_{i+1}=3,4,5$ の $3$ 種類しか許されません。
例外として、条件 $1$ より $0$ と $10$ は使えないので、 $X_i=1$ なら $X_{i+1}=1,2、$$X_i=9$ なら $X_{i+1}=8,9$ の $2$ 種類しか許されません。
解法の方針
上の桁から $1$ 桁ずつ、使う数字を決めていきます。
- 一番上の桁は 条件 $2$ の制約がありませんから、$1$ ～ $9$ まで好きな数字を使うことができます。
- それ以降の桁は、『$1$ つ 前の桁の数字』に応じて、使える数字が制限されます。例えば、$8$ にしたいならば、『$1$ つ 前の桁の数字』は $7,8,9$ のいずれかでなければいけません。
必要な情報は
- $i$ 桁目まで確定させて
- $i$ 桁目で使った数字が $j$ であるときの
- ここまでで作った数字の種類数
です。
最終的に、 『$N$ 文字目まで確定させて、$N$ 文字目が $1$ ～ $9$ である組み合わせ数の総和（を $998244353$ で割った余り）』 が答えになります。
動的計画法による解法
ここまでの考察を踏まえて、動的計画法の状態・遷移を設計していきます。
状態
$\mathrm{dp}[i][j]$ : 上から $i$ 桁目まで決めて、$i$ 桁目の数字が $j$ である組み合わせ数（を $998244353$ で割った余り）
$i+1$ 桁目以降は未定で、これから決めます。$i$ 桁目が確定すれば、そこから $i+1$ 桁目の情報も確定させていくことができます。
答え
$\mathrm{dp}[N][j]$ （$1\le{j}\le{9}$) の総和を $998244353$ で割った余り
$N$ 桁目まで決めたというのは、つまり全ての桁を確定させたということです。一番下の桁が $1$ ～ $9$ のいずれも答えに含みますから、全部足し合わせます。
$998244353$ で割った余りで答えるのを忘れないように注意しましょう。非常に忘れやすいです。
初期値
$\mathrm{dp}[1][j]=1$ （ $1\le{j}\le{9}$ ）
一番上の桁だけを $1$ ～ $9$ のいずれかに決めた組み合わせ数は、もちろんそれぞれ $1$ 通りだけです。
遷移
$\mathrm{dp}[i+1][j]=(\mathrm{dp}[i][j-1]+\mathrm{dp}[i][j]+\mathrm{dp}[i][j+1])\ %\ 998244353$
前述の通り、$i+1$ 桁目を $j$ にする場合、$i$ 桁目は $j-1$、$j$、$j+1$ のいずれかでなければいけません。
本来 $j=1,9$ の場合はそれぞれ $\mathrm{dp}[i][j-1]$、$\mathrm{dp}[i][j+1]$ を省かなければいけませんが、実装を後述のように少しだけ工夫すると、この式をそのまま使うことができます。
実装
j=0, 10 もリストに含めると楽
$j=1,9$ の場合はそれぞれ $\mathrm{dp}[i][j-1]$、$\mathrm{dp}[i][j+1]$ を省かなければいけませんが、この場合分けは面倒です。
dp配列の二次元目の長さを $11$ にして、 $j=0,10$ も存在することにします。ただし、初期値は $0$ のままで、$j=0,10$ は値の変更を行いません。
そうすると、$j=0,10$ は何文字目だろうと常に $0$ ですから、$j=1,9$ の場合に足してしまっても影響がなくなります。
計算するたびに余りを取る
計算するたびに $998244353$ で割った余りを取ってください。そうしないと、組み合わせ数が非常に巨大な数となるため、TLEになります。
足し算・引き算・掛け算については、都度余りを取るのと、最後だけ余りを取るので答えは変わりません。
また、最後に総和を取った値が答えですが、ここで余りを取り忘れるのは大変よくあるミスなので、忘れずに余りを取ってください。
コード
通常版
CPythonではTLEになるので、PyPyで提出してください。
# PyPyの場合、MODのような定数はグローバルに置いたほうがやや速いらしい？
# Pythonはローカルに置いたほうが速い
MOD = 998244353 # 問題文からコピペするか、テンプレに10**9+7と一緒に入れとくといいです
def solve():
N = int(input())
dp = [[0] * 11 for _ in range(N + 1)] # 0~10があることにする
for i in range(1, 10):
dp[1][i] = 1 # 上から1桁目の1～9はそれぞれ1通り
for i in range(1, N):
for j in range(1, 10):
dp[i + 1][j] = (dp[i][j - 1] + dp[i][j] + dp[i][j + 1]) % MOD
return sum(dp[N]) % MOD
print(solve())
1次元目を省略して高速化
$2$ 文字以上前の数字が何かという情報は不要なので、$1$ 文字前と現在の文字の情報を持つ $2$ つの $1$ 次元リストを使い回すことで高速化できます。
PyPyを使わないことにこだわる意味はありませんが、Pythonでも1983msでギリギリ通りました。（※AtCoderは、あるテストケースでTLEになった場合複数回実行し、$1$ 回でもTLに間に合えばACになる仕様です。運が悪いと通らないかもしれません）
アルゴリズム自体に手を加えずこれ以上高速化する場合、ループアンローリング（ dp1[1] = (dp0[1]+dp0[2]) % 998244353 ……を手で $9$ 個書く）する必要があります。1500ms程度になるようです。
def solve():
N = int(input())
dp0 = [0] * 11
for i in range(1, 10):
dp0[i] = 1
for i in range(2, N + 1):
dp1 = [0] * 11
for j in range(1, 10):
dp1[j] = (dp0[j - 1] + dp0[j] + dp0[j + 1]) % 998244353
dp0 = dp1
ans = sum(dp1) % 998244353
return ans
print(solve())
D問題『ABC Transform』
問題ページ：D - ABC Transform
灰コーダー正解率：1.9 %
茶コーダー正解率：7.9 %
緑コーダー正解率：25.5 %
入力
$S$ : A, B, C のみからなる、長さ $1$ 以上 $10^5$ 以下の文字列
$Q$: クエリの数（最大 $10^5$）
$t_i$ : $i$ 個目のクエリでは、文字列に対して操作（後述）を $t_i$ 回行う（${0}\le{t_i}\le{10^{18}}$）
$k_i$ : $S$ に $t_i$ 回操作を行ったあとの文字列の、$k_i$ 文字目が何か答える
- $k_i$ は、操作後の文字列の長さ以下かつ、$10^{18}$ 以下
考察
はじめに解法を書くと、この問題は再帰関数で解けます。（他の解法もありますが、この解法を書くだけで力尽きました）
なお、この解説では $S$ の最初の文字を $S_0$ と表すことにします。つまり、$0$ 文字目から数え始めます。（問題文では $1$ 文字目から数えていますから、$k_i$ を $-1$ してください）
文字列を直接生成するのは不可能
操作 $1$ 回ごとに$1$ 文字が $2$ 文字に増えますから、操作後の文字列の長さは最大で $10^5\times2^{10^{18}}$ で、 $3\times{10^{22}}$ 文字程度です。$k_i$ 文字目より後の文字は答えに関係がないので、$k_i$ 文字より後の文字を捨てるとしても、 $k_i$ は最大で $10^{18}$ です。
これほど巨大な文字列を生成するのは不可能です。別の解法が必要になります。
取っ掛かりがつかめない→とりあえず操作で文字列の変化を見てみる
取っ掛かりがつかめない問題です。**こういうときは、とりあえず操作で文字列がどのように変化するか見てみると良いです。良い法則が見つかるかもしれません。**手書きではミスをするので、以下のようなコードを書いてみます。
S = "A"
T = 6
ttable = str.maketrans({"A": "BC", "B": "CA", "C": "AB"}) # 同時に変化させるので、replace3回ではダメ
for i in range(T + 1):
print(f"{i}: {S}")
S = S.translate(ttable)
すると、以下の出力が得られます。
0: A
1: BC
2: CAAB
3: ABBCBCCA
4: BCCACAABCAABABBC
5: CAABABBCABBCBCCAABBCBCCABCCACAAB
6: ABBCBCCABCCACAABBCCACAABCAABABBCBCCACAABCAABABBCCAABABBCABBCBCCA
ここで、縦方向に着目してみると、どうやら任意の $i$ について、$i$ 文字目は出現して以降、操作 $1$ 回ごとにA→B→C→A→B→C →A……と $1$ ずつ、周期 $3$ で進んでいることがわかります。（横に長くなりすぎるので操作は $6$ 回にしましたが、これ以上長くしても成り立ちます）
この特徴は後に使います。
操作の重要な特徴: 変化後の前半は変化前+1, 後半は+2
A は BC、B は CA、Cは ABに変化します。ABC をそれぞれ $0,1,2$ と整数で表してみます。すると、操作による変化は以下で表されます。
$0:12$
$1:20$
$2:01$
元の数字を $x$ とおき、$3$ を超えた場合は $3$ で割った余りを取ることにします。すると、**いずれの文字も操作後の前半は $x+1$、後半は $x+2$ に変化しています。**これも非常に重要な特徴です。
ABCを数字に置き換える
以後、文字ABC のかわりに、整数 $0,\ 1,\ 2$ を使います。余りや足し算を使うので、整数で扱って計算したあと、最後に文字に戻したほうが解きやすいからです。
再び出力を観察
先ほどの出力のABCを012に置き換え、さらにどの文字が操作でどの文字になったかわかりやすくするために、スペースを入れてみます。
0: 0
1: 1 2
2: 2 0 0 1
3: 0 1 1 2 1 2 2 0
4: 1 2 2 0 2 0 0 1 2 0 0 1 0 1 1 2
5: 2 0 0 1 0 1 1 2 0 1 1 2 1 2 2 0 0 1 1 2 1 2 2 0 1 2 2 0 2 0 0 1
6: 0112122012202001122020012001011212202001200101122001011201121220
例えば、$t=2$ は2001です。 これに操作を行った $t=3$ では、$4$ 文字が 01/12/12/20 の $8$ 文字に変化しています。
$t = 2$ の 何文字目が、$t=3$ の何文字目と何文字目に変化しているかを表にしてみます。
| t = 2 | t = 3 |
|---|---|
| 0文字目 | 0,1文字目 |
| 1文字目 | 2,3文字目 |
| 2文字目 | 4,5文字目 |
| 3文字目 | 6,7文字目 |
任意の $t$ で同様の関係が成り立ちますから、式にして一般化します。
『$t$ 回操作した時点の $k$ 文字目は、 $t-1$ 回操作した時点の $\lfloor{\dfrac{k}{2}}\rfloor$ 文字目が変化したもの』（上の出力で確認してみてください。なお、 $\lfloor{\dfrac{k}{2}}\rfloor$ は $k$ を $2$ で割って切り捨てた値です）
そして、$k$ の偶奇によって、$\lfloor{\dfrac{k}{2}}\rfloor$ 文字目が変化した前半部分か後半部分かわかるので、以下のことも言えます。
- $k$ が偶数（$0,2,4,6$）ならば、$t-1$ 回操作した時点の $\lfloor{\dfrac{k}{2}}\rfloor$ 文字目が変化した前半部分なので、$1$ 進む
- $k$ が奇数（$1,3,5,7$）ならば、$t-1$ 回操作した時点の $\lfloor{\dfrac{k}{2}}\rfloor$ 文字目が変化した後半部分なので、$2$ 進む
再帰関数で表せる
ここまでの特徴をまとめます。
-
任意の $i$ について、$i$ 文字目は操作ごとに $+1$ 進む
-
$t$ 回目の操作の $k$ 文字目は、 $t-1$ 回目の操作の $\lfloor{\dfrac{k}{2}}\rfloor$ 文字目が変化したものである
-
$k$ の偶奇で、変化前から $1$ 進むか $2$ 進むか決まる
これらの特徴を利用することで、再帰関数を用いてこの問題を解くことができます。
$f(t,k)$ を、$t$ 回操作した $S$ の $k$ 文字目 と定義します。 求めたいものは $f(t_i,k_i)$ ですが、もちろん直接は求められません。
特徴 $2$ より、$f(t,\ k)=f(t-1,\ \lfloor{\dfrac{k}{2}}\rfloor)+C$ （$C$ は $1$ または $2$） と表せます。特徴 $3$ より、$k$ が偶数なら $C=1$、奇数ならば $C=2$ です。したがって
- $k$ が偶数 ： $f(t,\ k)=f(t-1,\ \lfloor{\dfrac{k}{2}}\rfloor) + 1$
- $k$ が奇数 ：$f(t,\ k)=f(t-1,\ \lfloor{\dfrac{k}{2}}\rfloor) + 2$
となります。
この操作を続けると、いつかは $t$ または $k$ は $0$ になります。これらのケースは、 $O(1)$ で簡単に求めることができます。
t = 0 の場合
$f(0,\ k)$ です。$t=0$ というのは、操作を一度もしていない状態のことです。したがって、$f(0,\ k)=S_k$ です。
k=0 の場合
$f(t,\ 0)$ です。$S_0$ が $k$ 回の操作で何になるかわかればいいです。特徴 $1$ より、$0$ 文字目は $1$ 回操作するごとに、$+1$ 進みます。ということは、$t$ 回操作すると $+t$ 進みます。
したがって、$f(t,\ 0)=S_0+t$ です。
最終的な答え
$f(t,k)$ の値は A から何回進んだかを表します。A から $3$ 回進むと A に戻ってきますから、$f(t,k)$ を $3$ で割った余りによって、答えがA,B,Cのいずれかに定まります。
計算量について
$t$ が $1$ ずつしか減らないので、この再帰関数はいつまでも終わらないように思えるかもしれません。
**ですが、$k$ が 半分ずつ減っていくので、$k=10^{18}$ だとしても、$60$ 回 で $k=0$ まで減少します。**先述の通り、$f(t,\ 0)$ は $t$ がいくら大きくてもただの足し算で求められますから、最大でも $61$ 回の再帰関数実行で答えが求められます。
クエリ $1$ 回につき計算量は $O(\mathrm{min}(t_i\ ,\log{k_i}))$ です。$Q$ 回のクエリがあるので、全体では $O(Q・\mathrm{min}(t_i\ ,\log{k_i})))$ です。
コード
再帰が浅いので、PyPyのほうがPythonよりも高速です。
def main():
def rec(t, k):
if t == 0:
return pat.index(S[k])
if k == 0:
return pat.index(S[0]) + t
if k % 2 == 0:
return rec(t - 1, k // 2) + 1
else:
return rec(t - 1, k // 2) + 2
def solve():
t, k = map(int, input().split())
k -= 1 # 忘れずに
return pat[rec(t, k) % 3]
S = input()
Q = int(input())
pat = "ABC"
for _ in range(Q):
print(solve())
if __name__ == '__main__':
main()
E問題『(∀x∀)』
問題ページ：E - (∀x∀)
灰コーダー正解率：1.2 %
茶コーダー正解率：4.8 %
緑コーダー正解率：19.2 %
入力
$T$ : テストケースの数
各テストケース
$N$ : 文字列の長さ
$S$ : 英大文字のみからなる長さ $N$ の文字列
- $N$ の総和は $10^6$ を超えない
考察
回文とは、逆から読んでも同じ文字列のことを言います。つまり、前から $i$ 文字目を決めたら、後ろから $i$ 文字目も自動的に決まります。
実質的には、$N$ が偶数なら $S$ の前から半分、$N$ が奇数なら S の前から半分と中央の文字しか決定権はありません。つまり、前から $\lceil\dfrac{N}{2}\rceil$ 文字だけ考えればいいです。
X<S が確定した文字列だけ先に数える
先に、$X<S$ が確定している文字列だけ数え上げます。 初期値は $\mathrm{ans}=0$ とします。
そして、 $i=0$ からはじめて、$i=\lceil\dfrac{N}{2}\rceil-1$ まで、forループで以下の操作を繰り返します。（$0$ 文字目から数え始めるため、$-1$ しています）
- $\mathrm{ans}=26\times{\mathrm{ans}}$ （既に $X<S$ が確定しているため、
A～Zの $26$ 種類どれを付け加えても $X\lt{S}$） - $\mathrm{ans}=\mathrm{ans}+(S_iより辞書順で小さい英大文字の種類数)$ （ここまで $X=S$ で、今 $S_i$ より小さい文字を付け加えて $X\lt{S}$ にする）
- $\mathrm{ans}=\mathrm{ans}\ %\ 998244353$
中央までSと同じ文字列がX<=Sか判定する
最後に、$\lceil\dfrac{N}{2}\rceil$ まで $S$ と同じ文字列が、$X\le{S}$ を満たすか判定します。回分ですから、中央まで使う文字を確定させた場合、残り後半の文字列はそこまでの文字列を反転させたもの $1$ 通りのみです。この判定は、 『$S$ の前半を反転させたもの』 と 『$S$ の後半』 を比較するだけで済みます。
なお、$X=S$ になるのはこのケースで$S$ が回文の場合のみです。
実装
最後の判定で $+1$ したあと、$998244353$ で割った余りを取り忘れないように気をつけてください。$998244352+1$ 通りになるケースがあるのでWAになります。
コード
import sys
readline = sys.stdin.readline # 高速な入力ですが、改行文字も受け取るので、文字列を受け取る場合rstrip()で取り除く必要があります
MOD = 998244353
def main():
ston = lambda S, initial=0: [(ord(c) | 32) - 97 - initial for c in S]
div_ceil = lambda x, y: (x + y - 1) // y
def solve():
N = int(readline())
S = ston(readline().rstrip()) # 文字列を"A=0, B=1, ……,Z=25"のリストに変換する関数
H = div_ceil(N, 2) # xをyで割って切り上げた値を返す関数
ans = 0 # X < S が確定した文字列の数
for ch in S[:H]:
ans *= 26 # 既にX < Sが確定している文字列にはA~Zの26個何をくっつけても良い
ans += ch # ここまでSと同じで、今chより小さい文字を使うパターン
ans %= MOD # 忘れずに
# H文字目までSと同じにしたとき、X <= S になるか
fh, sh = S[:H], S[-H:]
if fh[::-1] <= sh:
ans += 1
ans %= MOD # 忘れずに
return ans
T = int(readline())
for _ in range(T):
print(solve())
if __name__ == '__main__':
main()