Blackops

初心易得，始终难守

0%

Lonlife 1169 既然有B那还得有C（高斯消元）

发表于 更新于 分类于 ， ，

1169 - 既然有B那还得有C

Time Limit：2s Memory Limit：128MByte

Submissions：83Solved：28

DESCRIPTION

输入n个长度为n的01向量，

问有多少组解，取出解中的向量，将他们异或起来，恰好等于解本身。

比如n = 3
1 0 1
0 1 1
1 1 0

如果我们取出第1个和第2个向量异或起来可以得到
1 1 0

恰好等于这个解本身，其中1表示取这个向量，0表示不取这个向量。

显而易见，空集一定是一个解，因为异或起来都是0。

INPUT

第一行一个整数n
接下来n行，第i行n个0或1表示第i个向量。

(1 <= n <= 300)

OUTPUT

一行一个整数表示解的个数。

SAMPLE INPUT

3
1 0 1
0 1 1
1 1 0

SAMPLE OUTPUT

2

SOLUTION

“玲珑杯”ACM比赛 Round #22

题目连接：Lonlife 1169
中文题意就不说了，由于智商硬伤，比赛的时候完全没想出来，第一个提交，但是到最后也没有过……
实际上异或其实就是模$2$的加法，那么肯定先用加法的思想做，如果将给定的向量视为行向量，从上到下一次放置，此时就构成了一个$n*n$的矩阵，记为$A$，那么题意显然就是叫我们求$A \times X=X$（暂时这么写）这个矩阵方程解的个数，那么如何构造$X$呢，显然如果是用行向量构成$A$的话实际上要左乘（比赛的时候一直在用行向量+右乘构造，当然是构造不了的）一个$X$使得某几行的所有维向量得以相乘并相加。也就是求$X \times A=X$的解的个数，然后我们用乘法分配律或者直接两边同时左乘一个$X^{-1}$，得到$A-E=\vec{0}$，由于是题目是异或，因此对角线减$1$就相当于对角线异或$1$。最后高斯消元求秩记为$q$，答案就是$2^{q}$，这里还学到一个不用大数模板就可以输出$2^{1023}$以下的大数的技巧
拿样例举个例子：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 310;
int Mat[N][N];

int Gaussian(int ne, int nv)
{
    int ce, cv;
    for (ce = 1, cv = 1; ce <= ne && cv <= nv; ++ce, ++cv)
    {
        int te = ce;
        for (int i = ce + 1; i <= ne; ++i)
            if (Mat[i][cv])
                te = i;
        if (te != ce)
        {
            for (int j = cv; j <= nv + 1; ++j)
                swap(Mat[ce][j], Mat[te][j]);
        }
        if (!Mat[ce][cv])
        {
            --ce;
            continue;
        }
        for (int i = ce + 1; i <= ne; ++i)
        {
            if (Mat[i][cv])
            {
                for (int j = cv; j <= nv + 1; ++j)
                    Mat[i][j] ^= Mat[ce][j];
            }
        }
    }
    return ne - ce + 1;
}
int main(void)
{
    int n, i, j;
    while (~scanf("%d", &n))
    {
        for (i = 1; i <= n; ++i)
            for (j = 1; j <= n; ++j)
                scanf("%d", &Mat[i][j]);
        for (i = 1; i <= n; ++i)
            Mat[i][i] ^= 1;
        int fr = Gaussian(n, n);
        cout << fixed << setprecision(0) << pow(2, fr) << endl;
    }
    return 0;
}