以前就学了高斯消元，但是学得零零散散很混乱，有必要系统地总结一下了。
高斯消元
学习博客：https://www.cnblogs.com/candy99/p/6653743.html
模板题：洛谷P3389
#include<bits/stdc++.h> using namespace std; const int N=100+10; const double eps=1e-8; int n; double c[N][N],b[N]; bool Gauss() { int r=0; for (int i=1;i<=n;i++) { for (int j=i;j<=n;j++) if (fabs(c[j][i])>eps) { for (int k=1;k<=n;k++) swap(c[i][k],c[j][k]); swap(b[i],b[j]); } if (fabs(c[i][i])<eps) continue; //消元结束 r++; //矩阵的秩 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; } } if (r<n) return 0; //有多解 return 1; //唯一解 } int main() { cin>>n; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) scanf("%lf",&c[i][j]); scanf("%lf",&b[i]); } if (!Gauss()) puts("No Solution"); else for (int i=1;i<=n;i++) printf("%.2lf ",b[i]/c[i][i]); return 0; }
POJ-2947
高斯消元解同余方程组模板题，写了可以当高斯消元全情况判断的模板。注意判断多解，无解，唯一解的情况。另外注意输入的时候要模7。
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; const int N=300+10; int n,m; char s[N]; int c[N][N],b[N]; int power(int x,int p) { int ret=1; for (;p;p>>=1) { if (p&1) ret=(ret*x)%7; x=(x*x)%7; } return ret; } int inv(int x) { return power(x,7-2); } void Gauss() { int r=0; for (int i=1;i<=n;i++) { int j=r+1; while (j<=m && c[j][i]==0) j++; //从下面方程找一个第i位不为0的 if (j==m+1) continue; //不存在第i位不为0的方程 r++; //矩阵的秩 for (int k=1;k<=n;k++) swap(c[r][k],c[j][k]); //存在第i位不为0的方程，交换上去 swap(b[r],b[j]); for (int j=1;j<=m;j++) { //以r方程回代m个方程 if (r==j) continue; int rate=c[j][i]%7*inv(c[r][i])%7; for (int k=i;k<=n;k++) c[j][k]-=c[r][k]*rate,c[j][k]%=7,c[j][k]=(c[j][k]+7)%7; b[j]-=b[r]*rate,b[j]%=7,b[j]=(b[j]+7)%7; } } for (int i=1;i<=m;i++) if (b[i]) { //判断无解情况 bool ok=0; for (int j=1;j<=n;j++) if (c[i][j]) { ok=1; break; } if (!ok) { puts("Inconsistent data."); return; } } if (r<n) { puts("Multiple solutions."); return; } //有解但多解 for (int i=1;i<=n;i++) b[i]=b[i]%7*inv(c[i][i])%7; //唯一解求解 for (int i=1;i<=n;i++) printf("%d ",b[i]<3 ? b[i]+7 : b[i]); puts(""); } int num(char *s) { if (s[0]=='M') return 1; if (s[0]=='W') return 3; if (s[0]=='F') return 5; if (s[0]=='T') if (s[1]=='U') return 2; else return 4; if (s[0]=='S') if (s[1]=='A') return 6; else return 7; } //POJ-2947 高斯消元解同余方程组 int main() { while (scanf("%d%d",&n,&m)==2 && n) { for (int i=1;i<=m;i++) { memset(c[i],0,sizeof(c[i])); b[i]=0; //清空方程数组 int t,x,y; char s1[10],s2[10]; scanf("%d%s%s",&t,s1,s2); x=num(s1); y=num(s2); for (int j=1;j<=t;j++) { //建立同余方程 int tp; scanf("%d",&tp); c[i][tp]++; } b[i]=((y-x+1)%7+7)%7; for (int j=1;j<=n;j++) c[i][j]%=7; } Gauss(); } return 0; }
POJ-2065
跟POJ2947差不多甚至还要更简单些，注意除法变成逆元随时取模即可。
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; const int N=100+10; int n,P; char s[N]; int c[N][N],b[N]; int power(int x,int p) { int ret=1; for (;p;p>>=1) { if (p&1) ret=(ret*x)%P; x=(x*x)%P; } return ret; } int inv(int x) { return power(x,P-2); } void Gauss() { for (int i=1;i<=n;i++) { for (int j=i;j<=n;j++) if (abs(c[j][i])>0) { 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]%P*inv(c[i][i])%P; for (int k=i;k<=n;k++) c[j][k]-=c[i][k]*rate,c[j][k]%=P,c[j][k]=(c[j][k]+P)%P; b[j]-=b[i]*rate,b[j]%=P,b[j]=(b[j]+P)%P; } } } void equation() { for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) c[i][j]=power(i,j-1); b[i]=(s[i]=='*') ? 0 : (s[i]-'a'+1); } } int main() { int T; cin>>T; while (T--) { scanf("%d",&P); scanf("%s",s+1); n=strlen(s+1); equation(); Gauss(); for (int i=1;i<=n;i++) printf("%d ",b[i]%P*inv(c[i][i])%P); printf(" "); } return 0; }
BZOJ-1770
线性基
推荐博客：https://blog.sengxian.com/algorithms/linear-basis
https://blog.csdn.net/litble/article/details/78820648
上面两位大佬讲得炒鸡好，线性基的内容也大抵如此了。
模板题：HDU-3949
求集合子集异或值第K小（去掉重复数）。思路和代码都是抄上面大佬的，当作模板了。
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; typedef long long LL; int n,m; bool have0; LL cnt,a[N],b[70],v[70]; void prepare() { //求a[1-n]得线性基放到v数组 int r=0; memset(b,0,sizeof(b)); for (int i=1;i<=n;i++) { for (int j=60;j>=0;j--) { if (!(a[i]&(1LL<<j))) continue; //该位置为0直接跳过 if (b[j]) a[i]^=b[j]; //该位置已经有数 else { ++r; b[j]=a[i]; //插入成功 for (int k=j-1;k>=0;k--) if (b[k]&&((b[j]>>k)&1)) b[j]^=b[k]; for (int k=j+1;k<=60;k++) if ((b[k]>>j)&1) b[k]^=b[j]; break; //同时为了维护一个对角矩阵，要先用下面的行消自己，再用自己消上面的行。 } } } have0=(r!=n); cnt=0; for (int i=0;i<=60;i++) if (b[i]) v[++cnt]=b[i]; //得到线性基 } LL query(LL k) { if (have0) k--; //因为这种方法算的是非0第k小，所以存在0的话就得减一 if (k>=(1LL<<cnt)) return -1; //这里要注意： 到这里已经排除0的情况了，那么线性基的数不能一个不取 LL ret=0; for (int i=1;i<=cnt;i++) if (k&(1LL<<(i-1))) ret^=v[i]; //按k的二进制表示取数 return ret; } int main() { int T,kase=0; cin>>T; while (T--) { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); prepare(); scanf("%d",&m); printf("Case #%d: ",++kase); for (int i=1;i<=m;i++) { int x; scanf("%d",&x); printf("%lld ",query(x)); } } return 0; }
BZOJ-2844
求集合某个子集异或值得名次（不去重复数）。我们先不考虑重不重复这个事，先想去掉重复得情况下，某个数x得名次是多少？网上大佬都是一笔带过，蒟蒻愣是一时半会没想明白。其实求名次这个操作就是求第K小值这个操作逆过来，但是我们要注意到因为线性基的性质，线性基异或成某个数的方案是唯一的，也就是说线性基异或出来的某个数x和异或得到x的组合是一一对应的，这就为我们做这个逆操作提供了方向。我们只要看看x到底由哪些线性基组合而成，然后按照位置计算权值累加起来即可。例如线性基是{1,4,8} 然后我们的x是9，我们发现9=1+8，x里面有第1位和第3位，那它的rank就是1<<0+1<<2=5。然后再考虑重复的个数即可，重复个数已经有很多证明了其实就是每个数会重复恰好2^n-cnt次（包括0），然后加1即可。
这里有一个思维的小细节：其实按照我上面说的计算rank的方法是从1开始算的，但是我们要求的其实是rank-1，但是因为我们还没算0，所以+1又恰好等于rank。例如上面的9的rank在所有不重复组合{0,1,4,5,8,9} 中排第6，(rank-1)*(2^n-cnt)+1就是答案了。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; const int MOD=10086; typedef long long LL; int n,x,ans; bool have0; LL cnt,a[N],b[70],v[70]; void prepare() { //求a[1-n]得线性基放到v数组 int r=0; memset(b,0,sizeof(b)); for (int i=1;i<=n;i++) { for (int j=30;j>=0;j--) { if (!(a[i]&(1LL<<j))) continue; //该位置为0直接跳过 if (b[j]) a[i]^=b[j]; //该位置已经有数 else { ++r; b[j]=a[i]; //插入成功 for (int k=j-1;k>=0;k--) if (b[k]&&((b[j]>>k)&1)) b[j]^=b[k]; for (int k=j+1;k<=30;k++) if ((b[k]>>j)&1) b[k]^=b[j]; break; //同时为了维护一个对角矩阵，要先用下面的行消自己，再用自己消上面的行。 } } } have0=(r!=n); cnt=0; for (int i=0;i<=30;i++) if (b[i]) v[++cnt]=i; //得到线性基 } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); prepare(); scanf("%d",&x); for (int i=1;i<=cnt;i++) if (x&(1LL<<v[i])) ans=(ans+(1LL<<(i-1)))%MOD; for (int i=1;i<=n-cnt;i++) ans=(ans+ans)%MOD; ans=(ans+1)%MOD; cout<<ans<<endl; return 0; }
BZOJ-2115
参考大佬题解：从1到n的任意一条路径上的异或和，一定可以表示为随意一条路径异或上若干环的异或和的值。所以把所有的环找出来，求出环的异或线性基，然后以随意一条路径从线性基高位开始贪心。
其实蒟蒻并没有完全理解。但是个人感觉其实并不是把所有的环都找出来了，只是用dfs把能找的都找出来了，但是基于线性基的特性（线性基的组合能表示所有的集合），其实所有环的异或都能表示出来，且根据上面路径=路径+环的结论，贪心就能得到最大值。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=5e4+10,M=1e5+10; LL n,m,num,dis[N]; LL cnt=0,head[N],nxt[M<<1],to[M<<1],len[M<<1]; void add_edge(LL x,LL y,LL z) { nxt[++cnt]=head[x]; to[cnt]=y; len[cnt]=z; head[x]=cnt; } LL k,a[M<<2],b[70],v[70]; void prepare() { //求a[1-n]得线性基放到v数组 memset(b,0,sizeof(b)); for (int i=1;i<=num;i++) { for (int j=60;j>=0;j--) { if (!(a[i]&(1LL<<j))) continue; //该位置为0直接跳过 if (b[j]) a[i]^=b[j]; //该位置已经有数 else { b[j]=a[i]; //插入成功 for (int k=j-1;k>=0;k--) if (b[k]&&((b[j]>>k)&1)) b[j]^=b[k]; for (int k=j+1;k<=60;k++) if ((b[k]>>j)&1) b[k]^=b[j]; break; //同时为了维护一个对角矩阵，要先用下面的行消自己，再用自己消上面的行。 } } } k=0; for (int i=0;i<=60;i++) if (b[i]) v[++k]=b[i]; //得到线性基 } bool vis[N]; void dfs(int x) { vis[x]=1; for (int i=head[x];i;i=nxt[i]) { int y=to[i]; if (!vis[y]) dis[y]=dis[x]^len[i],dfs(y); else a[++num]=dis[x]^len[i]^dis[y]; //返祖边：形成环 } } int main() { cin>>n>>m; for (int i=1;i<=m;i++) { LL x,y,z; scanf("%lld%lld%lld",&x,&y,&z); add_edge(x,y,z); add_edge(y,x,z); } dfs(1); prepare(); LL ans=dis[n]; for (int i=k;i;i--) if ((ans^v[i])>ans) ans=ans^v[i]; cout<<ans<<endl; return 0; }
BZOJ-3811