【知识点】高斯消元&线性基

高斯消元：

解$n$元一次方程组的通用方法，大部分时候用于解决没有明显转移顺序的dp。

考虑将方程组列成一个$n imes (n+1)$的矩阵$A$，然后依次枚举每一个未知数$j$（第$j$列）：

从上往下找到第一个$i$，满足$igeq j,A_{i,j} eq 0$。
如果找不到则该方程组无解，退出。否则把第$i$行与第$j$行交换。
对于任意$k eq j$，用第$j$行消第$k$行，使其满足$A_{k,j}=0$。

显然最后消出的是一个对角线矩阵（只在$A_{i,i}$处不为0），此时方程组的解$x_{i}=frac{A_{i,n+1}}{A_{i,i}}$。

复杂度$O(n^{3})$。

#include<bits/stdc++.h>
#define maxn 505
#define maxm 500005
#define inf 0x7fffffff
#define ll long long
#define rint register int
#define debug(x) cerr<<#x<<": "<<x<<endl
#define fgx cerr<<"--------------"<<endl
#define dgx cerr<<"=============="<<endl

using namespace std;
int n; double A[maxn][maxn];

inline int read(){
    int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}

inline bool Gauss(){
    for(int j=1;j<=n;j++){
        for(int i=j;i<=n;i++){
            if(A[i][j]==0) continue;
            for(int k=1;k<=n+1;k++) swap(A[i][k],A[j][k]); 
            break;
        }
        if(A[j][j]==0) return 0;
        for(int i=1;i<=n;i++){
            if(i==j || A[i][j]==0) continue;
            double x=A[i][j]/A[j][j];
            for(int k=1;k<=n+1;k++) A[i][k]-=A[j][k]*x;
        }
    }
    return 1;
}

int main(){
    n=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
            A[i][j]=read();
    if(!Gauss()) printf("No Solution
");
    else for(int i=1;i<=n;i++) printf("%.2lf
",A[i][n+1]/A[i][i]);
    return 0;
}

高斯消元

线性基：

用若干个线性基底表示一个向量空间，一般用来解决异或问题。

例如：你有一个序列A，支持插入操作和查询操作，每次询问在A中选一个子集的最大异或和是多少。

考虑把序列中的每个数拆成m位二进制，构成一个$n imes m$的01矩阵，我们只要把这个矩阵消成一个上三角矩阵就行了。

用高斯消元写的话每次插入都要重构一遍，不够优秀。

考虑不需要重构的支持插入的做法，设当前插入的数为x，从高位到低位枚举二进制位p：

如果x在p这一位为0则跳过。
如果x在p这一位不为0且$B_{p}$有值，则令$xoplus B_p$。
否则，令$B_{p}=x$，结束枚举。

这样消出的是一个可能有重复列的上三角矩阵。

如果希望消出一个没有重复列的上三角矩阵，只需要在结束枚举时：

对于所有$i<p$，用$B_i$更新$B_{p}$，使$B_p$与$B_i$没有重复列。
对于所有$i>p$，用$B_{p}$更新$B_{i}$，使$B_i$与$B_p$没有重复列。

复杂度$O(nlog{a_{i}})$。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 100005
#define maxm 50
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll N,A[maxn],p[maxm+5];
inline ll read(){
    ll x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
int main(){
    N=read(); for(ll i=1;i<=N;i++) A[i]=read();
    for(ll i=1;i<=N;i++) for(ll j=maxm;j>=0;j--)
        if(A[i]&(1LL<<j)){
            if(!p[j]){ p[j]=A[i];
                for(ll k=j-1;k>=0;k--) if(p[k]&&(p[j]&(1LL<<k))) p[j]^=p[k];
                for(ll k=j+1;k<=maxm;k++) if(p[k]&(1LL<<j)) p[k]^=p[j];
            break; } else A[i]^=p[j];
        } ll ans=0;
    for(ll i=maxm;i>=0;i--)
        if((ans^p[i])>ans) ans^=p[i];
    printf("%lld
",ans);    
    return 0;
}

线性基

树上高斯消元：

设$f_i =a_i f_{father_{i}}+b_i$，从下往上递推即可。