Description：

$n$ 个变量，给出一些变量的和是奇数还是偶数，问能否确定每个变量的奇偶性。

$1\leqslant n\leqslant 10^3$

Solution：

本质上是一个高斯消元解异或方程组削成上三角矩阵再回代解出每个的值就可以了，无解就是消完后 $a[i][i]=0$ ，但是本题还要求用最少的前几个能够确定所有的值，这个只要在消元的时候找一个最小的 $j$ 满足 $a[j][i]=1$ 然后用 $j$ 更新答案即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<bitset>

#include<cctype>

#include<cstring>

using namespace std;

int getc()

{

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	return c - '0';

}

int n,m;

#define MAXN 1010

#define MAXM 2010

bitset<MAXN> a[MAXM];

int b[MAXM];

int res[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

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

	{

		for(int j = 1;j <= n;++j)

		{

			a[i][j] = getc();

		}

		b[i] = getc();

	}

	int ans = 0;

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

	{

		for(int j = i;j <= m;++j)

		{

			if(a[j][i])

			{

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

				ans = max(ans,j);

				break;

			}

		}

		for(int j = i + 1;j <= m;++j)

		{

			if(a[j][i])

			{

				a[j] ^= a[i];

				b[j] ^= b[i];

			}

		}

	}

	for(int i = n;i >= 1;--i)

	{

		res[i] = b[i] ^ a[i][i] ^ 1;

		if(a[i][i] == 0)

		{

			puts("Cannot Determine");

			return 0;

		}

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

		{

			if(a[j][i])

			{

				b[j] ^= res[i];

			}

		}

	}

	cout << ans << endl;

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

	{

		if(res[i])puts("?y7M#");

		else puts("Earth");

	}

	return 0;

}