1. 题目

传送门=￣ω￣=

2. 题解

很显然是高斯消元解异或方程组。

因为 $\mod 2$意义下的加法等同于异或。

消元的时候记录一下最大访问到方程组的哪一行，这个就是 “到多少行确定答案”。

其他就没什么了。无解就是消着消着某一列都变成 0 了（除了之前已经访问过的行），则答案不唯一。

另外就是 $2000 \times 1000 ^ 2$的复杂度过不了，需要用 bitset 压位，复杂度降到 $\frac {2000 \times 1000 ^ 2} {32} = 6.25 \times 10 ^ 7$，就能过了。

代码：

#include <bits/stdc++.h>

#define NS (1005)
#define MS (2005)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, ans, res[NS];

bitset<NS> h[MS];

char str[NS];

void GS()
{
    for (int i = 1; i <= n; i += 1)
    {
        for (int j = i; j <= m; j += 1)
            if (h[j][i])
            {
                ans = max(ans, j);
                if (i != j) swap(h[i], h[j]);
                break;
            }
        if (!h[i][i]) puts("Cannot Determine"), exit(0);
        for (int j = i + 1; j <= m; j += 1)
            if (h[j][i]) h[j] ^= h[i];
    }
    for (int i = n; i >= 1; i -= 1)
    {
        res[i] = h[i][n + 1];
        for (int j = i + 1; j <= n; j += 1)
            if (h[i][j]) res[i] ^= res[j];
    }
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1; i <= m; i += 1)
    {
        scanf("%s", str + 1);
        for (int j = 1; j <= n; j += 1) if (str[j] == '1') h[i].set(j, 1);
        scanf("%s", str);
        if (str[0] == '1') h[i].set(n + 1, 1);
    }
    GS(), printf("%d\n", ans);
    for (int i = 1; i <= n; i += 1)
        if (res[i]) puts("?y7M#");
        else puts("Earth");
    return 0;
}