洛谷自建题目数据包

题目

题目描述

有一圈数 $a_1,a_2,a_3,\cdots,a_n$，定义一次操作为每个数变成原数圈中的自己与相邻的两个数这三个数的异或和，给出原数组和操作次数，计算出最后的结果数组。

输入格式

输入第一行包含两个正整数 $n$ 和 $k$，分别表示数的数目与操作次数。接下来一行 $n$ 个数，表示 $a_1,a_2,a_3,\cdots,a_n$。

输出格式

一行 $n$ 个数，表示结果数组中的 $a_1,a_2,a_3,\cdots,a_n$。

输入输出样例

输入样例

3 1
1 2 3

输出样例

0 0 0

说明/提示

对于 $30\%$ 的数据，满足 $n\times k\leq 10^8$。

对于 $100\%$ 的数据，满足 $1\leq n\leq 10^5,1\leq k\leq 10^9$。

题解

题意分析

给定一圈数 $a_1,a_2,a_3,\cdots,a_n$，进行 $k$ 次操作，每次操作会将 $a_i$ 变为 $a_{i-1}\oplus a_i\oplus a_{i+1}$，其中 $\oplus$ 表示异或。

为了便于区分，记 $b_i$ 表示若干次操作后的结果数组，$a_i$ 为初始时输入的数组，显然 $b_i$ 一定能表示为 $x\oplus y\oplus z$。

暂且不考虑首尾循环。

考虑第一次操作后，$b_i=a_{i-1}\oplus a_i\oplus a_{i+1}$。

那么对于 $a_i$，其被 $b_{i-1},b_i,b_{i+1}$ 包含。

因为在新的操作中，$b_i\leftarrow b_{i-1}\oplus b_i\oplus b_{i+1}$，则新的 $b_i$ 仍然包含 $a_i$。

第一次操作后，有 $b_i=a_{i-1}\oplus a_i\oplus a_{i+1}$。

第二次操作后，有：

\[\begin{aligned} b_i&=(a_{i-2}\oplus a_{i-1}\oplus a_i)\oplus(a_{i-1}\oplus a_i\oplus a_{i+1})\oplus (a_{i}\oplus a_{i+1}\oplus a_{i+2})\\ &=a_{i-2}\oplus a_i\oplus a_{i+2} \end{aligned}\]

第三次操作后，有：

\[\begin{aligned} b_i&=(a_{i-3}\oplus a_{i-1}\oplus a_{i+1})\oplus(a_{i-2}\oplus a_i\oplus a_{i+2})\oplus(a_{i-1}\oplus a_{i+1}\oplus a_{i+3})\\ &=a_{i-3}\oplus a_{i-2}\oplus a_i\oplus a_{i+2}\oplus a_{i+3} \end{aligned}\]

第四次操作后，有：

\[\begin{aligned} b_i&=(a_{i-4}\oplus a_{i-3}\oplus a_{i-1}\oplus a_{i+1}\oplus a_{i+2})\oplus(a_{i-3}\oplus a_{i-2}\oplus a_i\oplus a_{i+2}\oplus a_{i+3})\oplus(a_{i-2}\oplus a_{i-1}\oplus a_{i+1}\oplus a_{i+3}\oplus a_{i+4})\\ &=a_{i-2}\oplus a_i\oplus a_{i+2}\\ \end{aligned}\]

因此可以得出规律：操作 $2^k$ 次等价于 $a_i\leftarrow a_{i-k}\oplus a_i\oplus a_{i+k}$。

那么就可以 $\mathcal O(n\log k)$ 写出代码。

AC 代码

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1e5,K=1e9;
int n,k;
ll a[N+1],tmp[N+1];
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/
	
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",a+i);
	}
	for(int pl=1;k;pl<<=1,k>>=1){
		if(k&1){
			for(int i=1;i<=n;i++){
				tmp[i]=a[i];
			}
			for(int l=(-pl%n+n)%n+1,r=pl%n+1,j=1;j<=n;j++){
				a[j]=tmp[l++]^a[j]^tmp[r++];
				if(l>n){
					l=1;
				} 
				if(r>n){
					r=1;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}putchar(10);
	
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}

题解：XOR 操作

题目见正文

题目