题意
现在你面前摆有 \(1\ldots N\) 编号的 \(N\) 只千足虫，你的任务是鉴定每只虫子所属的星球，但不允许亲自去数它们的足。
Charles 每次会在这 \(N\) 只千足虫中选定若干只放入“昆虫点足机”（the Insect Feet Counter, IFC）中，“点足机”会自动统计出其内所有昆虫足数之和。Charles 会将这个和数 \(\bmod\) \(2\) 的结果反馈给你，同时告诉你一开始放入机器中的是哪几只虫子。
他的这种统计操作总共进行 \(M\) 次，而你应当尽早得出鉴定结果。
假如在第 \(K\) 次统计结束后，现有数据就足以确定每只虫子的身份，你就还应将这个 \(K\) 反馈给 Charles，此时若 \(K<M\)，则表明那后 \(M-K\) 次统计并非必须的。
如果根据所有 \(M\) 次统计数据还是无法确定每只虫子身份，你也要跟 Charles 讲明：就目前数据会存在多个解。
\(1\leq N\leq 10^3\)，\(1\leq M\leq 2\times 10^3\)
Solution
本题要求求解
\[\begin{cases} a_1 x_1 \ \text{xor} \ a_2 x_2 \dots \text{xor} \ a_n x_n = a_{n+1} \\ b_1 x_1 \ \text{xor} \ b_2 x_2 \dots \text{xor} \ b_n x_n = b_{n+1} \\ \dots \\ c_1 x_1 \ \text{xor} \ c_2 x_2 \dots \text{xor} \ c_n x_n = c_{n+1} \\ \end{cases}\]显然这是一个类似于高斯消元的方程组，可以考虑使用高斯消元解决，只不过由原来的加减消元转化为异或消元即可。
对于无解判断，跟原高斯消元一致，只需要判断是否存在新的 \(x_i\) 来进行消元。
而考虑到需要多少组统计数据，我们发现在高斯消元的时候会尽量的选择可供消元的 \(n\) 的方程，只需要记录下这些方程原来是第几组， 然后统计最大值即可。
不幸的是，我们发现整个过程为 \(O(n^3)\) ，我们的算法不能通过。
考虑使用 bitset ，其具有更加优秀的异或时间复杂度，或者是比较原始的说，用二进制数来表示出这些01位，然后对这些二进制进行异或运算，可以有效降低时间复杂度。
幸运的是，这个题的数据很水，我们不需要 bitset 也可以通过。
Code
点击查看代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3 + 50;
inline int read() {
register int w = 0, f = 1;
register char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
w = w * 10 + c - '0';
c = getchar();
}
return w * f;
}
int n, m;
int a[N << 1][N];
int main() {
n = read(), m = read();
for (register int i = 1; i <= m; ++i) {
for (register int j = 1; j <= n; ++j)
scanf("%1d", &a[i][j]);
scanf("%d", &a[i][n + 1]);
a[i][0] = i;
}
for (register int i = 1; i <= n; ++i) {
register bool flag = false;
for (register int j = i; j <= m; ++j)
if (a[j][i]) {
swap(a[i], a[j]);
flag = true;
break;
}
if (!flag) {
puts("Cannot Determine");
return 0;
}
for (register int j = i + 1; j <= m; ++j)
if (a[j][i])
for (register int k = i; k <= n + 1; ++k)
a[j][k] ^= a[i][k];
}
for (register int i = n ; i >= 1; --i)
for (register int j = i - 1; j >= 1; --j)
if (a[j][i])
for (register int k = i; k <= n + 1; ++k)
a[j][k] ^= a[i][k];
register int ans = a[1][0];
for (register int i = 2; i <= n; ++i)
ans = max(ans, a[i][0]);
printf("%d\n", ans);
for (register int i = 1; i <= n; ++i)
puts(a[i][n + 1] == 0 ? "Earth" : "?y7M#");
return 0;
}