AtCoder ABC 380 D - Strange Mirroring (1Q, 緑色, 350 点)

実験していくうちにシンプルな構造がわかった。

• 問題へのリンク

問題概要

英文字からなる長さ の文字列 が与えられる。この文字列に対して、次の操作を 回行ってできる文字列を考える。

【操作】
文字列 に対して、英小文字と英大文字を入れ替えてできる文字列を として、 を で置き換える

この文字列に対して、 回のクエリ「整数 が与えられるので、先頭から 番目の文字に答えよ」に答えよ。

制約

• 
• 

考えたこと

0-indexed で考えることにする。クエリとして与えられる の値もデクリメントしておくこととする。

さて、もとの文字列 に対して、大文字と小文字を入れ替えた文字列を としよう。このとき、操作を十分回数行うと、

をこの順に連結したものとなる。まず一つ重要なことは、 を で割った商を 、余りを とすると、求める文字は、

• 上記の文字列の列の 番目の文字列について
• 先頭から 番目の文字

であるということだ。よって、問題は次のものに帰着される。

---

文字列の列

について、 番目のものは のいずれか？

---

文字列の列を考える

文字列の列に何か規則性がないかと考えてみよう。注目したいことは、「文字列の列」の作り方からして、文字列の列の 番目は、 と交互になっていることだ（文字列の列の作り方から明らか）。

このことから、きっと文字列の列の 番目の値は、 を二進法で表すと、良いことがあるのではないかと考えた。やってみよう！！

番目	番目（二進法）	文字列	二進法の 1 の個数
0	0		0
1	1		1
2	10		1
3	11		2
4	100		1
5	101		2
6	110		2
7	111		3
8	1000		1
9	1001		2
10	1010		2
11	1011		3
12	1100		2
13	1101		3
14	1110		3
15	1111		4

これを見ると、文字列の列の 番目の項は、 を二進法で表したときの 1 の個数を として、

---

• が偶数のとき：
• が奇数のとき：

---

となることがわかる。証明は、一般に 未満の整数 に対して、 であることから導ける（詳細は公式解説より）。

計算量は となる。

コード

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

int main() {
    long long Q, K;
    string S;
    cin >> S >> Q;

    auto flip = [&](char c) -> char {
        if (islower(c)) return toupper(c);
        else return tolower(c);
    };

    while (Q--) {
        cin >> K;
        K--;
        long long q = K / S.size(), r = K % S.size();

        long long num = 0;
        for (int i = 0; i < 61; i++) if (q & (1LL << i)) num++;
        if (num % 2 == 0) cout << S[r] << " ";
        else cout << flip(S[r]) << " ";
    }
    cout << endl;
}