抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

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

转换题意:fi,j=fi1,j1fi1,j+1f_{i, j} = f_{i - 1, j - 1} \bigoplus f_{i - 1, j + 1}

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

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

那么我们先画图:

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

我们可以猜出结论:

fi,j=fi2k,j2kfi2k,j+2k,kN,2kif_{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=0k=0 时,这就是题目给出的条件。
  2. k>0k>0 时,假设结论对于 k1k-1 成立,则有:fi,j=fi2k1,j2k1fi2k1,j+2k1=(fi2k,j2kfi2k,j)(fi2k,jfi2k,j+2k)=fi2k,j2kfi2k,j+2kf_{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}

那么这题就很简单了。

我们对 TT 做二进制分解。
先处理出 11 位置的左右点,然后每次 +1+1 超出 nn 的时候 n-n 即可。
总时间复杂度:O(nlogT)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;
}