题解：P4804 [CCC2016] 生命中的圆

fush · 2024-12-03 15:12:00 · 题解

我们先把环断成链。

转换题意：f_{i, j} = f_{i - 1, j - 1} \oplus f_{i - 1, j + 1}。

其中第一维是操作次数，\oplus 是异或。

由于 T 很大，而且大概率是不会有循环的。

那么我们先画图：

因为是异或，所以橙色点的状态我们并不用在意。

我们可以猜出结论：

证明可以看前面的题解。

那么这题就很简单了。

我们对 T 做二进制分解。
先处理出 1 位置的左右点，然后每次 +1 超出 n 的时候 -n 即可。
总时间复杂度：O(n \log T)。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
constexpr int N = 1e5 + 10;
#define int long long
int a[2][N], p;
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, t;char c;
    cin >> n >> t;
    for(int i = 1; i <= n; i++)cin >> c, a[1][i] = c - '0';
    for(int k = 0; k <= log2(t); k++){
        if((t >> k) & 1){
            int l = (((long long)1 << k) % n) + 1, r = ((n - l + 1) % n) + 1;
            for(int i = 1; i <= n; i++){
                a[p][i] = a[!p][l] ^ a[!p][r];
                l++, r++;
                if(l > n)l -= n;
                if(r > n)r -= n;
            }
            p = !p;
        }
    }
    for(int i = 1; i <= n; i++)
    cout << a[!p][i];
    return 0;
}