高斯消元模板

整数类型高斯消元

返回值的情况

  • -2表示有浮点数解,但无整数解
  • -1表示无解
  • 0表示唯一解
  • 大于0表示无穷解,并返回自由变元的个数

    其他说明

  • 有equ个方程,var个变元。
  • 增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var.

浮点(整)型

Code

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
int gauss(){
int r=0;
rep(i,1,n){
rep(k,i+1,n)
if(a[k][i]>eps){swap(a[k],a[i]);break;}
if(fabs(a[i][i]) < eps) continue;
//a[i][i]化为1
repd(j,n+1,i) a[i][j]/=a[i][i]; // 倒序
//a[i][i]左下角化为0
rep(k,i+1,n){
if(fabs(a[k][i]) < eps)continue;
repd(j,n+1,i) //倒序
a[k][j] -= a[k][i]*a[i][j];
}
r++
}
if (r < n){
for (int i = r; i < n; i ++ )
if (fabs(a[i][n+1]) > eps)
return 2; // 无解
return 1; // 有无穷多组解
}
//不用把右上角全化为0,更新答案即可
repd(i,n,1)
repd(j,i-1,1)
a[j][n+1] -= a[j][i] * a[i][n+1];
return 0;
}

求解异或方程组

经常需要枚举自由元

Code

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
73
74
75
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define nmax 35
using namespace std;
int a[nmax][nmax];
int x[nmax];
int hashback[nmax][nmax];
int free_x[nmax];
char mp[nmax][nmax];
int ans1,ans2;
int equ,var;
int Gauss(){
int max_r;
int col=0,num = 0;
int k;
for(int i = 0;i<=var;++i) x[i] = free_x[i] = 0;
for(k = 0;k < equ && col < var;k++,col++){
max_r=k;
for(int i=k+1;i<equ;i++){
if(abs(a[i][col])>abs(a[max_r][col])) max_r=i;
}
if(max_r!=k){
for(int j=k ;j<var+1;j++) swap(a[k][j],a[max_r][j]);
}
if(a[k][col]==0){
free_x[num++] = col;
k--; continue;
}
for(int i=k+1;i<equ;i++){
if(a[i][col]!=0){
for(int j=col;j<var+1;j++){
a[i][j]^=a[k][j];;
}
}
}
}
for(int i = k;i<equ;++i){
if(a[i][col] != 0) return -1;
}
if(k < var) return var - k;
for(int i = var - 1; i >= 0; i--){
x[i]=a[i][var];
for(int j = i + 1; j < var; j++){
x[i] ^= ( a[i][j] && x[j]);
}
}
return 0;
}
void enum_freex(int n,int & ans){
int num = (1<<(n));
ans = 1e9+7;
for(int i = 0;i<num;++i){
int cnt = 0;
for(int j = 0;j<n;++j){
if(i&(1<<j)){
cnt++;
x[free_x[j]] = 1;
}else x[free_x[j]] = 0;
}
for(int k = var-n-1;k>=0;--k){// 没有自由元的最下面一行
int index = 0;
for(index = k;k<var;index++){// 在当前行找到第一个非0自由元(如果存在的话)
if(a[k][index]) break;
}
x[index] = a[k][var];
for(int j = index+1;j<var;++j){// 向后依次计算出结果
if(a[k][j]) x[index] ^= x[j];
}
cnt += x[index]; // 如果结果为1,则统计
}
ans = min(ans,cnt);
}
}
Donate comment here