很巧妙的一道题。
题意
给定一个字符串 \(S\)，只包含字符 A，B，C。
每过一个时刻，字符会发生变化：A\(\to\)BC，B\(\to\)CA，C\(\to\)AB。
设 \(0\) 时刻为 \(S_0=S\)。
进行 \(Q\) 次询问，每次询问时刻 \(t\) 时，字符串 \(S_t\) 中第 \(k\) 个字符。
分析
为了方便处理，我这里将所有下标减一。
经过观察可以得出，\(t \ (t>0)\) 时刻的第 \(k\) 个字符，一定是由 \(t-1\) 时刻的第 \(\left\lfloor\dfrac k 2\right\rfloor\) 个字符变化而来的。
如果 \(k \bmod 2 = 0\) 则是变化后的第一个字符，否则是第二个。
此时就可以倒推出 \(0\) 时刻对应的字符，再返回得到答案。
但是发现这样一个递归求解的复杂度是 \(O(t)\) 的，无法接受。
\(\log_2 k + 1\) 次操作后 \(k=0\) 且不会再变，此时构成了一个 ABC 的循环节。
单次询问时间复杂度 \(O(\min(t,\log_2 k))\)。
代码
//the code is from chenjh
#include<cstdio>
#define MAXN 100005
using namespace std;
typedef long long LL;
char s[MAXN];
const char T[3][3]={"BC","CA","AB"};//打表每种字符对应的情况，避免大量的分类讨论。
char dfs(const LL&t,const LL&k){return k?(t?T[dfs(t-1,k>>1)-'A'][k&1]:s[k]):(s[0]-'A'+t%3)%3+'A';}//k=0 不再变化时，直接由循环节得出，否则如果 t=0 返回第 k 位字符，否则获取上个时刻的字符。
int main(){
int q;
scanf("%s %d",s,&q);
for(LL t,k;q--;) scanf("%lld%lld",&t,&k),putchar(dfs(t,k-1)),putchar('\n');//因为下标减一，所以查询的时候也要减一。
return 0;
}