[AGC011D] Half Reflector 题解

题意：

有 $N$ 个装置排成一排，组成一个系统。每个装置有两种状态 $\mathtt{A}$ 和 $\mathtt{B}$ 。具体地，假想有一个小球从最左侧进入这个系统，则两种状态的行为如下：

$\mathtt{A}$ ：将球反弹回原方向。

$\mathtt{B}$ ：让球通过，不改变方向。

当然，每当一个小球经过一个装置后，无论是以 $\mathtt{A}$ 状态还是 $\mathtt{B}$ 状态经过，装置都将改变原来的状态 (即 $\mathtt{A}$ 变 $\mathtt{B}$ ，$\mathtt{B}$ 变 $\mathtt{A}$ )。现在给定初始情况下所有装置的状态，求 $K$ 个小球经过后装置的状态。

输入格式：

第一行包含两个正整数 $N,K\left(N \leq 2 \times 10^5,~K \leq 10^9\right)$，分别表示装置的个数和经过的小球数。

第二行包含一个由 $\mathtt{A}$ 和 $\mathtt{B}$ 构成的字符串 $S(|S|=N)$，其中第 $i$ 个字符表示左起第 $i$ 个装置的状态。

输出格式：

输出一行，包含一个字符串 $S_K$，表示 $K$ 次小球经过后状态的状态，具体格式同输入。

可以发现，对于很多情况，小球会来回弹来弹去，以至于对原串进行了类似于翻转的操作

不妨对 $S_1$ 的情况进行讨论，方便起见，称 $\mathtt{A}$ 为「墙」，$\mathtt{B}$ 为「地」。

若 $S_1$ 为「墙」，此时小球弹回，$S_1$ 变为地。
若 $S_1$ 为「地」，通过对较小情况的尝试，不难发现一个结论：记 $\bar{x}$ 为与 $x$ 相反的状态，

则当 $S_1$ 为「地」时，$S$ 的新状态 $T$ 有 $T_i=\overline{S_{i+1}}(i<n)$ ， $T_n$ 为「墙」，且小球一定从右边离开系统。

尝试证明这个结论：

对 $|S|$ 归纳证明。显然当 $|S|\le 3$ 时成立。于是设 $|S|$ 在 $n-1$ 处成立，尝试验证 $|S|=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$ 亦均满足结论。
若 $S_2$ 为「地」
```
(a) >>> _     _     ……
(b)     | >>> _     ……
```
同样的，(b) 显然已经满足命题条件了，从而可以用归纳假设，且 $T_1=\overline{S_2}=$ 「墙」，从而该情况成立。

综上，由归纳原理知，原命题成立。$\square$

于是我们要快速模拟这个过程。考虑到每次小球移动，要么是将 $S_1$ 翻转，或者整体平移一位

显然这个翻转是不用进行实际操作的，当且仅当进行了奇数次平移最终答案才会翻转。

而在平移的过程中，后面补充的字符依次为「墙」「地」「墙」…（交替出现）

因此我们考虑如何计算平移的次数。

对于 $S_1$ 是「墙」，则不会发生平移，而 $S_1$ 是「地」时会发生平移

那么只需要统计每个位置是否是「墙」即可。

注意，由于我们取消了取反操作，所以应该判断奇数位是否为「墙」，偶数位是否为「地」

特别地，对于 $k\ge n$ 的部分，不难发现，当 $n$ 为奇数时两步一平移，否则一步一平移，可以 $\mathcal{O}(1)$ 计算

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

int n,k; char s[N],t[N];
int get(int x) { return (x < n ? (int)s[x] : (x ^ n)) & 1; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int i, j, c; cin >> 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[0] ^= k, j = 0; j < n; j++) t[j] = (i & 1 ? 'A' + t[j] : 'A' + 1 - t[j]);
    cout << t << '\n';
    return 0;
}