题目大意

给定一个长度不定的字符串 S，现在你要对 S 执行 10^{100} 次操作，每次操作分两个步骤：

• 首先新开一个字符串 T，并让 T 等于 S 中所有大小字母颠倒。
• 然后让 S 在末尾连接上 T，形成新的字符串 S。

接下来有 Q 次询问，第 i 次询问要求输出进行了 10^{100} 次操作后的字符串 S 里，第 K_i 个字符是什么。

思路

赛时想了大半年，不得不说还是菜。菜，就多练呀。欢迎各位大佬来踩爆这个蒟蒻。

废话不多说我们进入正题，这道题目该怎么做呢？

一看就知道，不能够真的进行 10^{100} 次操作得到这个 S，时间空间都承受不了，只能找规律咯。

正着找，你试试看就会发现，根本没用，啥都找不出来。那咋办？反着倒退呗。

首先要获得一个 q，使得 n \times 2^q \ge K > n \times 2^{q-1}，我们让 p=n \times 2^q，因为 q 其实是没什么用的，p 最重要。p 是什么呀？p 是经过最少操作使得 S 存在第 K 个字符的情况下，S 的长度。这可以通过一个简短的 while 循环实现，不会超时。

接下来我们折半来看，如果当前的 K 处于这个长度的右边一半，那么它是会颠倒大小写的，我们便让记录大小写的 bool 变量 flag 进行一次非运算来颠倒，并把 K 重置为 K - p \div 2。否则，那么可以直接折半，K 还是老样子，flag 也不变。进行完一轮这个，把 p 缩小，变成 p \div 2 就行啦。

这样的操作要一直做到什么时候呢？一直做到这个 K 呀，已经满足 K \le |S| 啦，那么就一直折半变到了最开始那个 S 的范围内啦。这个时候只要看看 S_k 是什么，再根据 flag 进行或不进行大小写颠倒，最后输出就行啦。

好啰嗦，思路也怪怪的，还是看代码吧，代码倒是简单。

赛时 AC 代码

你们就爱看这个，我清楚得很。没事，尽管看，就是能够 AC 滴！不过因为赛时调试了一下，导致记录里是有一些注释的，忽略就行，下面这个代码里的，被我删掉啦！

#include<bits/stdc++.h>
using namespace std;
int Q,n;
string s;
int main(){
    cin>>s;n=s.size();s=" "+s;
    cin>>Q;
    while(Q--){
        long long k,p=n;cin>>k;
        while(k>p)p<<=1;
        bool flag=0;
        while(k>n){
            long long tmp=k;
            if(tmp>p/2)tmp-=p/2,flag=!flag;
            k=tmp;p/=2;
        }
        if(flag){
            if(s[k]>='A'&&s[k]<='Z')cout<<char(s[k]-'A'+'a')<<" ";
            else cout<<char(s[k]-'a'+'A')<<" ";
        }
        else cout<<s[k]<<" ";
    }
    return 0;
}

还是不太难吧？欢迎点赞，谢谢！