高斯消元
朴素的实数高斯消元写的比较短的板子：
1
2
3
4
5
6
7
8
9
| void gauss(db a[C][C],int n) {
F(i,1,n) {
int ma=i;
F(j,i,n) fabs(a[j][i])>fabs(a[ma][i])&&(ma=j);
swap(a[ma],a[i]);
UF(j,n+1,i) a[i][j]/=a[i][i];
F(j,1,n) if(j^i) UF(k,n+1,i) a[j][k]-=a[j][i]*a[i][k];
}
}
|
模意义下高斯消元可以照猫画虎：
1
2
3
4
5
6
7
8
| void gauss(ll a[C][C],int n) {
F(i,1,n) {
int ma=i;F(j,i,n) a[j][i]&&(ma=j);
swap(a[ma],a[i]);ll iv=ksm(a[i][i]);
UF(j,n+1,i) a[i][j]=a[i][j]*iv%p;
F(j,1,n) if(j^i) UF(k,n+1,i) (a[j][k]+=p-a[j][i]*a[i][k]%p)%=p;
}
}
|
上面两种高斯消元都可以消成仅有主对角线有值。
但假如没有逆元就不是很好玩了，我们可以辗转相除，不会证复杂度，反正是对的：
1
2
3
4
5
6
7
8
9
| void gau() {
F(i,1,n) F(j,i+1,n) {
while(a[i][i]) {
int d=a[j][i]/a[i][i];
F(k,i,n+1) (a[j][k]+=p-d*a[i][k]%p)%=p;
swap(a[i],a[j]);
} swap(a[i],a[j]);
}
}
|
需要频繁交换，换用 basic_string 可以获得小幅性能提升。
需要注意的是，该方法可以方便的求出一个上三角矩阵，要想求出主对角线矩阵还需要代换一步，如果不求行列式还是尽量别用了。
（求上三角矩阵有逆元可以这么写：
1
2
3
4
5
6
| F(i,1,n) F(j,i+1,n) {
if(a[i][i]) {
int d=a[j][i]*inv(a[i][i]);
F(k,i,n) a[j][k]=a[j][k]-a[i][k]*d;
} else swap(a[i],a[j]);
}
|
矩阵求逆
原理：A−1(A,I)=(I,A−1)，构造 (A,I) 并对左边高消即可得到 (I,A−1)。
1
2
3
4
5
6
7
8
9
10
| bool inv(ll a[C][2*C],int n) {
F(i,1,n) a[i][i+n]=1;
F(i,1,n) {
int ma=i;F(j,i,n) a[j][i]&&(ma=j);
swap(a[ma],a[i]);if(!a[i][i]) return 0;
ll iv=ksm(a[i][i]);
UF(j,2*n,i) a[i][j]=a[i][j]*iv%p;
F(j,1,n) if(j^i) UF(k,2*n,i) (a[j][k]+=p-a[j][i]*a[i][k]%p)%=p;
} return 1;
}
|
行列式求值
1
2
3
4
5
6
7
8
9
10
11
12
| ll gau() {ll res=1;
F(i,1,n) {
F(j,i+1,n) {
while(a[i][i]) {
int d=a[j][i]/a[i][i];
F(k,i,n) (a[j][k]+=p-d*a[i][k]%p)%=p;
swap(a[i],a[j]);res=p-res;
} swap(a[i],a[j]);res=p-res;
}
} F(i,1,n) res=res*a[i][i]%p;
return res;
}
|
