自动搬运

查看原文

来自洛谷，原作者为

	steambird Partially AFO || Seabird Starch Gunnhildr || 风生水起，无限可能

搬运于2025-08-24 22:32:15，当前版本为作者最后更新于2024-08-19 11:47:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

这道题缺少 Special Judge，害得我调了一上午然后发现是没有 Special Judge 的问题

思路

首先可以以 $O(n)$ 的复杂度模拟这个过程，输入中已经提供了每次加入的数（从第 $n+1$ 个数到第 $2n$ 个数）。观察这个过程，可以发现每次加入一个数 $x$ 时，对于这个数加入之前的序列 $\{a_1,a_2,...,a_n\}$，开关 $\{k_1,k_2,...,k_n\}$ 有：

$$(\sum_{i=1}^n {a_i \times k_i}) \equiv x \pmod 2$$

相当于对于每个 $a_i=1$ 的位置，对应的 $k_i$ 之和满足相加后除以 $2$ 的余数为 $x$。由此可以列出同余方程组，想到利用类似高斯消元的方式解决本题。

然而，多个变量的同余方程组求解并不容易。考虑到相加后对 $2$ 取余等价于做异或运算，问题转变为求解形如下面这样的异或方程组：

$$\begin{cases} k_1 \operatorname{xor} k_2 \operatorname{xor} k_3 = 1 \\ k_1 \operatorname{xor} k_5 \operatorname{xor} k_6 = 0 \\ \dots \end{cases} $$

考虑如何对这样的方程组进行消元。类比高斯消元，处理到第 $i$ 行时我们希望第 $i+1$ 行到第 $n$ 行方程均不涉及 $k_i$。

显然，等号两边同时异或上某个数时，等式仍然成立。因此，对于某个我们希望消去 $k_i$ 的方程，我们可以在其等号两边同时异或上第 $i$ 个方程左侧的式子。例如，对上面的方程组，消去第 $2$ 个方程的 $k_1$ 时可以这样计算：

$$\begin{aligned} k_1 \operatorname{xor} k_5 \operatorname{xor} k_6 &= 0 \\ k_1 \operatorname{xor} k_5 \operatorname{xor} k_6 \operatorname{xor} k_1 \operatorname{xor} k_2 \operatorname{xor} k_3 &= 0 \operatorname{xor} k_1 \operatorname{xor} k_2 \operatorname{xor} k_3 \\ k_5 \operatorname{xor} k_6 \operatorname{xor} k_2 \operatorname{xor} k_3 &= 0 \operatorname{xor} 1 \end{aligned} $$

代码实现时，这可以转化为将系数和等号右侧的值都与某行异或。最后统计答案时的方法和高斯消元一致。

注意不要把高斯消元写错。

代码

#include <bits/stdc++.h>
using namespace std;

inline void train() {
	   ios::sync_with_stdio(false);
	   cin.tie(0);
	   cout.tie(0);
}

#ifndef ONLINE_JUDGE
#define ONLINE_JUDGE
#endif

constexpr int N = 800, NT = 1504;

int n, mat[N][N], got[N];
bitset<N> gen;
bool vis[N];

inline void swap_mat(int a, int b) {
	if (a == b) return;
	for (int i = 1; i <= n+1; i++) {
		int tmp = mat[a][i];
		mat[a][i] = mat[b][i];
		mat[b][i] = tmp;
	}
}

inline void xor_mat(int target, int source) {
	if (target == source) return;
	for (int i = 1; i <= n+1; i++) {
		mat[target][i] ^= mat[source][i];
	}
}

int main() {

	train();
	
	cin>>n;
	for (int i = 0; i < n; i++) {
		int x;
		cin>>x;
		if (x) gen.set(i);
	}
	for (int i = 0; i < n; i++) {
		int x;
		cin>>x;
		
		for (int j = n-1, mpos = 1; j >= 0; j--, mpos++) {
			if (gen.test(j)) mat[i+1][mpos] = 1;
		}
		if (x) mat[i+1][n+1] = 1;
		
		gen >>= 1;
		if (x) gen.set(n-1);		// Top position
	}
	for (int i = 1; i <= n; i++) {
		int foundrow = -1;
		for (int j = 1; j <= n; j++) {
			if (mat[j][i] && (!vis[j])) {
				foundrow = j;
				break;
			}
		}
		if (foundrow < 0) continue;
		swap_mat(i, foundrow);
		vis[i] = true;
		for (int j = 1; j <= n; j++) {
			if (vis[j]) continue;
			if (mat[j][i]) {
				xor_mat(j, i);
			}
		}
	}
	for (int i = n; i >= 1; i--) {
		int right = mat[i][n+1];
		for (int j = i+1; j <= n; j++) {
			right ^= got[j] & mat[i][j];
		}
		if (mat[i][i] == 0) {
			if (right == 1) {
				cout<<"-1"<<endl;
				return 0;
			} else {
//				got[i] = 1;							// 加不加都可以，没有 spj 时分数不同 
			}
		} else {
			got[i] = right;
		}
	}
	for (int i = 1; i <= n; i++) cout<<got[i]<<' ';
	cout<<endl;

	return 0;
}