题意

题目链接

Sol

异或高斯消元的板子题。

bitset优化一下，复杂度\(O(\frac{nm}{32})\)

找最优解可以考虑高斯消元的过程，因为异或的特殊性质，每次向下找的时候找到第一个1然后交换就行，这样显然是最优的

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2001;

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

int N, M;

bitset<MAXN> b[MAXN];

void Gauss() {

	int ans = 0;

	for(int i = 1; i <= N; i++) {

		int j = i;

		while(!b[j][i] && j < M + 1)

			j++;

		if(j == M + 1) {puts("Cannot Determine"); return ;}

		ans = max(ans, j);

		swap(b[i], b[j]);

		for(int j = 1; j <= M; j++) {

			if(i == j || !b[j][i]) continue;

			b[j] ^= b[i];

		}

	}

	printf("%d\n", ans);

	for(int i = 1; i <= N; i++)

		puts(!b[i][N + 1] ? "Earth" : "?y7M#");

}

int main() {

	N = read(); M = read();

	for(int i = 1; i <= M; i++) {

		string s; cin >> s;

		b[i][N + 1] = read();

		for(int j = 1; j <= N; j++) b[i][j] = (s[j - 1] == '0' ? 0 : 1);

	}

	Gauss();

	return 0;

}