高斯消元：

一、整数高斯消元：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=20;
int gcd(int a,int b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}

int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}



int a[maxn][maxn];
int x[maxn];
int free_x[maxn];
int Gauss(int equ,int var)
{
    int k,col,max_r,ta,tb;
    int LCM,temp,free_x_num,free_index;

    for(int i=0;i<=var;i++)
        x[i]=0,free_x[i]=1;

    for(k=0,col=0;k<equ&&col<var;k++,col++)
    {
        max_r=k;
        for(int i=k+1;i<equ;i++)
        {
            if(abs(a[i][col])>abs(a[max_r][col])) max_r=i;
        }

        if(max_r!=k)
        {
            for(int j=k;j<var+1;j++) swap(a[k][j],a[max_r][j]);
            //for(int j=col;j<var+1;j++) swap(a[k][j],a[max_r][j]);
        }

        if(a[k][col]==0)
        {
            k--;
            continue;
        }
        
        for(int i=k+1;i<equ;i++)
        {
            if(a[i][col]!=0)
            {
                LCM=lcm(abs(a[i][col]),abs(a[k][col]));
                ta=LCM/abs(a[i][col]);
                tb=LCM/abs(a[k][col]);
                if(a[i][col]*a[k][col]<0) tb=-tb;
                for(int j=col;j<var+1;j++)
                {
                    a[i][j]=a[i][j]*ta-a[k][j]*tb;
                }
            }
        }
    }

    for(int i=k;i<equ;i++)
    {
        if(a[i][col]!=0) return -1;
    }

    if(k<var)
    {
        for(int i=k-1;i>=0;i--)
        {
            free_x_num=0;
            for(int j=0;j<var;j++)
            {
                if(a[i][j]&&free_x[j]) free_x_num++,free_index=j;
            }

            if(free_x_num>1) continue;

            temp=a[i][var];
            for(int j=0;j<var;j++)
            {
                if(a[i][j]&&j!=free_index) temp-=a[i][j]*x[j];
            }

            x[free_index]=temp/a[i][free_index];
            free_x[free_index]=0;
        }
        return var-k;
    }

    for(int i=var-1;i>=0;i--)
    {
        temp=a[i][var];
        for(int j=i+1;j<var;j++)
        {
            if(a[i][j]) temp-=a[i][j]*x[j];
        }
        if(temp%a[i][i]!=0) return -2;
        x[i]=temp/a[i][i];
    }
    return 0;
}

int main(void)
{
    int equ,var;
    while(scanf("%d%d",&equ,&var)!=EOF)
    {
        for(int i=0;i<equ;i++)
        {
            for(int j=0;j<=var;j++)
                scanf("%d",&a[i][j]);
        }

        int k=Gauss(equ,var);
        if(k==-1) cout<<"no answer!\n";
        if(k==-2) cout<<"you xiao shu jie\n";
        if(k==0)
        {
            cout<<"This: ";
            for(int i=0;i<var;i++)
                printf("%d ",x[i]);
            putchar('\n');
        }
        if(k>0)
        {
            printf("free: %d\n",k);
            for(int i=0;i<var;i++)
            {
                printf("%d ",x[i]);
                putchar('\n');
            }
        }
    }
    return 0;

}

二、浮点数高斯消元

int Gauss(int m,int n)
{
    int k,col;
    for(k=0,col=0;k<m&&col<n;k++,col++)
    {
        int r=k;
        for(int i=k+1;i<m;i++)
            if(fabs(a[i][col])>fabs(a[r][col])) r=i;

        if(fabs(a[r][col])<eps)
        {
            k--;
            continue;
        }

        if(r!=k)
        {
            for(int i=col;i<=n;i++)
                swap(a[r][i],a[k][i]);
        }

        for(int i=k+1;i<m;i++)
        {
            if(fabs(a[i][col])>eps)
            {
                double t=a[i][col]/a[k][col];
                for(int j=col;j<=n;j++)
                    a[i][j]-=a[k][j]*t;
                a[i][col]=0;
            }
        }
    }

    for(int i=k;i<m;i++)
        if(fabs(a[i][n])>eps) return -1;

    if(k<n) return n-k;

    for(int i=n-1;i>=0;i--)
    {
        double temp=a[i][n];
        for(int j=i+1;j<n;j++)
            temp-=x[j]*a[i][j];

        x[i]=temp/a[i][i];
    }
    return 0;

}

球形空间产生器sphere HYSBZ - 1013
有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球
面上n+1个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。

Input
　　第一行是一个整数n(1<=N=10)。接下来的n+1行，每行有n个实数，表示球面上一点的n维坐标。每一个实数精确到小数点
后6位，且其绝对值都不超过20000。

Output
　　有且只有一行，依次给出球心的n维坐标（n个实数），两个实数之间用一个空格隔开。每个实数精确到小数点
后3位。数据保证有解。你的答案必须和标准输出一模一样才能够得分。

Sample Input
2
0.0 0.0
-1.0 1.0
1.0 0.0
Sample Output
0.500 1.500

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 20;
double a[maxn][maxn],b[maxn]={0.0},c[maxn][maxn];
int n;
int main(void)
{
    cin>>n;
    for(int i=1;i<=n+1;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%lf",&a[i][j]);
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            c[i][j]=2*(a[i][j]-a[i+1][j]);
            b[i]+=a[i][j]*a[i][j]-a[i+1][j]*a[i+1][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            if(abs(c[j][i])>1e-8)
            {
                for(int k=1;k<=n;k++) swap(c[i][k],c[j][k]);
                swap(b[i],b[j]);
            }
        }
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            double rate=c[j][i]/c[i][i];
            for(int k=i;k<=n;k++) c[j][k]-=c[i][k]*rate;
            b[j]-=b[i]*rate;
        }
    }
    for(int i=1;i<n;i++) printf("%.3f ",b[i]/c[i][i]);
    printf("%.3f\n",b[n]/c[n][n]);
    return 0;
}

三、高斯消元解异或方程组

int Guass()
{
    int max_r,col,k;
    free_num=0;
    for(k=0,col=0;k<equ&&col<var;k++,col++)
    {
        max_r=k;
        for(int i=k+1;i<equ;i++)
        {
            if(abs(a[i][col])>abs(a[max_r][col])) max_r=i;
        }
        
        if(a[max_r][col]==0)
        {
            k--;
            free_x[free_num++]=col;
            continue;
        }
        
        if(max_r!=k)
        {
            for(int j=col;j<var+1;j++)
                swap(a[k][j],a[max_r][j]);
        }
        
        for(int i=k+1;i<equ;i++)
        {
            if(a[i][col]!=0)
            {
                for(int j=col;j<var+1;j++)
                    a[i][j]^=a[k][j];
            }
        }
    }
    
    for(int i=k;i<equ;i++)
        if(a[i][col]!=0) return -1;
    
    if(k<var) return var-k;
    
    for(int i=var-1;i>=0;i--)
    {
        x[i]=a[i][col];
        for(int j=i+1;j<var;j++)
        {
            x[i]^=(a[i][j]&&x[j]);
        }
    }
    return 0;
}

int mj(void)
{
    int t=Gauss();
    if(t==-1)
    {
        return -1;
    }
    else if(t==0)
    {
        int ans=0;
        for(int i=0;i<n*n;i++)
        {
            ans+=x[i];
        }
        return ans;
    }
    else
    {
        int ans=0x3f3f3f3f;
        int tot=(1<<t);
        for(int i=0;i<tot;i++)
        {
            int cnt=0;
            for(int j=0;j<t;j++)
            {
                if(i&(1<<j))
                {
                    x[free_x[j]]=1;
                    cnt++;
                }
                else x[free_x[j]]=0;
            }
            
            for(int j=var-t-1;j>=0;j--)
            {
                int index;
                for(index=j;index<var;index++)
                {
                    if(a[j][index]) break;
                }
                x[idnex]=a[j][var];
                for(int l=index+1;l<var;l++)
                {
                    if(a[j][l])
                        x[idnex]^=x[l];
                }
                cnt+=x[index];
            }
            ans=min(ans,cnt);
        }
        return ans;
    }
}

POJ1681

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=300;
int equ,var;
int a[maxn][maxn];
int x[maxn];
int free_x[maxn];
int free_num;
int n;
//考虑有 n*n 个多项式，每一个多项式涉及到上下左右以及自身的五个变量

//对于某个格子，对其涂两次相当于没涂，涂三次相当于涂一次
//所以只有涂0次和1次之分
void init()
{
    memset(a,0,sizeof(a));
    memset(x,0,sizeof(x));
    equ=n*n;
    var=n*n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            int t=i*n+j;
            a[t][t]=1;
            if(i>0) a[(i-1)*n+j][t]=1;
            if(i<n-1) a[(i+1)*n+j][t]=1;
            if(j>0) a[i*n+j-1][t]=1;
            if(j<n-1) a[i*n+j+1][t]=1;
        }
}

int Guass()
{
    int max_r,col,k;
    free_num=0;
    for(k=0,col=0;k<equ&&col<var;k++,col++)
    {
        max_r=k;
        for(int i=k+1;i<equ;i++)
        {
            if(abs(a[i][col])>abs(a[max_r][col])) max_r=i;
        }

        if(a[max_r][col]==0)
        {
            k--;
            free_x[free_num++]=col;
            continue;
        }

        if(max_r!=k)
        {
            for(int j=col;j<var+1;j++)
                swap(a[k][j],a[max_r][j]);
        }

        for(int i=k+1;i<equ;i++)
        {
            if(a[i][col]!=0)
            {
                for(int j=col;j<var+1;j++)
                    a[i][j]^=a[k][j];
            }
        }
    }

    for(int i=k;i<equ;i++)
        if(a[i][col]!=0) return -1;

    if(k<var) return var-k;

    for(int i=var-1;i>=0;i--)
    {
        x[i]=a[i][col];
        for(int j=i+1;j<var;j++)
        {
            x[i]^=(a[i][j]&&x[j]);
        }
    }
    return 0;
}

int mj(void)
{
    int t=Guass();
    if(t==-1)
    {
        return -1;
    }
    else if(t==0)
    {
        int ans=0;
        for(int i=0;i<n*n;i++)
        {
            ans+=x[i];
        }
        return ans;
    }
    else
    {
        int ans=0x3f3f3f3f;
        int tot=(1<<t);
        for(int i=0;i<tot;i++)
        {
            int cnt=0;
            for(int j=0;j<t;j++)
            {
                if(i&(1<<j))
                {
                    x[free_x[j]]=1;
                    cnt++;
                }
                else x[free_x[j]]=0;
            }

            for(int j=var-t-1;j>=0;j--)
            {
                int index;
                for(index=j;index<var;index++)
                {
                    if(a[j][index]) break;
                }
                x[index]=a[j][var];
                for(int l=index+1;l<var;l++)
                {
                    if(a[j][l])
                        x[index]^=x[l];
                }
                cnt+=x[index];
            }
            ans=min(ans,cnt);
        }
        return ans;
    }
}

char str[maxn][maxn];
int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        init();
        for(int i=0;i<n;i++)
        {
            scanf("%s",str[i]);
            for(int j=0;j<n;j++)
            {
                if(str[i][j]=='y')
                    a[i*n+j][n*n]=0;
                else a[i*n+j][n*n]=1;
            }
        }
        int k=mj();
        if(k==-1) printf("inf\n");
        else printf("%d\n",k);
    }
    return 0;
}

四、解同余方程组：
几乎与解整数方程组一样：
POJ2947

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn=400;
const int mod=7;
int equ,var;
int a[maxn][maxn];
int x[maxn];
int free_x[maxn];
int free_num;
int n;
map<string,int>mp;
int gcd(int a,int b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}

int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}

int inv(int a)
{
    if(a==1) return 1;
    return (mod-mod/a)%mod*inv(mod%a);
}

void init(void)
{
    mp["MON"]=1;
    mp["TUE"]=2;
    mp["WED"]=3;
    mp["THU"]=4;
    mp["FRI"]=5;
    mp["SAT"]=6;
    mp["SUN"]=7;
}

int Guass(int equ,int var)
{
    int max_r,k,col;
    for(k=0,col=0;k<equ&&col<var;k++,col++)
    {
        max_r=k;
        for(int i=k+1;i<equ;i++)
            if(abs(a[i][col])>abs(a[max_r][col])) max_r=i;

        if(a[max_r][col]==0)
        {
            k--;
            continue;
        }

        if(max_r!=k)
            for(int i=col;i<=var;i++)
                swap(a[k][i],a[max_r][i]);
        for(int i=k+1;i<equ;i++)
        {
            if(a[i][col]!=0)
            {
                int LCM=lcm(a[i][col],a[k][col]);
                int ta=LCM/abs(a[i][col]);
                int tb=LCM/abs(a[k][col]);
                if(a[i][col]*a[k][col]<0) tb=-tb;
                for(int j=col;j<=var;j++)
                {
                    a[i][j]=((a[i][j]*ta-a[k][j]*tb)%mod+mod)%mod;
                }
            }
        }
    }

    for(int i=k;i<equ;i++)
    {
        if(a[i][col]!=0) return -1;
    }

    if(k<var) return var-k;

    for(int i=var-1;i>=0;i--)
    {
        int temp=a[i][var];
        for(int j=i+1;j<var;j++)
        {
            if(a[i][j]!=0)
            {
                temp-=a[i][j]*x[j];
                temp=(temp%mod+mod)%mod;
            }
        }
        x[i]=(temp*inv(a[i][i]))%mod;
    }
    return 0;

}

int main(void)
{
    int n,m;
    init();
    while(scanf("%d%d",&n,&m),n||m)
    {
        memset(a,0,sizeof(a));
        char str1[10],str2[10];
        int k;
        for(int i=0;i<m;i++)
        {
            scanf("%d%s%s",&k,str1,str2);
            a[i][n]=((mp[str2]-mp[str1]+1)%mod+mod)%mod;
            int t;
            for(int j=1;j<=k;j++)
            {
                scanf("%d",&t);
                a[i][--t]++;
                a[i][t]%=mod;
            }
        }

        int ans=Guass(m,n);
        if(ans==0)
        {
            for(int i=0;i<n;i++)
                if(x[i]<=2) x[i]+=7;
            for(int i=0;i<n-1;i++)
            {
                printf("%d ",x[i]);
            }
            printf("%d\n",x[n-1]);
        }
        else if(ans==-1)
        {
            printf("Inconsistent data.\n");
        }
        else printf("Multiple solutions.\n");


    }
    return 0;
}