自动搬运

查看原文

来自洛谷，原作者为

	szh_AK_all S挂分挂到被洛谷7级勾卡线|I can do all things

搬运于2025-08-24 22:56:46，当前版本为作者最后更新于2024-04-04 21:04:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题挺巧妙的。

分析

可以想想，对于一个数 $x$，$x+1$ 在什么情况下会对答案产生贡献？假设在二进制下 $x+1$ 在 $x$ 的基础上产生了 $k$ 个进位，也就是说 $x$ 在二进制下第 $0,1,\dots,k-1$ 位都由 $1$ 变为了 $0$，而第 $k$ 位则由 $0$ 变为了 $1$，而其他位则不变。那么，也就是说，当 $a_0⊕a_1⊕\dots a_k-1=a_k$ 时，会对答案产生贡献。

所以，可以枚举进位个数 $i$，若 $a_0⊕a_1⊕\dots a_{i-1}=a_i$，则答案会增加。那么会增加多少呢？用排列组合的思想，即在 $n$ 位下已经确定了 $i+1$ 位的数字个数，也就是对于第 $i+2,i+3,\dots n$ 位来说，可以有两种选择：该位为 $0$ 或者 $1$，所以这样的数字个数为 $2^{n-(i+1)}$。由于题目要求用二进制的形式输出答案，所以在用二进制存储答案的数组的第 $n-(i+1)$ 设为 $1$ 即可。

还需注意判断边界，即 $i=0$ 或 $i=n$ 的情况，若它们满足条件，则各自会产生 $1$ 的贡献，即答案的第 $0$ 位增加 $1$。由于第 $0$ 位可能会增加两个 $1$，所以要处理下进位。

Code

#include <bits/stdc++.h>
using namespace std;
int a[200005];
int k[200005];//记录答案
int qian[200005];

int qpow(int a, int b) {//没用，就当做防抄袭吧
	int ans = 1;
	while (b) {
		if (b & 1)
			ans *= a;
		a *= a;
		b /= 2;
	}
	return ans;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n + 1; i++) {
			scanf("%d", &a[i]);
			qian[i] = qian[i - 1] ^ a[i];
		}
		for (int i = 0; i < n; i++) {
			if (i == 0 && a[1] == 0)
				k[n - 1]++;
			else if (i != 0) {
				if (qian[i] == a[i + 1])
					k[n - (i + 1)]++;
			}
		}
		if (qian[n] == a[n + 1])
			k[0]++;
		for (int i = 0; i <= n; i++) {
			k[i + 1] += k[i] / 2;
			k[i] %= 2;
		}
		int tot = n;
		while (tot > 0 && k[tot] == 0)
			tot--;
		for (int i = tot; i >= 0; i--) {
			cout << k[i];
			k[i] = 0;//记得清空
		}
		cout << endl;
	}
}