高斯消元

acm

高斯消元入门

从例题开始,模板最后整理

poj1222 EXTENDED LIGHTS OUT

https://vjudge.net/problem/POJ-1222

有三十个小灯,每开启或熄灭一个灯,都会引起附近四个灯状态的变化.

以前写过一个遍历第一行枚举所有情况再dfs关下面的灯,最后check()一下.

现在可以考虑使用高斯消元,对于每一盏灯,都会有一个方程,也就是他附近的和他自己的灯有没有按,一共30个方程,30个未知数.

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 35;

int gcd(int a, int b){
    return b?gcd(b,a%b):a;
}

int lcm(int a, int b){
    return a/gcd(a,b)*b;
}

void Gauss(int a[][N], int n, int m, int &r, int &c){
    r = c= 0;
    for(;r < n && c <m; r++,c++){
        int maxi = r;
        for(int i = r+1; i < n; i++){
            if(abs(a[i][c]) > abs(a[maxi][c])){
                maxi = i;
            }
        }
        if(maxi!=r){
            for(int i = r; i < m+1; i++)
                swap(a[r][i], a[maxi][i]);
        }
        if(!a[r][c]){
            r--;
            continue;
        }
        for(int i = r+1; i < n; i++){
            if(a[i][c]){
                int x = abs(a[i][c]);
                int y = abs(a[r][c]);
                int LCM = lcm(x,y);
                int tx = LCM/x;
                int ty = LCM/y;
                if(a[i][c]*a[r][c]<0)
                    ty=-ty;
                for(int j = c; j < m+1; j++)
                    a[i][j] = ((a[i][j]%2*tx%2-a[r][j]%2*ty%2 + 2)%2+2)%2;
            }
        }
    }
}
//解的回带.
int Rewind(int a[][N], int x[], int r, int c){
    for(int i = r-1; i >= 0; i--){
        int t = a[i][c] %2;
        for(int j = i+1; j < c; j++){
            if(a[i][j])
                t-=a[i][j]%2*x[j]%2;
        }
        if(a[i][i]){
            x[i] = t/a[i][i]%2;
            x[i] = (x[i]+2)%2;
        }else{
            return -1;
        }
    }
    return 0;
}

int a[N][N];int x[N];

void Print(int a[][N], int n, int m){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m+1; j++){
            printf("%d ",a[i][j]);
        }
        puts("");
    }
}

int main(){
    int t=0;
    int n,m,T;scanf("%d",&T);
    while(T--){
        n=m=30;
        memset(a,0,sizeof a);
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 6; j++){
                //上下左右
                if(i>=1)a[6*i+j][6*(i-1)+j]=1;
                if(i<=3)a[6*i+j][6*(i+1)+j]=1;
                if(j>=1)a[6*i+j][6*i+j-1]=1;
                if(j<=4)a[6*i+j][6*i+j+1]=1;
                //自己
                a[6*i+j][6*i+j]=1;
                //解
                scanf("%d",&a[6*i+j][30]);
            }
        }
        int r,c;
        int cnt=0;
        Gauss(a,n,m,r,c);
        Rewind(a,x,r,c);
        Print(a,n,m);
        printf("PUZZLE #%d\n",++t);
        for(int i = 0; i < 30; i++){
            cnt++;
            if(cnt%6)printf("%d ",x[i]);
            else printf("%d\n",x[i]);
        }
    }
    return 0;
}

poj 1830

和上面一样的题意,这里增加了无解的情况.而且只需输出解的个数,也就是说如果有效方程数小于变元,那么每多一个变元,就多了一倍的解的个数.

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int N = 35;

int abs(int a){
    return a>0?a:-a;
}

int gcd(int a, int b){
    return b?gcd(b,a%b):a;
}

int lcm(int a, int b){
    return a/gcd(a,b)*b;
}

void Gauss(int a[][N], int n, int m, int &r, int &c){
    r= c =0;
    for(;r<n&&c<m;r++,c++){
        int maxi = r;
        for(int i = r+1; i < n; i++){
            if(abs(a[i][c]) > abs(a[maxi][c])){
                maxi = i;
            }
        }
        if(maxi!=r){
            for(int i = r; i < m+1; i++)
                swap(a[r][i],a[maxi][i]);
        }
        if(a[r][c] == 0){
            r--;
            continue;
        }
        for(int i = r+1; i < n; i++){
            if(a[i][c]){
                int x = abs(a[i][c]);
                int y = abs(a[r][c]);
                int LCM=lcm(x,y);
                int tx = LCM/x;
                int ty = LCM/y;
                if(a[i][c]*a[r][c]<0)
                    ty = -ty;
                for(int j = c; j<m+1; j++)
                    a[i][j] = ((a[i][j]%2*tx%2 - a[r][j]%2*ty%2 + 2)%2 + 2)%2;
            }
        }
    }
}

ll Rewind(int a[][N], int n, int m, int r, int c){
    for(int i = r; i < n; i++){
        if(a[i][c])return -1;
    }
    if(m==r)return 1;
    //方程组过少.
    else if(m>r)return (ll)1<<(m-r);
    return -1;
}

int a[N][N];
int t1[N],t2[N];

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int num,n,m;
        scanf("%d",&num);
        n = m = num;
        memset(a,0,sizeof a);
        for(int i = 0; i < num; i++)
            scanf("%d",&t1[i]);
        for(int i = 0; i < num; i++){
            scanf("%d",&t2[i]);
            a[i][num]=(t1[i]-t2[i]+2)%2;
            a[i][i]=1;
        }
        while(1){
            int x,y;
            scanf("%d %d",&x,&y);
            if(!x&&!y)break;
            a[y-1][x-1]=1;
        }
        int r,c;
        Gauss(a,n,m,r,c);
        ll ans = Rewind(a,n,m,r,c);
        if(ans == -1)puts("Oh,it's impossible~!!");
        else printf("%lld\n",ans);
    }
    return 0;
}

hdu 3359

也是很多个方程,这里主要是得到的都是double ,那我们从开始就考虑double,那么消元的时候就不利用gcd()去消,直接除了取消.

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 105;
void Gauss(double a[][N], int n ,int m, int &r, int &c){
    r=c=0;
    for(;r<n&&c<m;r++,c++){
        int maxi = r;
        for(int i = r+1; i < n; i++){
            if(fabs(a[i][c])>fabs(a[maxi][c])){
                maxi = i;
            }
        }
        if(maxi!=r){
            for(int i = r; i < m+1; i++){
                swap(a[maxi][i],a[r][i]);
            }
        }
        if(!a[r][c]){
            r--;
            continue;
        }
        for(int i = r+1; i < n; i++){
            if(a[i][c]){
                double t = -a[i][r]/a[r][r];
                for(int j = r; j < m+1; j++){
                    a[i][j] += t*a[r][j];
                }
            }
        }
    }
}

void Rewind(double a[][N], double x[], int n, int m, int r, int c){
    for(int i = r-1; i >= 0; i--){
        //再不改变原方程的情况下计算解
        double t = a[i][c];
        for(int j = i+1; j < c; j++){
            t-=a[i][j]*x[j];
        }
        if(a[i][i])
            x[i] = t/a[i][i];
    }
}

int dist(int x1, int y1, int x2, int y2){
    return abs(x1-x2)+abs(y1-y2);
}

double a[N][N],t[N][N],x[N];

int main(){
    int n,m;
    int w,h,d;
    bool flag = 1;
    while(~scanf("%d%d%d",&w,&h,&d) && w){
        if(flag)flag=0;
        else puts("");
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                scanf("%lf",&t[i][j]);
            }
        }
        n=m=w*h;
        memset(a, 0 ,sizeof a);
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                int cnt = 0;
                //暴力跑符合的点
                for(int k = 0; k < h; k++){
                    for(int l = 0; l < w; l++){
                        if(dist(i,j,k,l)<=d){
                            a[i*w+j][k*w+l]=1;
                            cnt ++;
                        }
                    }
                }
                a[i*w+j][m] = t[i][j]*cnt;
            }
        }
        int r,c;
        Gauss(a,n,m,r,c);
        Rewind(a,x,n,m,r,c);
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                printf("%8.2f",x[i*w+j]);
            }
            puts("");
        }
    }
    return 0;
}

下面是腿老师的专题里我没做过的题目:https://vjudge.net/contest/173410#problem/B

习题:

POJ3185B - The Water Bowls (枚举变元)(不判无解)

高斯消元可以求出一组解,但是我们这边需要枚举所有的自由变元,也就是多有无效的方程,对于这些自由变元,由于方程解不多,直接枚举就可以找到最小值了.

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 40;
const int inf = 0x3f3f3f3f;
int abs(int a){
    return a>0?a:-a;
}

int gcd(int a, int b){
    return b?gcd(b,a%b):a;
}

int lcm(int a, int b){
    return a/gcd(a,b)*a;
}

void Gauss(int a[][N], int n, int m, int &r, int &c){
    r=c=0;
    for(;r<n&&c<m;r++,c++){
        int maxi = r;
        for(int i = r+1; i < n; i++){
            if(abs(a[i][c] > abs(a[maxi][c])))
                maxi = i;
        }
        if(maxi != r){
            for(int i = r; i < m+1; i++){
                swap(a[maxi][i],a[r][i]);
            }
        }
        if(!a[r][c]){
            r--;continue;
        }
        for(int i = r+1; i < n; i++){
            if(a[i][c]){
                int x = abs(a[i][c]);
                int y = abs(a[r][c]);
                int LCM = lcm(x,y);
                int tx = LCM/x;
                int ty = LCM/y;
                if(a[i][c]*a[r][c]<0)
                    ty = -ty;
                for(int j = c; j < m+1; j++){
                    a[i][j] = (a[i][j]%2*tx%2 - a[r][j]%2*ty%2 + 2)%2;
                }
            }
        }
    }

}

int a[N][N];
int in[N];
int x[N];

void Print(int a[][N], int n ,int m){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m+1; j++){
            printf("%d ",a[i][j]);
        }
        puts("");
    }
}

int Rewind(int a[][N], int x[N], int n, int m, int r, int c){
    //枚举所有情况,分别回带
    int Min = inf;
    for(int k = 0; k < (1<<(n-r)); k++){
        for(int i = 0; i < n-r; i++)
            if(k&(1<<i))x[n-1-i]=1;
            else x[n-1-i]=0;
        for(int i = r-1; i >= 0; i--){
            int temp = a[i][c]%2;
            for(int j = i+1; j < c; j++){
                if(a[i][j])
                temp -= a[i][j]%2*x[j]%2;
            }
            if(a[i][i])
            x[i] = temp/a[i][i]%2;
            x[i] = (x[i]+2)%2;
        }
        int sum = 0;
        for(int i = 0; i < m; i++)
            sum += x[i];
        Min = min(Min,sum);
        if(!Min)break;
    }
    return Min;
}

int main(){
    memset(a, 0 , sizeof a);
    int n=N/2,m=N/2;
    for(int i = 0; i < N/2; i++){
        scanf("%d",&in[i]);
        a[i][m] = in[i];
    }
    a[0][0] = a[0][1] = 1;
    a[19][18] = a[19][19] = 1;
    for(int i = 1; i <= 18; i++){
        a[i][i-1] = a[i][i] = a[i][i+1] = 1;
    }
    int r,c;
    Gauss(a,n,m,r,c);
    //Print(a, n, m );
    int sum = Rewind(a,x,n,m,r,c);
    /*
    puts(" ");
    for(int i = 0; i < N/2; i++)printf("%d ",x[i]);
    puts("");
    */
    printf("%d",sum);
    return 0;
}

POJ 2065 高斯消元 + 模方程(逆元)

本体要用高斯消元去解模方程,在等式相减的时候注意+p %p,除此之外还要注意要使用 逆元取算每个解.这里使用ex_gcd(),当然也可以使用a^{p-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
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const int N = 80;
ll p,T;
char s[80];

ll abs(ll n){
    return n>0?n:-n;
}

ll power(ll a, ll b, ll mod){
    ll ans = 1 ;
    while(b){
        if(b&1)ans = (ans*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return ans;
}

ll gcd(ll a, ll b){
    return b?gcd(b,a%b):a;
}

ll lcm(ll a, ll b){
    return a/gcd(a,b)*b;
}

void e_gcd(ll a, ll b, ll &d, ll &x, ll &y){
    if(!b){
        d=a;x=1;y=0;
        return;
    }
    e_gcd(b,a%b,d,y,x);
    y -= (a/b)*x;
}

void Gauss(ll a[][N], int n, int m, int &r, int &c){
    r=c=0;
    for(;r<n && c < m; r++,c++){
        int maxi = r;
        for(int i = r+1; i < n; i++){
            if(abs(a[maxi][c] < abs(a[i][c])))
                maxi = i;
        }
        if(maxi!=r){
            for(int i = r; i < m+1; i++){
                swap(a[r][i], a[maxi][i]);
            }
        }
        if(!a[r][c]){
            r--;continue;
        }
        for(int i = r+1; i < n; i++){
            if(a[i][c]){
                ll x = abs(a[i][c]);
                ll y = abs(a[r][c]);
                ll LCM = lcm(x,y);
                ll tx = LCM/x;
                ll ty = LCM/y;
                if(a[r][c]*a[i][c]<0)
                    ty = -ty;
                for(int j = c; j < m+1; j++){
                    a[i][j] = ((a[i][j]%p*tx%p - a[r][j]%p*ty%p) + p)%p;
                }
            }
        }
    }
}

int Rewind(ll a[][N] , ll x[N], int n, int m, int r, int c){
    for(int i = r-1; i>=0; i--){
        ll temp = a[i][c]%p;
        for(int j = i+1; j < c; j++){
            temp -= a[i][j]*x[j];
        }
        //求逆元
        //欧几里得
        ll d,xx,y;
        e_gcd(a[i][i], p, d, xx, y);
        xx = (xx%p+p)%p;
        x[i] = ((temp%p*xx%p)%p+p)%p;
    }
}
#include<cstring>
ll a[N][N],x[N];

void Print(ll a[][N], int n, int m){
    for(int i = 0; i < n; i++){
        for(int j = 0 ;j < m+1; j++){
            printf("%3lld ",a[i][j]);
        }
        puts("");
    }
}


int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld %s",&p,s);
        memset(a, 0, sizeof a);
        memset(x, 0, sizeof x);
        int n,m;n = m = strlen(s);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                a[i][j] = power(i+1, j, p);
            }
        }
        for(int i = 0; i < n; i++){
            if(s[i]=='*')
                a[i][m] = 0;
            else a[i][m] = s[i]-'a'+1;
        }
        int r,c;
        //Print(a,n,m);
        Gauss(a, n, m , r, c);
        //Print(a,n,m);
        Rewind(a, x, n , m, r, c);
        for(int i = 0; i < n-1; i++){
            printf("%lld ",x[i]);
        }
        printf("%lld\n",x[n-1]);
    }
    return 0;
}

线性基　＋　高斯消元 　

线性基模板

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
struct L_B{
    long long d[61],p[61];
    int cnt;
    L_B()
    {
        memset(d,0,sizeof(d));
        memset(p,0,sizeof(p));
        cnt=0;
    }
    //插入
    bool insert(long long val)
    {
        for (int i=60;i>=0;i--)
            if (val&(1LL<<i))
            {
                if (!d[i])
                {
                    d[i]=val;
                    break;
                }
                val^=d[i];
            }
        return val>0;
    }
    //查询最大值
    long long query_max()
    {
        long long ret=0;
        for (int i=60;i>=0;i--)
            if ((ret^d[i])>ret)
                ret^=d[i];
        return ret;
    }
    //查询最小值
    long long query_min()
    {
        for (int i=0;i<=60;i++)
            if (d[i])
                return d[i];
        return 0;
    }
    //查找第k小时的重建(将线性基改造成每一位都相互独立)
    void rebuild()
    {
        for (int i=60;i>=0;i--)
            for (int j=i-1;j>=0;j--)
                if (d[i]&(1LL<<j))
                    d[i]^=d[j];
        for (int i=0;i<=60;i++)
            if (d[i])
                p[cnt++]=d[i];
    }
    long long kthquery(long long k)
    {
        int ret=0;
        if (k>=(1LL<<cnt))
            return -1;
        for (int i=60;i>=0;i--)
            if (k&(1LL<<i))
                ret^=p[i];
        return ret;
    }
}
//合并
L_B merge(const L_B &n1,const L_B &n2)
{
    L_B ret=n1;
    for (int i=60;i>=0;i--)
        if (n2.d[i])
            ret.insert(n1.d[i]);
    return ret;
}

用高斯消元的想法来去掉末尾的.获取第k个时，我们对每一个线性基都只有２个选择，这样k>>=1,k&!可以用来判断是否要选择．

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
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int maxn = 10005;

ll a[maxn];
int n;
void gauss(){
    int r = 0;
    for(int i =  60; i >= 0; i--){
        int j;
        for(j = r; j < n; j++)
            if((a[j]>>i)&1)
                break;
        if(j == n)continue;
        swap(a[j],a[r]);
        for(int k = 0; k < n; k++){
            if(k!=r && ((a[k]>>i)&1))
            a[k] ^= a[r];
        }
        r++;
    }
    sort(a, a+n);
    //去重
    n = unique(a,a+n)-a;
}

ll cal(ll k){
    int i = 0;
    if(a[0] == 0){
        i++;
        if(k==1)return 0;
        k--;
    }
    ll ans = 0;
    for(;i < n && k; i++){
        if(k&1)ans^=a[i];
        k >>= 1;
    }
    if(i == n&&k)return -1;
    return ans;
}

int main(){
    int t=0,T;scanf("%d",&T);
    while(t++<T){
        memset(a, 0, sizeof a);
        scanf("%d",&n);
        for(int i = 0; i < n; i++){
            scanf("%lld",&a[i]);
        }
        gauss();
        int q;
        scanf("%d",&q);
        ll k;
        printf("Case #%d:\n",t);
        while(q--){
            scanf("%lld",&k);
            printf("%lld\n",cal(k));
        }
    }
    return 0;
}

G - Painter’s Problem POJ - 1681(枚举自由变元+需要判断是否无解)

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
const int inf = 2<<28;
const int N = 230;
using namespace std;

int gcd(int a, int b){
    return b?gcd(b, a%b):a;
}

int lcm(int a, int b){
    return a/gcd(a,b)*b;
}

int a[N][N],n,m,x[N],free[N];
int cnt;
void Gauss(int a[][N], int n, int m, int &r, int &c){
    memset(free, 0, sizeof free);
    r = c = cnt = 0;
    for(; r < n && c < m; r++,c++){
        int maxi = r;
        for(int i = r+1; i < n; i++){
            if(abs(a[i][c]) > abs(a[maxi][c])){
                maxi = i;
            }
        }
        if(maxi!=r){
            for(int i = r; i <m+1; i++)
                swap(a[r][i], a[maxi][i]);
        }
        if(!a[r][c]){
            free[cnt++] = c;
            r--;continue;
        }
        for(int i = r + 1; i < n ; i++){
            if(a[i][c]){
                int x = abs(a[i][c]);
                int y = abs(a[r][c]);
                int LCM = lcm(x,y);
                int tx = LCM/x;
                int ty = LCM/y;
                if(a[i][c]*a[r][c] < 0){
                    ty = -ty;
                }
                for(int j = c; j < m+1; j++){
                    a[i][j] = ((a[i][j]%2*tx%2 - a[r][j]%2*ty%2 + 2)%2 + 2)%2;
                }
            }
        }
    }
}

int Rewind(int a[][N], int x[], int r, int c){
    for(int i = r; i < n; i++){
        if(a[i][c])
            return -1;
    }
    int Minx = inf;
    for(int k = 0; k < (1<<cnt); k++){
        int num = 0;
        int s = k;
        for(int i = 0; i < cnt; i ++){
            if(x[free[i]]=s&1)num++;
            s >>= 1;
        }
        for(int i = r-1; i >= 0; i--){
            int tmp = a[i][m];
            for(int j = i+1; j < m; j++){
                tmp -= a[i][j]%2*x[j]%2;
            }
            if(a[i][i]){
                x[i] = tmp/a[i][i]%2;
                x[i] = (x[i]+2)%2;
                if(x[i]) num++;
            }
        }
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum+=x[i];
        }
        Minx = min(Minx, sum);
    }
    return Minx;
}

void Print(int a[][N], int n , int m){
    for(int i = 0; i <n ; i++){
        for(int j = 0; j <m+1; j++){
            printf("%3d ",a[i][j]);
        }
        puts("");
    }
    puts("---");
}

int main(){
    int t;scanf("%d",&t);
    while(t--){
       scanf("%d",&n);m=n*n;
       int p = n;
       n*=n;
       char tp[20];
       memset(a, 0, sizeof a);
       memset(x, 0, sizeof x);
       for(int i = 0; i < p; i++){
            scanf("%s",&tp);
            for(int j = 0; j < p; j++)
                if(tp[j] == 'w')
                a[i*p+j][n]=1;
       }
        //Print(a, n, m);
       for(int i = 0; i < p; i++){
            for(int j = 0; j < p; j++){
                if(i>0){a[i*p+j][(i-1)*p+j] = 1;}
                if(i<p-1){a[i*p+j][(i+1)*p+j] = 1;}
                if(j>0){a[i*p+j][i*p+j-1] = 1;}
                if(j<p-1){a[i*p+j][i*p+j+1]=1;}
                a[i*p+j][i*p+j]=1;
            }
       }
       int r,c;
       //Print(a, n, m);
       Gauss(a, n, n, r, c);
       //Print(a, n, m);
       int ans = Rewind(a, x, r, c);
       //Print(a, n, m);
       if(ans+1){
        printf("%d\n",ans);
       }else puts("inf");
    }
    return 0;
}

I - Lanterns HDU - 3364(求解方程个数)

这里要求解方程个数,在有解的情况下,答案就是$2^{自由变元的个数}$, 这里要注意对于m>n的情况时,只跑了n行,也就是说自由变元的个数应该是m-(c-cnt);

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int N = 70;
const int inf = 0x3f3f3f3f;

int gcd(int a, int b){
    return b?gcd(b,a%b):a;
}

int lcm(int a, int b){
    return a/gcd(a,b)*b;
}

int a[N][N],x[N],fre[N],n,m;
int jilu[N][N],cnt;
ll power(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b&1)ans *= a;
        a *= a;
        b >>=1;
    }
    return ans;
}

void Gauss(int a[][N], int n, int m, int &r, int &c){
    cnt = r = c = 0;
    for(; r < n & c < m ; r++,c++){
        int maxi = r;
        for(int i = r+1; i < n; i++){
            if(abs(a[maxi][c] < abs(a[i][c])))
                maxi = i;
        }
        if(maxi != r){
            for(int i = r; i < m+1; i++){
                swap(a[maxi][i], a[r][i]);
            }
        }
        if(!a[r][c]){
            fre[cnt++] = c;
            r--;continue;
        }
        for(int i = r+1; i < n; i++){
            if(a[i][c]){
                int x = abs(a[i][c]);
                int y = abs(a[r][c]);
                int LCM = lcm(x, y);
                int tx = LCM/x;
                int ty = LCM/y;
                if(a[i][c] * a[r][c] <0)
                    ty = -ty;
                for(int j = c; j < m+1; j++){
                    a[i][j] = (a[i][j]%2*tx%2 - a[r][j]%2*ty%2+2)%2;
                }
            }
        }

    }
}

ll Rewind(int a[][N], int x[N], int n, int m, int r, int c){
    for(int i = r; i < n; i++){
        if(a[i][c])
            return -1;
    }
    /*

    int Minx = inf;
    for(int k = 0; k < (1<<cnt); k++){
        int num = 0;
        int s = k;
        for(int i = 0; i < cnt; i++){
            if(x[free[i]]=s&1)num++;
            s >> = 1;
        }
        for(int i = r-1; i >= 0; i--){
            int tmp = a[i][m];
            for(int j = i+1; j < m; j++){
                tmp -= a[i][j]%2*x[j]%2;
            }
            if(a[i][i]){
                x[i] = tmp/a[i][i]%2;
                x[i] = (x[i]+2)%2;
                if(x[i])num++;
            }
        }
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += x[i];
        }
        Minx = min(Minx, sum);
    }
    */
    //printf("%d %d %d",cnt, r, m);
    return 1LL<< (m-(c-cnt));
}

void Print(int a[][N], int n, int m){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m+1; j++)
            printf("%d ",a[i][j]);
        puts("");
    }
}

int main(){
    int t=0,T;scanf("%d",&T);
    while(t++<T){
        scanf("%d%d",&n,&m);
        char c;int in;
        memset(jilu, 0 ,sizeof jilu);
        for(int i = 0; i < m; i++){
            int k;scanf("%d",&k);
            for(int j = 0 ; j < k; j++){
                scanf("%d",&in);
                jilu[in-1][i] = 1;
            }
        }
        int query;
        scanf("%d",&query);
        printf("Case %d:\n",t);

        for(int i = 0; i < query;i++){
            memcpy(a, jilu, sizeof jilu);
            for(int j = 0; j < n; j++){
                scanf("%d",&a[j][m]);
            }
            int r,c;
            //Print(a, n ,m);
            Gauss(a, n, m, r, c);
            ll ans = Rewind(a, x, n, m, r, c);
            if(ans+1)printf("%lld\n",ans);
            else puts("0");
        }
    }
    return 0;
}

J - Widget Factory POJ - 2947(模方程 + 判断有解无解的条件!)

此处高能,wa了好几发,原因竟然是我还是没有搞清楚,多解和无解的情况.在此重新声明:

多解的条件是: r < m

无解的情况是:i>=r若 a[i][c] != 0

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int N = 350;
const int mod = 7;

int abs(int n){
    return n>0?n:-n;
}

int gcd(int a, int b){
    return b?gcd(b,a%b):a;
}

int lcm(int a, int b){
    return a/gcd(a,b)*b;
}

ll power(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a =a *a %mod;
        b >>=1;
    }
    return ans;
}

void e_gcd(int a, int b, int &d, int &x, int &y){
    if(!b){
        d = a;x = 1;y = 0;
        return;
    }
    e_gcd(b, a%b, d, y, x);
    y -= (a/b)*x;
}

int a[N][N], fre[N], x[N], n,m, cnt;

void Gauss(int a[][N], int n, int m, int &r, int &c){
    memset(fre, 0, sizeof fre);
    r = c = cnt = 0;
    for(; r < n && c < m ; r++,c++){
        int maxi = r;
        for(int i = r+1; i < n; i++){
            if(abs(a[maxi][c]) < abs(a[i][c]))
                maxi = i;
        }
        if(maxi!=r){
            for(int i = r; i < m+1; i++)
                swap(a[r][i],a[maxi][i]);
        }
        if(!a[r][c]){
            fre[cnt++]=c;
            r --;continue;
        }
        for(int i = r +1; i < n; i++){
            if(a[i][c]){
                int x = abs(a[i][c]);
                int y = abs(a[r][c]);
                int LCM = lcm(x,y);
                int tx = LCM/x;
                int ty = LCM/y;
                if(a[r][c]*a[i][c] < 0)
                    ty = -ty;
                for(int j =c ; j < m+1; j++)
                    a[i][j] = (a[i][j]%mod*tx%mod - a[r][j]%mod*ty%mod+mod)%mod;
            }
        }
    }
}

int Rewind(int a[][N], int x[N], int n, int m, int r, int c){
    for(int i = r ; i < n; i++){
        if(a[i][c])return -1;
    }
    if(cnt || r<m)return 1;
    //求解
    memset(x, 0, sizeof x);
    for(int i = r-1; i >= 0; i--){
        int temp = a[i][c] % mod;
        for(int j = i+1; j < c; j++){
            temp -= a[i][j]*x[j];
        }
        //求逆元的欧几里得
        int d,xx,yy;
        e_gcd(a[i][i], mod, d, xx, yy);
        xx = (xx%mod+mod)%mod;
        x[i] = ((temp%mod*xx%mod)%mod+mod)%mod;
        if(x[i]<3)x[i]+=mod;
    }
    return 0;
}

void Print(int a[][N], int n, int m){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m+1; j++){
            printf("%d ",a[i][j]);
        }
        puts("");
    }
}
char day[10][10]={"MON","TUE","WED","THU","FRI","SAT","SUN"};
int getDay(char* str){
    for(int i = 0; i < 7; i++){
        if(!strcmp(day[i],str))
            return i+1;
    }
    puts("Hello wrold!");
    return 0;
}

int getCha(char* str1, char* str2){
    int d1 = getDay(str1);
    int d2 = getDay(str2);
    return (d2-d1+1+mod)%mod;
}

char str1[10],str2[10];
int main(){
    while(~scanf("%d%d",&m,&n) && n){
        memset(a, 0, sizeof a);
        for(int i = 0; i < n; i++){
            int k,in;scanf("%d%s%s",&k,str1,str2);
            a[i][m] = getCha(str1, str2);
            for(int j = 0; j < k; j++){
                scanf("%d",&in);
                a[i][in-1]++;
                a[i][in-1]%=mod;
            }
        }
        int r,c;
        //Print(a,n,m);
        Gauss(a, n, m, r, c);
        int ans = Rewind(a, x, n, m, r, c);
        if(ans==-1)puts("Inconsistent data.");
        else if(ans == 1)puts("Multiple solutions.");
        else{
            for(int i = 0; i < m; i++)
                printf("%d%c",x[i]," \n"[i==(m-1)]);
        }
    }
    return 0;
}

还有两道概率dp+ 高斯消元放在概率dp中

本文标题:高斯消元

文章作者:呼哧

发布时间:2017-07-19, 18:40:42

最后更新:2018-08-04, 02:47:40

原始链接:http://hu-chi.github.io/2017/07/19/acm/高斯消元/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 高斯消元入门
    1. 1.1. poj1222 EXTENDED LIGHTS OUT
    2. 1.2. poj 1830
    3. 1.3. hdu 3359
  2. 2. 习题:
    1. 2.1. POJ3185B - The Water Bowls (枚举变元)(不判无解)
    2. 2.2. POJ 2065 高斯消元 + 模方程(逆元)
    3. 2.3. 线性基　＋　高斯消元 　
    4. 2.4. G - Painter’s Problem POJ - 1681(枚举自由变元+需要判断是否无解)
    5. 2.5. I - Lanterns HDU - 3364(求解方程个数)
    6. 2.6. J - Widget Factory POJ - 2947(模方程 + 判断有解无解的条件!)
    7. 2.7. 还有两道概率dp+ 高斯消元放在概率dp中
|