高斯消元简笔
高斯消元，利用消元思想，通过矩阵初等变换，达到求解线性方程组的目的。
高斯消元基本工具：一个 \(n\times(n+1)\) 的矩阵，其中左边 \(n\times n\) 的部分为系数矩阵，第 \(n+1\) 列表示方程式右侧常数。
求解结束：
- 若方程组有唯一解，则第 \(i\) 行只有 \(a_{i,i}\ne 0\)
- 若方程组有无穷多组解，则存在行 \(a_{i,1}=a_{i,2}=...=a_{i,n+1}=0\)
- 若方程组无解，则存在行 \(a_{i,1}=a_{i,2}=...=a_{i,n}=0,a_{i,n+1}\ne 0\)
更多地，如果不想要小数而是求在 \(\bmod p\) 下值则采用辗转相除方法。
高斯消元的应用：
- 求矩阵行列式
- 求异或方程组(AcWing开关问题)
相关题目：
【模板】高斯消元法
点击查看代码
#include
using namespace std;
const int N=105;
const double eps=1e-4;
int n;
double a[N][N];
int main(){
cin>>n;
for(int i=1;i<=n;i++)for(int j=1;j<=n+1;j++)cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int p=1;p<=n;p++)if(p!=i){
double d=a[p][i]/a[i][i];
for(int q=1;q<=n+1;q++)a[p][q]-=d*a[i][q];
}
for(int i=1;i<=n;i++){
bool flag=0;
for(int j=1;j<=n;j++)if(abs(a[i][j])>eps){flag=1;a[i][n+1]/=a[i][j];break;}
if(!flag){puts("No Solution");return 0;}
}
for(int i=1;i<=n;i++)printf("%.2f\n",a[i][n+1]);
}
【模板】行列式求值
点击查看代码
#include
using namespace std;
const int N=605;
int n,det=1,mod,a[N][N];
int main(){
cin>>n>>mod;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
while(a[i][i]){
int d=a[j][i]/a[i][i];
for(int k=1;k<=n;k++)a[j][k]=(a[j][k]-1ll*d*a[i][k]%mod+mod)%mod;
swap(a[i],a[j]),det=-det;
}
swap(a[i],a[j]),det=-det;
}
for(int i=1;i<=n;i++)det=1ll*det*a[i][i]%mod;
cout<<(det+mod)%mod;
}
【变式】球形空间产生器
点击查看代码
#include
using namespace std;
const double eps=1e-5;
int n;
double a[15][15];
int main(){
cin>>n,n++;
for(int i=1;i<=n;i++){
for(int j=1;j>a[i][j],a[i][n+1]+=a[i][j]*a[i][j],a[i][j]*=2;
a[i][n]=1;
}
for(int i=1;i<=n;i++){
if(abs(a[i][i])eps)swap(a[i],a[j]); //这句话应该时刻加上的！
for(int j=1;j<=n;j++)if(i!=j){
double d=a[j][i]/a[i][i];
for(int k=1;k<=n+1;k++)a[j][k]-=a[i][k]*d;
}
}
for(int i=1;i