P2447 [SDOI2010]外星千足虫 (高斯消元)

题目

P2447 [SDOI2010]外星千足虫

解析

sol写到自闭，用文字描述描述了半个小时没描述出来，果然还是要好好学语文
用高斯消元求解异或方程组。
因为

• (奇数bigoplus奇数=偶数)
• (偶数bigoplus偶数=偶数)
• (奇数bigoplus偶数=奇数)

(0)为偶数，(1)为奇数，

• ((奇数+奇数)mod 2=0)
• ((偶数+偶数)mod 2=0)
• ((奇数+偶数)mod 2=1)

若把第一个里面的奇偶数分别换成(1)和(0)，则对于((x_1+x_2)bmod 2)的操作，可以看做异或操作((x_1bigoplus x_2))。

易证，((x_1+x_2+x_3+···+x_n)mod 2 = x_1bigoplus x_2bigoplus x_3 bigoplus ···bigoplus x_n)。

对于主元所在的列，我们只让主元行上的数为(1)，其余的为(0)，于是我们让每一行与当前主元行比较，若某一行的这个数为(1)，就让这一行异或主元行。
因为我们之前处理当前主元行以上的内容时，把除了当时主元行上的所有当时主元所在列上的数都异或成了(0)，所以我们当前主元行主元之前的数都为0，根据异或的性质，发现当前主元行前面的(0)对之前处理的行没有影响，这样更新到最后，我们会得到一个单位矩阵，
其实手动一模拟就出来了。。
如[begin{bmatrix} 0&1&1&mid&11&0&1&mid&0&0&1&mid&1 end{bmatrix} tobegin{bmatrix} 1&0&1&mid&0&1&1&mid&1&0&1&mid&1 end{bmatrix} tobegin{bmatrix} 1&0&0&mid&1&1&0&mid&0&0&1&mid&1 end{bmatrix}]
于是就得到了答案。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2010; 
bitset<N> a[N];
char s[N];
int n,m,ans;

template<class T>inline void read(T &x) {
    x = 0;int f = 0;char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch -'0',ch = getchar();
    x = f ? -x : x;
    return ;
}


void Gauss() {
    for (int i = 1; i <= n; ++i) {
        int k = i;
        while (!a[k][i] && k <= m) k++;
        if (k == m + 1) {
            ans = -1;
            return;
        }
        ans = max(ans,k);
        if (k != i) swap(a[k],a[i]);
        for (int j = 1; j <= m; ++j)
            if (j != i && a[j][i]) a[j] ^= a[i];
    }
    return;
}

int main() {
    read(n),read(m);
    for (int i = 1,x; i <= m; ++i) {
        scanf("%s",s);
        for (int j = 0; j < n; ++j) a[i][j + 1] = s[j] - '0';
        read(x);
        a[i][n + 1] = x;
    }
    Gauss();
    if (ans == -1) printf("Cannot Determinen");
    else {
        printf("%dn",ans);
        for (int i = 1; i <= n; ++i)    
            printf(a[i][n + 1] == 1 ? "?y7M#n" : "Earthn");
    }
    return 0;
}