算法分析
不难看出这相当于是解\(n\)元一次异或方程组，类比\(n\)元一次方程组的解法，不难想到使用高斯消元。
发现数据范围比较大，\(n^3\)是肯定过不去的，因此想到01矩阵用bitset存储，用bitset Xor运算实现对其他方程的转化，时间复杂度\(\frac{n^3}{32}\)可以通过。
求最早确定结果的时间，只需要再记录一个\(id[i]\)表示当前第\(i\)个方程是输入的第\(id[i]\)个方程，对每一次使用的方程的\(id\)取最大值即可。
代码实现
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
#define maxm 2005
template<typename Tp>
void read(Tp &x){
x=0;int f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-'){f=-1;}c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;
}
int n,m;
bitset<maxn>a[maxm];
int id[maxm],ans;
int main(){
read(n);read(m);int x;
for(int i=1;i<=m;i++){
for(int j=1;j<=n+1;j++){
scanf("%1d",&x);
a[i][j]=x;
}
id[i]=i;
}
for(int i=1;i<=n;i++){
int p=i;
while(!a[p][i]&&p<=m)p++;
ans=max(ans,id[p]);
if(p==m+1){
puts("Cannot Determine");
return 0;
}
if(i!=p){
swap(a[i],a[p]);swap(id[i],id[p]);
}
for(int j=1;j<=m;j++){
if(i==j)continue;
if(a[j][i])a[j]=a[j]^a[i];
}
}
printf("%d\n",ans);
for(int i=1;i<=n;i++){
puts(a[i][n+1]?"?y7M#":"Earth");
}
return 0;
}