有 $N$ 个装置排成一排，组成一个系统。每个装置有两种状态 $\texttt A$ 和 $\texttt B$。具体地，假想有一个小球从最左侧进入这个系统，则两种状态的行为如下：。
$\texttt A$：将球反弹回原方向。
$\texttt B$：让球通过，不改变方向。
当然，每当一个小球经过一个装置后，无论是以 $\texttt A$ 状态还是 $\texttt B$ 状态经过，装置都将改变原来的状态 (即 $\texttt A$ 变 $\texttt B$，$\texttt B$ 变 $\texttt A$)。
现在给定初始情况下所有装置的状态，求 $K$ 个小球经过后装置的状态。
第一行包含两个正整数 $N, K$ ($N \leq 2 \times 10^5; K \leq 10^9$)，分别表示装置的个数和经过的小球数。
第二行包含一个由 $\texttt A$ 和 $\texttt B$ 构成的字符串 $S$ ($\left| S \right| = N$)，其中第 $i$ 个字符表示左起第 $i$ 个装置的状态。
输出一行，包含一个字符串 $S_K$，表示 $K$ 次小球经过后状态的状态，具体格式同输入。
首先，分析当一个小球经过时，改变的状态。下面方便起见，把 $\texttt A$ (会反弹的) 称为「墙」，把 $\texttt B$ (直接通过的) 称为「地」。
根据第一个位置 $S_1$ 是否是「墙」进行讨论：
$S_1$ 是「墙」。
此时小球将直接弹回，然后 $S_1$ 变回「地」。
$S_1$ 是「地」。
通过对较小的情况的尝试，不难发现一个结论：
若记 $\bar x$ 为与状态 $x$ 相反的状态，则若 $S_1$ 是「地」，则新状态 (用 $T$ 表示) 满足 $T_i = \overline {S_{i+1}}$ ($1 \leq i < N$)，$T_N$ 为「墙」，且小球一定从右边离开系统。
对 $\left| S \right|$ 归纳证明。当 $\left| S \right| \leq 3$ 时容易验证。
设结论对 $\left| S \right| = N - 1$ 成立，考虑 $\left| S \right| = N$ 的情形。
根据 $S_2$ 是否为「墙」进行讨论：
$S_2$ 是「墙」。
分析如下表 (图例：>>> 表示向右运动的球，<<< 表示向左运动的球，| 表示「墙」，_ 表示「地」)。
(a) >>> _ | …… (b) | >>> | …… (c) | <<< _ …… (d) _ >>> _ ……
到上表中 (d) 步时，$T_1 = \overline {S_2} =$「地」，然后只考虑右边 $N - 1$ 个位置，不难发现它们恰好构成原问题的一个大小为 $N - 1$ 的子问题。
由归纳假设知，$T_2, T_3, \cdots, T_N$ 满足结论中所述的状态，且球从右边离开系统，加上前面 $T_1$ 也满足，这种情况结论成立。
$S_2$ 是「地」。
分析如下表：
(a) >>> _ _ …… (b) | >>> _ ……
同样，到 (b) 时就已经满足命题条件了，从而可以使用归纳假设，且 $T_1 = \overline {S_2} =$「墙」，从而这种情形结论也成立。
综上，由归纳原理知，原命题成立。
于是我们只需要快速模拟这个过程。
考虑每次小球移动，要么是将 $S_1$ 切换，要么整体平移一位。
对于整体反转 (取反) 的问题，其实可以不用真的去 "反转"，因为容易注意到，最终答案需要取反当且仅当进行了了奇数次平移。
而在平移的过程中，后面补充的字符一定是从「墙」开始，「墙」「地」「墙」「地」……交错出现 (ps: 因为我们已经取消了取反操作，所以这里会变成交替)。
于是接下来的任务就是计算出一共平移了多少次。
可以发现，对于情况 1 ($S_1$ 是「墙」)，则不会发生平移，而对于情况 2 ($S_1$ 是「地」)，则会发生平移。
那么只需要统计每个位置是否是「墙」即可，但是，同样的道理，我们取消了取反操作，应该判断奇数位是否是「墙」，偶数位是否为「地」。
对于 $K \geq N$ 的部分，不难发现后面的过程非常由规律：当 $N$ 为奇数时两步一平移，$N$ 为偶数时一步一平移，因此可以 $O \left( 1 \right)$ 计算。
综上，本题可以在 $O \left( N \right)$ 时间内解决。
#include <bits/stdc++.h>
const int N = 200054;
int n, K;
char s[N], t[N];
inline int get(int i) {return (i < n ? (int)s[i] : (i ^ n)) & 1;}
int main() {
int i, j, c;
scanf("%d%d%s", &n, &K, s);
for (i = 0; i < n && K; ++i) {
c = 1 + ((i ^ (int)s[i]) & 1);
if (K >= c) K -= c;
else break;
}
if (i == n && K) c = 1 + (n & 1), i += K / c, K %= c;
for (j = 0; j < n; ++j) t[j] = get(i + j);
for (*t ^= K, j = 0; j < n; ++j) t[j] = (i & 1 ? 65 + t[j] : 66 - t[j]);
return puts(t), 0;
}
坑1：在平移的时候注意输出的问题，不要数组越界了。可以使用类似队列的方法来实现，不过这里没必要。
坑2：$K \geq N$ 的时候整个串的周期为 $1$ ($2 \mid N$) 或 $2$ ($2 \nmid N$)，不过要注意串的形态变化是 "ρ" 形的。