luogu 阅读链接。
题目链接
我们先把环断成链。
转换题意:fi,j=fi−1,j−1⨁fi−1,j+1。
其中第一维是操作次数,⨁ 是异或。
由于 T 很大,而且大概率是不会有循环的。
那么我们先画图:

因为是异或,所以橙色点的状态我们并不用在意。
我们可以猜出结论:
fi,j=fi−2k,j−2k⨁fi−2k,j+2k,k∈N,2k≤i
数学归纳法证明如下:
- 当 k=0 时,这就是题目给出的条件。
- 当 k>0 时,假设结论对于 k−1 成立,则有:fi,j=fi−2k−1,j−2k−1⊕fi−2k−1,j+2k−1=(fi−2k,j−2k⊕fi−2k,j)⊕(fi−2k,j⊕fi−2k,j+2k)=fi−2k,j−2k⊕fi−2k,j+2k。
那么这题就很简单了。
我们对 T 做二进制分解。
先处理出 1 位置的左右点,然后每次 +1 超出 n 的时候 −n 即可。
总时间复杂度:O(nlogT)。
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; }
|