题目大意
给定一个 n 元异或线性方程组（系数与常数均为 0/1），求其解：
时隔接近一年，重写一下这个代码。
https://cp-algorithms.com/linear_algebra/linear-system-gauss.html
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
|
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define SZ(a) ((int) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
using namespace std;
using ll = long long;
constexpr ll INF=static_cast<ll>(1e17)+9;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
const double pi=acos(-1.0);
int gauss(vector< bitset<110> > a,ll n,ll m,bitset<110> &ans){
vector<ll> where(m,-1);
for(int col=0,row=0; col<m && row<m;++col){
for(int i=row;i<n;++i){
if(a[i][col]){
swap(a[i],a[row]);
break;
}
}
if(!a[row][col]){
continue;
}
where[col]=row;
for(int i=0;i<n;++i){
if(i!=row && a[i][col]){
a[i]^=a[row];
}
}
++row;
}
for(int i=0;i<m;++i){
if(where[i]!=-1){
ans[i]=a[where[i]][m];
}
}
for(int i=0;i<n;++i){
ll sum=0;
for(int j=0;j<m;++j){
sum^=ans[j]*(int)a[i][j];
}
if(sum!=a[i][m]){
return 0;
}
}
for(int i=0;i<m;++i){
if(where[i]==-1) return 2;
}
return 1;
}
inline void solve(){
ll n;
cin>>n;
vector< bitset<110> > A(n+5);
for(int i=0;i<n;++i){
for(int j=0;j<n+1;++j){
int a;
cin>>a;
A[i][j]=(bool)a;
}
}
bitset<110> ans;
int ret=gauss(A,n,n,ans);
if(ret==2){
cout<<"Multiple sets of solutions\n";
}else if(ret==0){
cout<<"No solution\n";
}else{
for(int i=0;i<n;++i){
cout<<(int)ans[i]<<"\n";
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
solve();
return 0;
}
|
int opr=0; // 这个一定要写在循环内，因为每次都要重置（因为这个WA了一次）
利用了一个数异或自己变为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
|
#include <iostream>
using namespace std;
const int maxn=105;
int n,m[maxn][maxn];
void gauss(){
int r=1;
for(int c=1;c<=n;c++){
int opr=0;
for(int i=r;i<=n;i++){
if(m[i][c]==1){
opr=i;break;
}
}
if(opr==0) continue;
if(opr!=r){
for(int i=1;i<=n+1;i++){
swap(m[opr][i],m[r][i]);
}
}
for(int i=1;i<=n;i++){
if(m[i][c]==0 || i==r) continue;
for(int j=c;j<=n+1;j++){
m[i][j]^=m[r][j];
}
}
r++;
}
if(r<n+1){
for(int i=r;i<=n;i++){
if(m[i][n+1]!=0){
cout<<"No solution"<<endl;return;
}
}
cout<<"Multiple sets of solutions"<<endl;return;
}
for(int i=1;i<=n;i++){
cout<<m[i][n+1]<<endl;
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n+1;j++){
cin>>m[i][j];
}
}
gauss();
return 0;
}
|