题目1：abc242_d
题意
-
有一个由
A,B,C组成的字符串 \(S(0)\)，对于字符串 \(S(i)\)，它会通过以下方式变为 \(S(i + 1)\)：A->BC，B->CA，C->AB。给定 \(q\) 组询问，问 \(S(t_i)\) 的第 \(k_i\) 个字符是什么。 -
\(1 \le q,|S(0)| \le 10^5,1 \le t_i,k_i \le 10^{18}\)。
思路
-
\(S(x)\) 的第 \(y(y = 0, 1, \dots)\) 个字符是由 \(S(x - 1)\) 的第 \(\lfloor \frac{y}{2} \rfloor\) 转移过来了。
-
由此可以得到一个思路：令数字 \(0,1,2\) 分别表示 \(A,B,C\)，\(F(x, y)\) 为 \(S(x)\) 的第 \(y\) 个字符对应数字。那么 \(F(x,y) = (F(x - 1, \lfloor \frac{y}{2} \rfloor) + 1 + y \% 2) \% 3\)，当 \(x = 0\) 时返回 \(S(0)_y\)。
-
但是显然这个时间复杂度高达 \(O(t_i)\)，会超时，那该怎么办了。可以发现若 \(y = 0\) 了，\(F(x, y) = (F(x - 1, 0) + 1) % 3\)，也就是 \((F(0, 0) + x) \% 3\)，所以当 \(y = 0\) 时直接返回 \(S(0)_\) 对应数字 + x 再 对 \(3\) 取模即可。
-
时间复杂度： \(q\) 组询问，每次到用 \(F(x,y)\)，因为每次 \(y = \lfloor \frac{y}{2} \rfloor\)，需要 \(log \ y\) 次到 \(0\)，总时间复杂度：\(O(q \times log \ k_i)\)。