概要

各文字列について、暗号化操作を \(K\) 回繰り返した後の文字列を求めます。
\(K\) は最大 \(10^{18}\) と非常に大きいため、操作をそのまま \(K\) 回シミュレーションすることはできません。

考察

暗号化操作は、文字列中の文字のアルファベット順の値の合計 \(S\) の偶奇によって決まります。

• \(S\) が奇数なら、文字列を反転する
• \(S\) が偶数なら、各文字を \(1\) つ後ろにずらす

重要なのは、操作後に \(S\) の偶奇がどう変化するかです。

反転の場合

文字列を反転しても、含まれる文字は変わりません。

したがって、\(S\) の値も変わらず、偶奇も変わりません。

つまり、最初に \(S\) が奇数なら、何回操作しても常に「反転」が行われます。

反転を \(2\) 回行うと元に戻るので、

• \(K\) が奇数なら反転
• \(K\) が偶数ならそのまま

です。

文字を \(1\) つ後ろにずらす場合

次に、\(S\) が偶数で「各文字を \(1\) つ後ろにずらす」場合を考えます。

各文字の値は次のように変わります。

• a \(\to\) b: \(1 \to 2\)
• b \(\to\) c: \(2 \to 3\)
• …
• y \(\to\) z: \(25 \to 26\)
• z \(\to\) a: \(26 \to 1\)

どの場合も、文字の値の偶奇は必ず反転します。

例えば、

• \(1 \to 2\) で奇数から偶数
• \(2 \to 3\) で偶数から奇数
• \(26 \to 1\) で偶数から奇数

となります。

つまり、文字列の長さを \(L\) とすると、全体の合計 \(S\) の偶奇は

• \(L\) が偶数なら変わらない
• \(L\) が奇数なら反転する

ことになります。

場合分け

最初の \(S\) の偶奇を見て、以下のように分けられます。

1. \(S\) が奇数の場合

常に反転だけが行われます。

そのため、

• \(K\) が奇数なら反転
• \(K\) が偶数ならそのまま

です。

2. \(S\) が偶数、かつ文字列長が偶数の場合

文字を \(1\) つ後ろにずらしても、\(S\) の偶奇は偶数のままです。

したがって、毎回「文字を \(1\) つ後ろにずらす」操作が行われます。

\(K\) 回行うと、各文字を \(K\) 個後ろにずらせばよいです。

アルファベットは \(26\) 文字なので、実際には \(K \bmod 26\) だけずらせば十分です。

3. \(S\) が偶数、かつ文字列長が奇数の場合

最初の操作では、文字を \(1\) つ後ろにずらします。

このとき文字列長が奇数なので、\(S\) の偶奇は偶数から奇数に変わります。

以降は \(S\) が奇数なので、ずっと反転操作になります。

つまり、

• まず必ず \(1\) 文字ずつ後ろにずらす
• 残り \(K-1\) 回は反転を繰り返す

反転は \(2\) 回で元に戻るので、\(K-1\) が奇数なら反転します。

これは \(K\) が偶数のときです。

したがって、

• まず全体を \(1\) 文字ずらす
• \(K\) が偶数なら反転する

となります。

アルゴリズム

各文字列 \(W\) に対して、次を行います。

1. 各文字の値の偶奇を調べ、合計 \(S\) の偶奇を求める
   • a は \(1\)、b は \(2\)、…、z は \(26\)
   • 実際には合計値そのものではなく、偶奇だけ分かればよい
2. \(S\) が奇数なら
   • \(K\) が奇数なら \(W\) を反転
   • \(K\) が偶数なら何もしない
3. \(S\) が偶数なら
   • \(|W|\) が偶数なら、各文字を \(K \bmod 26\) だけ後ろにずらす
   • \(|W|\) が奇数なら、各文字を \(1\) つ後ろにずらし、さらに \(K\) が偶数なら反転する
4. 結果を出力する

例えば、\(W =\) abc の場合を考えます。

文字の値の合計は

\[ 1 + 2 + 3 = 6 \]

なので偶数です。文字列長は \(3\) で奇数です。

したがって、最初に各文字を \(1\) つずらして bcd になります。
その後は反転操作だけになります。

• \(K=1\) なら bcd
• \(K=2\) なら dcb
• \(K=3\) なら bcd

となります。

計算量

• 時間計算量: \(O\left(\sum |W_i|\right)\)
• 空間計算量: \(O(L)\)

ただし、\(L\) は処理中の文字列の長さです。
各文字列について、文字を一度ずつ確認し、必要なら一度ずつ変更するだけなので、全体で入力文字列長の合計に比例します。

実装のポイント

\(S\) の偶奇だけが必要なので、合計値をそのまま持つ必要はありません。

コードでは次のようにして偶奇を求めています。

int parity = 0;
for (char c : W) {
    parity ^= ((c - 'a' + 1) & 1);
}

これは、各文字の値の偶奇を足し合わせた結果の偶奇を求めています。

また、文字を \(x\) 個後ろにずらす処理は次のように書けます。

c = char('a' + (c - 'a' + x) % 26);

z の次が a になる処理も、剰余 % 26 によって自然に扱えます。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    cin >> N >> K;

    while (N--) {
        string W;
        cin >> W;

        int parity = 0;
        for (char c : W) {
            parity ^= ((c - 'a' + 1) & 1);
        }

        auto shift_chars = [&](int x) {
            for (char &c : W) {
                c = char('a' + (c - 'a' + x) % 26);
            }
        };

        if (parity == 1) {
            if (K % 2 == 1) reverse(W.begin(), W.end());
        } else {
            if (W.size() % 2 == 0) {
                shift_chars(K % 26);
            } else {
                shift_chars(1);
                if (K % 2 == 0) reverse(W.begin(), W.end());
            }
        }

        cout << W << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。