高斯消元

数学

更好阅读体验：https://www.zybuluo.com/xzyxzy/note/1046632

一、概述

两种形式

求解方程组

模拟加减消元，先消成上三角再带入求解，详见代码

异或方程组

与求解方程组类似，也许更简单，若只有01建议用bitset压常数
可以类比线性基哦（orz zsy dalao）

主要用途

主要用于计算出现环的概率DP问题，如[HNOI2013]游走
也有一些开关灯问题，很灵活地用到异或方程组如[USACO09NOV]灯Lights

二、题目

• [hihoCoder]高斯消元·一
• [hihoCoder]高斯消元·二
• [Luogu]【模板】高斯消元法
• [USACO09NOV]灯Lights
• [SDOI2010]外星千足虫
• [JSOI2008]球形空间产生器
• [HNOI2013]游走
• [HNOI2011]XOR和路径
• [HDU]Time travel
• BZOJ 2729 [HNOI2012]排队
• BZOJ 4804 欧拉心算
• BZOJ 1406 [AHOI2007]密码箱
• Luogu 1414 又是毕业季II
• Codeforces 113 D Museum
• BZOJ 1178 [Usaco2010 Hol]Dotp 驱逐猪猡
• BZOJ 3270 博物馆
• BZOJ 4004 [JLOI2015]装备购买
• HDU 3364 Lanterns
• 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;
}