防封题解(2)

给定一个格式串 S，将按以下方式将其扩展无穷多次：

• 在 S 的后面插入 把 S 的所有字母大小写反转后的字符串。

求最终的串中第 k_i(1\le k_i\le 10^{18}) 个字母是多少。有多组询问。

二进制拆位练手题。

设原来 S 的长度为 l，不难想到在第 i 次扩展后，S 的长度为 l\times 2^{i-1}，可以通过枚举求出第 k_i 个字符是第几次扩展后被确定的。

根据题意，如果是通过奇数次确定，则大小写将会反转；否则不会反转。并且在反复的减去 2 的幂次以及拆位过程中，我们可以求出其源自原来 S 的哪个字符，问题就求解完成了。

AC 记录。