P8279 题解

题目传送

题意

给定一个正整数数组的前缀异或和和后缀异或和数组，在这两个异或和数组里共有原数组长度个数是未知数，求出任意一组可能的原数组。

思路

令前缀异或和数组的每个数为 $p_i$，代表的是 $a_1\sim a_i$ 所有数的异或和（即 $p_i=a_1\oplus a_2\oplus\dots\oplus a_i$）。后缀异或和数组的每个数为 $s_j$， 代表的是 $a_j\sim a_n$ 所有数的异或和（即 $s_j=a_j\oplus a_{j+1}\oplus\dots\oplus a_n$）。那么如果让 $j=i+1$（$i\geq1,j\leq n$），$p_i \oplus s_j$ 的结果不就是 $a_1\sim a_n$ 所有数的异或和了吗？有人可能问：如果 $-1$ 把这些组合的一边遮住了，怎么办？例如：

p  |3    34 367 -1
s  |3178 -1 -1  -1

我们可以将两个异或和数组的首尾视作有 $0$，这样，就相当于增多了两个组合，分别是：$p_0,s_1$ 和 $p_n,s_{n+1}$（其实就是 $0$ 和 $a_1\oplus a_2\oplus\dots\oplus a_n$）。

p  |0  3    34 367 -1  0
s  |0  3178 -1 -1  -1  0

接着可以从题目中发现一个重要的关键点，那就是：

现在 Tommy 一共将 $p$ 和 $s$ 的 $n$ 个元素换成 $-1$。

这个有什么用呢？增加了两个组合后 $i,j$ 的取值范围就变成了 $i \in [0,n],j \in [1,n+1]$，组合数正好比原数组长度多 $1$。也就是说，无论如何覆盖，都可以求出 $a_1\sim a_n$ 所有数的异或和。知道这个后，就可以将一些组合的未知数给求出来。但是，如果一组中两个数都是未知，那怎么办呢？

假设！我们就可以把推不出的组合 $(p_i,s_{i+1})$ 的 $p_i$ 全部假设成一个 $< 2^{60}$ 的数。显然可以发现假设的 $p_i$ 一定能使得 $a_i=p_i \oplus p_{i-1}$ 合法。这样子就把 $a_i$ 的一个解算出来了。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n;//数组长度
long long p[100005],s[100005];//前、后缀异或和数组
long long total;//异或总和 
int main(){
	ios::sync_with_stdio(false);
	cin.tie();cout.tie();//加速
	int t;//数据组数
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;++i) cin>>p[i];
		for(int i=1;i<=n;++i) cin>>s[i];
		for(int i=0;i<=n;++i){
			if(p[i]!=-1&&s[i+1]!=-1) {//当找到一个完整的组合时，算出异或总和
				total=p[i]^s[i+1];
				break;
			}
		}
		for(int i=0;i<=n;++i){
			if(p[i]==-1&&s[i+1]!=-1) {//如果有一个未知数
				p[i]=s[i+1]^total;//求出未知数
			}
			else if(p[i]!=-1&&s[i+1]==-1) {
				s[i+1]=p[i]^total;
			}
		}
		for(int i=1;i<=n;++i){
			if(p[i]==-1) p[i]=1;//推不出来的用1代替
		}
		for(int i=1;i<=n;++i){
			cout<<(p[i]^p[i-1])<<" ";//求出原数组
		}
		cout<<"\n";
	}
	return 0;
}

2022/7/15 修改
2025/10/10 第二次修改