高斯消元与线性基
感觉就是线代里面的矩阵，还有线性相关，这两部分。
今日战况
今日总结
A题快要写吐了，但是在写A题的时候把高斯消元理解了不少。甚至快把矩阵类(结构体)给封装好了(bushi)。
把差不多写好的浮点数的矩阵结构体代码放到这里。
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
| struct Matrix{
vector<vector<double> > c;
int nn,mm;
Matrix(){
nn=0;mm=0;
}
Matrix(int nnn,int mmm){
nn=nnn;mm=mmm;
c.resize(nnn+1);
for(int i=1;i<=nn;++i)
c[i].resize(mm+1);
}
friend Matrix operator*(const Matrix& x,const Matrix& y){
Matrix re(x.nn,y.mm);
for(int i=1;i<=x.nn;++i){
for(int j=1;j<=y.mm;++j){
for(int k=1;k<=x.mm;++k){
re.c[i][j]+=(double)((LL)(x.c[i][k]*y.c[k][j])%MOD)+x.c[i][k]*y.c[k][j]-(LL)(x.c[i][k]*y.c[k][j]);
re.c[i][j]=(double)((LL)(re.c[i][j])%MOD)+re.c[i][j]-(LL)(re.c[i][j]);
}
}
}
return re;
}
void elimination(){
int nm=min(nn,mm);
for(int cc=1,r=1;cc<=nm;++cc){
int t=r;
for(int i=r+1;i<=nn;++i)
if(fabs(c[i][cc])>fabs(c[t][cc]))
t=i;
if(fabs(c[t][cc])<eps) continue;
if(t!=r){
for(int j=cc;j<=mm;++j)
swap(c[t][j],c[r][j]);
}
for(int j=mm;j>=cc;--j)
c[r][j]/=c[r][cc];
for(int i=1;i<=nn;++i){
if(i==r) continue;
if(fabs(c[i][cc])>eps)
for(int j=mm;j>=cc;--j)
c[i][j]=c[i][j]-c[i][cc]*c[r][j];
}
++r;
}
}
Matrix inverse() const{
Matrix re(this->nn,this->mm),temp=*this;
temp.mm*=2;
for(int i=1;i<=temp.nn;++i){
temp.c[i].resize(temp.mm+1,0);
}
for(int i=1;i<=temp.nn;++i){
temp.c[i][temp.nn+i]=1;
}
temp.elimination();
for(int i=1;i<=re.nn;++i)
for(int j=1;j<=re.mm;++j){
re.c[i][j]=temp.c[i][re.nn+j];
}
return re;
}
void output(){
for(int i=1;i<=nn;++i){
for(int j=1;j<mm;++j){
printf("%lf ",c[i][j]);
}
printf("%lf\n",c[i][mm]);
}
}
};
|
- 在后面线性基的学习中，在网上查了不少，也理解的差不多了，感觉就跟线代里面的最大线性不相关向量组(好像叫这名)很像，只不过是变成了二进制的形式。
- 然后G题里有一个坑(可能并不算坑)，当线性基的元素个数等于n的时候，他们异或得不到0这个结果。
- 这部分感觉主要就是熟悉理解模板。但是C题实在是看不出来和高斯消元有什么关系，A题也是一直WA，用了两种方法，都是WA。现在也没想出比较好的解决方法。
