GYM103743H Super Gray Pony - 思维 -

题目链接：https://codeforces.com/gym/103743/problem/H

这应该是近期做出来的最难的题之一了……想了一个多小时
首先，如何由 \(S\) 求得 $a^{(n)}(S) $ ？
考虑 \(S\) 的每一位 0/1
如果第一位是 1，那么相当于就知道了剩下的数字在 \(rev(a^{(n-1)})\) （即在右侧）中，此时如果第二位为 0，由于 \(a^{(n-1)}\) 是反过来的，因此相当于是在 \(rev\) 的左侧，即 \(a^{(n-1)}\) 的右侧，因此对应的格雷码是 1.
找规律可以发现：对于一个 01 串，求格雷码的方法就是，如果出现一个 1，那么 标记为 1，继续接下来，如果是 0 记 1，否则记 0（如果标记为 0 的话就不变了），如果当前记的是 1，那么标记反转，以此类推
我们发现这本质上就是异或，如果 \(s_i\) 的格雷码是 \(t_i\)，那么根据上面的算法我们就可以得到 \(t_i=(t_1\oplus .. \oplus t_{i-1}) \oplus s_i\)，同理写出 \(t_{i-1}=(t_1\oplus .. \oplus t_{i-2}) \oplus s_{i-1}\)，两式异或得 \(t_i=s_i\oplus s_{i-1}\)
考虑多次重复这个过程，考虑 \(t_i\) 的格雷码 \(p_i\)，那么同理有 \(p_i=t_i\oplus t_{i-1}=s_i\oplus s_{i-2}\)
因此，我们得到算 \(k\) 阶格雷码的方法：\(a^{(k)}_i=s_i\oplus s_{i-k}\)
这里出现了一个问题：\(a^{(k)}\) 的 \(1..k\) 项没了，通过打表/数学归纳法可以得到当 \(k\) 是 2 的幂次时，前面的 \(k\) 项是不变的
因此我们可以将 \(k\) 拆成 2 的幂次之和，然后用我们的做法求出 \(k\) 阶格雷码
代码相当好写

#include <bits/stdc++.h>
#define mpr make_pair

typedef long long ll;

using namespace std;

const int inf = 1e9, maxn = 3e6 + 5;

int n,k;
char s[maxn];
int a[maxn];

signed main(){
    scanf("%d%d",&n,&k);
    scanf("%s",s + 1);
    for(int i=1;i<=n;i++)a[i] = s[i] - '0';

    for(int i=0;i<=30;i++)
        if(k & (1 << i)){
            int qw = (1 << i);
            for(int j=n;j>=qw+1;j--)
                a[j] ^= a[j-qw];
        }
    for(int i=1;i<=n;i++)
        printf("%d",a[i]);
    puts("");

    return 0;
}