高斯消元
Tags:数学
https://www.zybuluo.com/xzyxzy/note/1046632
一、概述
两种形式
求解方程组
模拟加减消元，先消成上三角再带入求解，详见代码
异或方程组
与求解方程组类似，也许更简单，若只有01建议用bitset压常数
可以类比线性基哦（orz zsy dalao）
主要用途
主要用于计算出现环的概率DP问题，如[HNOI2013]游走
也有一些开关灯问题，很灵活地用到异或方程组如[USACO09NOV]灯Lights
二、题目
- [[hihoCoder]高斯消元·一](http://hihocoder.com/problemset/problem/1195)
- [[hihoCoder]高斯消元·二](http://hihocoder.com/problemset/problem/1196)
- [[Luogu]【模板】高斯消元法](https://www.luogu.org/problemnew/show/P3389)
- [[USACO09NOV]灯Lights](https://www.luogu.org/problemnew/show/P2962)
- [[SDOI2010]外星千足虫](https://www.luogu.org/problemnew/show/P2447)
- [[JSOI2008]球形空间产生器](https://www.luogu.org/problemnew/show/P4035)
- [[HNOI2013]游走](https://www.luogu.org/problemnew/show/P3232)
- [[HNOI2011]XOR和路径](https://www.luogu.org/problemnew/show/P3211)
- [[HDU]Time travel](https://vjudge.net/problem/HDU-4418)
- [BZOJ 2729 [HNOI2012]排队](https://www.luogu.org/problemnew/show/P3223)
- BZOJ 4804 欧拉心算
- BZOJ 1406 [AHOI2007]密码箱
- Luogu 1414 又是毕业季II
- Codeforces 113 D Museum
- [BZOJ 1178 [Usaco2010 Hol]Dotp 驱逐猪猡](https://www.luogu.org/problemnew/show/P2973)
- BZOJ 3270 博物馆
- BZOJ 4004 [JLOI2015]装备购买
- HDU 3364 ***s
- HDU 4870 Rating
- HDU 4936 Rainbow Island
- HDU 4592 Boring仪仗队
- BZOJ 1968 [Ahoi2005]COMMON 约数研究
考试题
- 2018.4.10 T1 BOM
代码
[hihoCoder]高斯消元·一
给定N个未知数M个方程，要求判无解、无穷解，有唯一解则输出毒瘤题「题解戳我BY TPLY」
注意：\(Line19\) 的\(!f[i][i]\)易写错为\(!f[now][i]\)!!!
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int N,M;
double f[1011][511];
const double EPS=1e-7;
void Gauss()
{
int flag=0;
for(int i=1;i<=N;i++)
{
int now=i;
for(int j=i+1;j<=M;j++)
if(fabs(f[now][i])<fabs(f[j][i]))
now=j;
if(now!=i)swap(f[now],f[i]);//在这里这一段不能省，当这一行为0时有可能这个式子是无效的所以换一个式子上来
if(fabs(f[i][i])<EPS){flag=1;continue;}//从i到M这些式子x[i]的系数都是0,那么如果x[i+1]-x[N]都有解的话，x[i]就有无穷解了，注意无解情况优先于无穷解
for(int j=i+1;j<=N+1;j++)f[i][j]/=f[i][i];f[i][i]=1;
for(int j=i+1;j<=M;j++)
{
for(int k=i+1;k<=N+1;k++)
f[j][k]-=f[j][i]*f[i][k];
f[j][i]=0;
}
//正常的消元
}
//判无解1：系数全0，常数非0
for(int j,i=1;i<=M;i++)
{
for(j=1;j<=N;j++)
if(fabs(f[i][j])>EPS)break;
if(j==N+1&&fabs(f[i][N+1])>EPS){printf("No solutions\n");return;}//有一项方程系数都为0但是常数项大于0于是方程无解
}
//判无解2：计算第i行答案时出现a*x[i]=C(a=0,C!=0)
for(int i=N;i>=1;i--)
{
for(int j=i+1;j<=N;j++)f[i][N+1]-=f[i][j]*f[j][N+1];
if(f[i][N+1]&&!f[i][i]){printf("No solutions\n");return;}
}
if(flag){printf("Many solutions\n");return;}
for(int i=1;i<=N;i++)
printf("%d\n",int(f[i][N+1]+0.5));
}
int main()
{
scanf("%d%d",&N,&M);
for(int i=1;i<=M;i++)
for(int j=1;j<=N+1;j++)
scanf("%lf",&f[i][j]);
Gauss();return 0;
}
[hihoCoder]高斯消元·二
异或方程组求解 模板
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<bitset>
using namespace std;
char s[10][10];
bitset<50>f[50];
int id(int x,int y){return (x-1)*6+y;}
void Gauss()
{
for(int i=1;i<=30;i++)
{
int now=i;
for(int j=i+1;j<=30;j++)
if(f[j][i]>f[now][i]) now=j;
if(now!=i) swap(f[now],f[i]);
for(int j=i+1;j<=30;j++)
if(f[j][i]) f[j]^=f[i];
}
for(int i=30;i>=1;i--)
for(int j=i-1;j>=1;j--)
if(f[j][i]) f[j]^=f[i];
int tot=0;
for(int i=1;i<=30;i++)
if(f[i][31]==1) tot++;
printf("%d\n",tot);
for(int i=1;i<=30;i++)
if(f[i][31]==1)
{
if(i%6==0) printf("%d %d\n",i/6,6);
else printf("%d %d\n",i/6+1,i%6);
}
}
int main()
{
for(int i=1;i<=5;i++)
scanf("%s",s[i]+1);
for(int i=1;i<=5;i++)
for(int j=1;j<=6;j++)
{
int p=id(i,j),l=id(i,j-1),r=id(i,j+1),u=id(i-1,j),d=id(i+1,j);
f[p][p]=1;f[p][31]=(s[i][j]-'0')^1;
if(i>1)f[p][u]=1;
if(i<5)f[p][d]=1;
if(j>1)f[p][l]=1;
if(j<6)f[p][r]=1;
}
Gauss();return 0;
}