実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 849

問題概要

英文字からなる文字列 $S$ が与えられる。 $S$ に以下の操作を $10^{100}$ 回繰り返す。

まず、 $S$ の大文字を小文字に、小文字を大文字に書き換えた文字列を $T$ とする。
その後、 $S$ と $T$ とをこの順に連結した文字列を新たな $S$ とする。

以下の $Q$ 個のクエリを処理せよ。

$i$ 番目のクエリ : 全ての操作を終えた後の $S$ の先頭から $K_i$ 文字目を出力する。

制約

$1 \leq |S| \leq 2 \times 10^5$
$Q, K_i$ は整数。
$1 \le Q \le 2 \times 10^5$
$1 \le K_i \le 10^{18}$

考察

$10^{100}$ 回の操作をすべてを実行するのは不可能だが、何らかの規則性はありそう。ということで、まずは実験してみる。

$\begin{align*} S_0 & = (S) \\ S_1 & = (S)(T) \\ S_2 & = (ST)(TS) \\ S_3 & = (STTS)(TSST) \\ S_4 & = (STTSTSST)(TSSTSTTS) \\ \cdots \end{align*}$

ただし、 $S{i+1} = (S_i)(T_i)$ という表し方をしている。これを見ると、 $S_i$ の長さは操作を行うごとに倍々になっていき、 $S_i$ の前半は $S_{i-1}$ に、後半は $S_{i-1}$ の大文字・小文字を反転した $T_{i-1}$ に一致していることが分かる。

あるステップに、その前のステップのものが含まれているような性質を自己相似性といい、その代表的なものがフラクタル図形である。この性質を持つものは、再帰的な探索が有効なことが多い。

実際、本問の背景には Thue-Morse 数列という自己相似性を持つ数列があるらしい。

では、今回も再帰関数の方針で解いてみる。

操作後の文字列からさかのぼっていくことを考えると、最終的に出力すべき文字のインデックス $k$ が $S_i$ の前半と後半のどちらに属しているかで処理が変わってくる。

具体的には、再帰関数を $f(今考えているステップの文字列, 出力すべきインデックス, 文字列の長さ)$ とすると、以下のような実装となる。ただし、 $l_0 = |S|$ 、 $flip(x)$ を文字列 $x$ の大文字・小文字を反転する関数とした。

$|s| = l_0$ ならば、 $s_k$ を出力する (ベースケース) 。
そうでないとき、として、
- $k \lt l$ ( $s_k$ が $s$ の前半にある) ならば、 $f(s, k, l)$ を呼び出す。
- そうでない ( $s_k$ が $s$ の後半にある) ならば、 $flip(f(s, k - l, l))$ を呼び出す。

このもとで、 $f(S, K, 2^{60})$ からさかのぼっていけばよい ( $2^{60} \leq 10^{18}$ なので、60回操作後の $S_{60}$ からで十分) 。

コード

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

using ll = long long;

// ======================================== //

char flip(char c)
{
    if (islower(c))
        return toupper(c);
    return tolower(c);
}

char f(const string &S, ll K, ll current_len)
{
    if (current_len == S.size())
    {
        return S[K];
    }

    ll prev_len = current_len / 2;
    if (K < prev_len)
    {
        return f(S, K, prev_len);
    }
    else
    {
        return flip(f(S, K - prev_len, prev_len));
    }
}

int main()
{
    string S;
    int Q;
    cin >> S >> Q;

    ll current_len = S.size();
    while (current_len < 1e18)
    {
        current_len *= 2;
    }

    while (Q--)
    {
        ll K;
        cin >> K;

        K--;
        cout << f(S, K, current_len) << endl;
    }
}