线性代数
高斯消元法求解线性方程组
高斯消元法是求解线性方程组的经典算法，还可以用于行列式计算、求矩阵的逆。
部分代码 From「SDOI2006」线性方程组
double a[N][N];//a[i][j] 表示第 i 个方程中第 j 个元的系数，a[i][n+1] 为等号右侧的常数项
void Gauss(){
for(int i=1;i<=n;i++){
//当前消第 i 个元
//找第 i 个元系数绝对值最大的行 m
int mxo=i;
for(int j=1;j<=n;j++){
if(fabs(a[j][j])>eps&&j<i)continue;
if(fabs(a[j][i])>fabs(a[mxo][i]))mxo=j;
}
//换第 i 行和第 m 行，使得交换后第 i 行第 i 个系数最大
for(int j=1;j<=n+1;j++)
swap(a[i][j],a[mxo][j]);
if(fabs(a[i][i])<eps)continue;//无解或有无数解
for(int j=1;j<=n;j++){//在每一个方程中消元
if(i==j)continue;
double tmp=a[j][i]/a[i][i];//令 tmp 为当前行第 i 个元系数与第 i 行第 i 个元系数的比值
for(int k=i;k<=n+1;k++)//1~i-1 为 0，可以从 i 开始
a[j][k]-=a[i][k]*tmp;
}
}
}
理论上 n 个方程出现 n 个元的方程组有定解。
若出现系数全 0 且常数项不为 0，则为无解（方程间矛盾）。
若出现系数全 0 且常数项为 0，则有无数解（n 个方程中有等价的）。
否则矩阵变为
\[\left[\begin{array}{c} k_1 & 0 & 0 & 0 & \text{...} & v_1 \\ 0 & k_2 & 0 & 0 & \text{...} & v_2 \\ 0 & 0 & k_3 & 0 & \text{...} & v_3 \\ \text{...} & \text{...} & \text{...} & \text{...} & \text{...} & \text{...} \\ 0 & 0 & 0 & k_n & \text{...} & v_n \end{array} \right] \]消去系数可得到简化阶梯形矩阵
\[\left[\begin{array}{c} 1 & 0 & 0 & 0 & \text{...} & v_1/k_1 \\ 0 & 1 & 0 & 0 & \text{...} & v_2/k_2 \\ 0 & 0 & 1 & 0 & \text{...} & v_3/k_3 \\ \text{...} & \text{...} & \text{...} & \text{...} & \text{...} & \text{...} \\ 0 & 0 & 0 & 1 & \text{...} & v_n/k_n \end{array} \right] \]线性基
高斯消元法。
部分代码 From 「JLOI2015」装备购买
#define ld long double
ld a[N][N];
int cnt;//cnt 表示已求出的线性基数量
for(int i=1;i<=m;i++){//最多买 m 件装备
int now=0;//在为求出的方程中找存在第 i 个元且常数项最小的
for(int j=cnt+1;j<=n;j++){
if(fabs(a[j][i])>eps&&(now==0||w[j]<w[now]))now=j;
}
if(now==0)continue;//可由其它方程表示出（非线性基）
++cnt;
ans+=w[now];
for(int k=1;k<=m;k++)
swap(a[now][k],a[cnt][k]);//交换当前第 cnt 行和后面的第 now 行
swap(w[now],w[cnt]);
for(int j=1;j<=n;j++){//与高斯消元同
if(j!=cnt&&fabs(a[j][i])>eps){
ld t=a[j][i]/a[cnt][i];
for(int k=i;k<=m;k++)
a[j][k]-=a[i][k]*t;
}
}
}
异或线性基
贪心法一般更实用，如下。
ll base[55],ans;
bool insert(ll x){
for(int i=50;i>=0;i--)
if(x>>i&1){
if(base[i])x^=base[i];
else{
base[i]=x;
return 1;
}
}
return 0;
}