题解：AT_abc380_d [ABC380D] Strange Mirroring

CloverArmeriaThrift · 2024-11-18 18:36:55 · 题解

题目大意

给定一个字符串 S，执行 10^{100} 次以下操作：

• 首先，令字符串 T 为字符串 S 中所有大写字母变为小写字母，小写字母变为大写字母的结果。
• 其次，将 T 拼接在 S 后面。

接下来，有一些询问：

• 请输出在所有操作执行完成之后 S 的第 K 个字母。

  思路

  乍一看，好大的数据范围！这题真难！

仔细思考一番发现，我们可以令原始的 S 为一号串，刚开始T 为二号串，然后每一次操作完的字符串就是一号串和二号串的组合。

于是，这题是……找规律？

以下内容为考场上研究的内容：

1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
1  2  2  1  2  1  1  2  2  1  1  2  1  2  2  1  2  1  1  2  1  2  2  1  1  2  2  1  2  1  1  2  2  1  1  2  1  2  2  1  1  2  2  1  2  1  1  2  1  2  2  1  2  1  1  2  2  1  1  2  1  2  2  1

1           2           3           4           5           6           7           8           9           10          11          12          13          14          15          16
1           2           2           1           2           1           1           2           2           1           1           2           1           2           2           1

1                                               2                                               3                                               4                                     
1                                               2                                               2                                               1                                     

解释一下，这堆东西每两行为一组，每组中第一行为位置，第二行为编号（一或二）。第一组是刚才说的一号二号串的组合，第二组就是把第一组中的 1 2 2 1 看作一号串，2 1 1 2 看作二号串，第三组同理。

规律的话嘛，就是可以发现每一层的规律都一样，最后一层就是 1 2 2 1。当然不能直接计算出来了，不过可以递归。单次查询的时间复杂度不高，递归调用的时间复杂度较为合理。dfs(x) 的时间复杂度为线性级的，可以解决本题。

代码

Submission #59860658