概念

高斯消元是线性代数中的一个算法
可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。

线性代数基础知识

  • 一个矩阵A中线性无关的行/列的极大数目,记为(r(A))
  • 一个矩阵中行和列的秩相等
  • 对于矩阵A,B,$r(AB) \leq min(r(A),r(B))$
  • 高斯消元行阶梯形矩阵,中非0的行数即矩阵的秩

线性方程组

  • 线性方程组$Ax = b$,可以转化为矩阵$(A,b)$
  • 若对于所有的$b = 0$,则称之为齐次线性方程组,反之为非齐次线性方程组
  • 非齐次线性方程组有解的条件为$r(A) \leq n$,$r(A) = n$时有唯一解(n为未知数个数)

线性无关组

  • 若一组向量不能被组内的其他向量线性表示,则称之为线性无关组
  • 高斯消元的结果是极大线性无关组

逆矩阵

  • 给定一个n阶方阵A,若存在一n阶方阵B,使得AB = BA = $I_n$(单位矩阵)
    则称A是可逆的,B是A的逆矩阵,记为$A^{-1}$
  • n阶方阵A可逆的充要条件为$r(A) = n$(满秩)
  • $(AB)^{-1} = A^{-1}B^{-1}$
  • $(A^T)^{-1} = (A^{-1})^T$
  • $det(A^{-1}) = \frac{1}{det(A)}$ (det为行列式)
  • 高斯消元求逆,即将方阵变换为单位矩阵
    对另一个单位矩阵做同样变换,即为逆矩阵

高斯消元

高斯消元会产生一个行阶梯形矩阵
然后回带可以求出所表示线性方程组的解

复杂度$O(n^3)$

模板

浮点数

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
const double eps = 1e-9;
const int maxn = 1010;
double a[maxn][maxn],ans[maxn];
bool freeX[maxn];

bool Zero(double x)
{
return fabs(x) < eps;
}

void getAns(int n,int m,int r)
{
for(int i = r-1;i >= 0; --i)
for(int j = 0;j < m; ++j)
{
if(Zero(a[i][j])) continue;
ans[j] = a[i][m];
for(int k = j+1; k < m; ++k)
ans[j] -= a[i][k]*ans[k];
ans[j] /= a[i][j];
break;
}
}

int gauss(int n,int m)
{
for(int i=0;i<m;++i) freeX[i] = 0;
int r = 0,c = 0;
for(;r < n && c < m; ++r,++c)
{
int maxR = r;
for(int i = r+1;i < n; ++i)
if(fabs(a[i][c]) > fabs(a[maxR][c])) maxR = i;
if(r != maxR) swap(a[r],a[maxR]);
if(Zero(a[r][c])) { --r,freeX[c] = 1; continue; }

for(int i = r+1;i < n; ++i)
{
if(!Zero(a[i][c]))
{
double delta = a[i][c]/a[r][c];
for(int j=c;j<=m;++j) a[i][j] -= delta*a[r][j];
}
}
}
for(int i = r;i < n; ++i) if(!Zero(a[i][m])) return -1;
return r;
}

mod

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
62
63
64
65
66
67
68
69
70
71
72
const int maxn = 100;
const LL mod = 2;

LL a[maxn][maxn],ans[maxn];
bool freeX[maxn];

LL pow_m(LL a,LL n)
{
LL res = 1;
while(n)
{
if(n&1) res = res*a%mod;
a = a*a%mod;
n >>= 1;
}
return res;
}

LL inv(LL x)
{
return pow_m(x,mod-2);
}

LL getAns(LL n,LL m,LL r)
{
for(LL i = r-1;i >= 0; --i)
for(LL j = 0;j < m; ++j)
{
if(!a[i][j]) continue;
ans[j] = a[i][m];
for(LL k = j+1; k < m; ++k)
{
ans[j] -= a[i][k]*ans[k];
if((ans[j] %= mod) < 0) ans[j] += mod;
}
ans[j] = ans[j]*inv(a[i][j]) %mod;
break;
}
LL res = 0;
for(int i = 0;i < m;++i) res += ans[i];
return res;
}

LL gauss(LL n,LL m)
{
for(LL i=0;i<m;++i) freeX[i] = 0;
LL r = 0,c = 0;
for(;r < n && c < m; ++r,++c)
{
LL maxR = r;
for(LL i = r+1;i < n; ++i)
if(abs(a[i][c]) > abs(a[maxR][c])) maxR = i;
if(r != maxR) swap(a[r],a[maxR]);
if(!a[r][c]) { --r,freeX[c] = 1; continue; }

for(LL i = r+1;i < n; ++i)
{
if(a[i][c])
{
LL delta = a[i][c]*inv(a[r][c]);
for(LL j=c;j<=m;++j)
{
a[i][j] -= delta*a[r][j];
if((a[i][j] %= mod) < 0) a[i][j] += mod;
}
}
}
}
for(LL i = r;i < n; ++i) if(a[i][m]) return -1;

return r;
}

xor

即mod 2意义下的线性方程组
常用位运算来加速

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
const int maxn = 100;
LL a[maxn],ans[maxn];

int xorGauss(int n)
{
int r = 0,c = 60,m = 60;
for(;r < n && c >= 0; ++r,--c)
{
int p = r;
for(;p < n;++p) if((a[p]>>c) & 1) break;
if(p == n) { --r; continue; };
if(p != r) swap(a[p],a[r]);

for(int i=0;i < n;++i)
if(i != r && ((a[i]>>c) &1))
a[i] ^= a[r];
}

for(int i = r; i < m; ++i) if((a[i] >> 61) & 1) return -1;

for(int i = r - 1; ~i; --i)
for(int j = 0; j < m; ++j)
if((a[i] >> j) &1 ) {ans[j] = (a[i] >> 61)&1; break;}

return r;
}

逆矩阵

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
const double eps = 1e-9;
const int maxn = 100;
typedef double Matrix[maxn][maxn];
int n;

bool Zero(double x)
{
return fabs(x) < eps;
}

void matrix_mul(Matrix A,Matrix B,Matrix res)
{
Matrix C;
memset(C,0,sizeof(C));
for(int i = 0;i < n;++i)
for(int j = 0;j < n;++j)
for(int k = 0;k < n;++k)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]);
memcpy(res,C,sizeof(C));
}

void matrix_inv(Matrix C,Matrix res)
{
Matrix I,A;
memset(I,0,sizeof(I));
memcpy(A,C,sizeof(A));
for(int i=0;i<n;++i) I[i][i] = 1;
for(int i=0;i<n;++i)
{
for(int j=i;j<n;++j)
{
if(!Zero(A[j][i]))
{
swap(A[i],A[j]);
swap(I[i],I[j]);
break;
}
}

double t = 1/A[i][i];

for(int j=0;j<n;++j) I[i][j] = I[i][j]*t;
for(int j=0;j<n;++j) A[i][j] = A[i][j]*t;

for(int j=0;j<n;++j)
{
if(j != i && !Zero(A[j][i]))
{
double t = A[j][i];
for(int k=0;k<n;++k)
{
I[j][k] = I[j][k] - I[i][k]*t;
A[j][k] = A[j][k] - A[i][k]*t;
}
}
}
}
memcpy(res,I,sizeof(I));
}

题目

hihocoder 1195

直接套模板
!! 注意n,m是反着给的

hihocoder 1196

经典的开关问题
mod 2意义下的矩阵

sgu 275

n个元素中取若干个求最大异或和

对位进行高斯消元,求出极大线性无关组,异或起来即答案

CF-662A

有n对(a,b),从没对中选择一个,求最后异或和不等于0的概率

设所有a的异或和为$s$,令$b = a\text{ xor }b$
现在问题转化为求从b中选若干数,异或和s的方案数
考虑高斯消元,矩阵的秩为r,若前r个元素(即线性无关组)可以构成s
则异或和为s的方案数为$2^{n-r}$,否则答案为$1/1$
所有答案为$1 - \frac{2^{n-r}}{2^n} = \frac{2^r-1}{2^r}$

  • 如何判断是否可以构成s: 令$a[n] = s$,若消元最后$a[n] = 0$则代表可以构成s

参考资料