[AGC011D] Half Reflector 题解

题意：

有 \(N\) 个装置排成一排，组成一个系统。每个装置有两种状态 \(\mathtt{A}\) 和 \(\mathtt{B}\) 。具体地，假想有一个小球从最左侧进入这个系统，则两种状态的行为如下： 1. \(\mathtt{A}\) ：将球反弹回原方向。 2. \(\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)     _ >>> _     ……
```
1. 表明了之后 \(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;
}