洛谷-P4804题解

luogu 阅读链接。
题目链接
我们先把环断成链。

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

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

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

那么我们先画图：

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

我们可以猜出结论：

$$f_{i, j} = f_{i - 2^k, j - 2 ^k} \bigoplus f_{i - 2 ^k, j + 2 ^k}, k \in \mathbb{N}, 2 ^ k \le i$$

数学归纳法证明如下：

1. 当 $k=0$ 时，这就是题目给出的条件。
2. 当 $k>0$ 时，假设结论对于 $k-1$ 成立，则有：$f_{i,j}=f_{i-2^{k-1},j-2^{k-1}}\oplus f_{i-2^{k-1},j+2^{k-1}}=(f_{i-2^{k},j-2^{k}}\oplus f_{i-2^{k},j})\oplus(f_{i-2^{k},j}\oplus f_{i-2^{k},j+2^k})=f_{i-2^k,j-2^k}\oplus f_{i-2^k,j+2^k}$。

那么这题就很简单了。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#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;
}