题目地址：洛谷：【P2447】[SDOI2010]外星千足虫 – 洛谷、BZOJ：Problem 1923. — [Sdoi2010]外星千足虫

题目描述

公元2089年6月4日，在经历了17年零3个月的漫长旅行后，“格纳格鲁一号”载人火箭返回舱终于安全着陆。此枚火箭由美国国家航空航天局（NASA）研制发射，行经火星、金星、土卫六、木卫二、谷神星、“张衡星”等23颗太阳系星球，并最终在小行星“杰森星”探寻到了地外生命。宇航员在“杰森星”地表岩层下45.70米位置发现一批珍贵的活体生命样本，并将其带回检测。在带回的活体样本中，最吸引人的当属这些来自外星的千足虫了。这些虫子身躯纤长，身体分为若干节。受到触碰时，会将身体卷曲成圆环形，间隔一段时间后才会复原活动。
有趣的还不止如此。研究人员发现，这些虫子的足并不像地球千足虫成对出现、总共偶数条——它们每节身体下方都有着不定数量的足，但足的总数一定是奇数条！虽然从外观难以区分二者，但通过统计足的数目，科学家们就能根据奇偶性判断出千足虫所属的星球。
作为J国派去NASA的秘密间谍，你希望参加这次研究活动以掌握进一步的情报，而NASA选拔的研究人员都是最优秀的科学家。于是NASA局长Charles Bolden出了一道难题来检测你的实力：
现在你面前摆有1…N编号的N只千足虫，你的任务是鉴定每只虫子所属的星球，但不允许亲自去数它们的足。Charles每次会在这N只千足虫中选定若干只放入“昆虫点足机”（the Insect Feet Counter, IFC）中，“点足机”会自动统计出其内所有昆虫足数之和。Charles会将这个和数mod 2的结果反馈给你，同时告诉你一开始放入机器中的是哪几只虫子。他的这种统计操作总共进行M次，而你应当尽早得出鉴定结果。
假如在第K次统计结束后，现有数据就足以确定每只虫子的身份，你就还应将这个K反馈给Charles，此时若K＜M，则表明那后M－K次统计并非必须的。
如果根据所有M次统计数据还是无法确定每只虫子身份，你也要跟Charles讲明：就目前数据会存在多个解。

输入输出格式

输入格式：
输入文件insect.in第一行是两个正整数N, M。
接下来M行，按顺序给出Charles这M次使用“点足机”的统计结果。每行包含一个“01”串和一个数字，用一个空格隔开。“01”串按位依次表示每只虫子是否被放入机器：如果第i个字符是“0”则代表编号为i的虫子未被放入，“1”则代表已被放入。后面跟的数字是统计的昆虫足数mod 2的结果。
由于NASA的实验机器精确无误，保证前后数据不会自相矛盾。即给定数据一定有解。

输出格式：
输出文件insect.out在给定数据存在唯一解时有N＋1行，第一行输出一个不超过M的正整数K，表明在第K次统计结束后就可以确定唯一解；接下来N行依次回答每只千足虫的身份，若是奇数条足则输出“?y7M#”（火星文），偶数条足输出“Earth”。如果输入数据存在多解，输出“Cannot Determine”。
所有输出均不含引号，输出时请注意大小写。

输入输出样例

输入样例#1：

3 5
011 1
110 1
101 0
111 1
010 1

输出样例#1：

4
Earth
?y7M#
Earth

输入样例#2：

5 7
01100 1
11000 1
10100 0
11100 1
00011 1
00000 0
11111 0

输出样例#2：

Cannot Determine

说明

对于每一个测试点，如果你的输出文件与答案文件完全相同，该测试点得满分；
否则，对于存在唯一解的测试点，如果你正确回答所有千足虫的身份，将得到50%的分数；
其他情况，该测试点得零分。
【数据规模和约定】
对于20%的数据，满足N＝M≤20；
对于40%的数据，满足N＝M≤500；
对于70%的数据，满足N≤500，M≤1,000；
对于100%的数据，满足N≤1,000，M≤2,000。

题解

本题实际上给了m组线性方程，要求在\bmod 2意义下的解。我们依然可以套用高斯消元。但是我们观察到数据范围不允许O(n^3)算法，由于方程在\bmod 2意义下，可以用bitset压起来算，这样高斯消元就变为O(n^3 / 64)算法了。
具体做法与高斯消元并无差别，只是替换成位运算了。
对于到第几个方程能够知道结果，只需要在找行主元的时候记下行主元的行号最大值。

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <algorithm>
#include <bitset>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool is01(char c) {
    return c == '0' || c == '1';
}

inline int read01() {
    char c;
    while(!is01(c = fgc()));
    return c - '0';
}

const int MAXN = 2005;

int n, m, t, ans;
bool fail;
std::bitset<MAXN> mat[MAXN];

inline void gauss() {
    for(int i = 1; i <= n; i++) {
        int r = i;
        for(int j = i; j <= m; j++) {
            if(mat[j][i]) {
                r = j;
                break;
            }
        }
        ans = std::max(ans, r);
        if(r != i) {
            std::swap(mat[i], mat[r]);
        }
        if(!mat[i][i]) {
            fail = true;
            return;
        }
        for(int j = 1; j <= m; j++) {
            if(j != i && mat[j][i]) {
                mat[j] ^= mat[i];
            }
        }
    }
} 

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n + 1; j++) {
            mat[i][j] = read01();
        }
    }
    gauss();
    if(fail) {
        puts("Cannot Determine");
    } else {
        printf("%d\n", ans);
        for(int i = 1; i <= n; i++) {
            printf(mat[i][n + 1] ? "?y7M#\n" : "Earth\n");
        }
    }
    return 0;
}