暑假练过线性基，当时学习了线性基在博弈，图上异或计数的应用，这段时间又做了几道线性代数的题，一起总结一下。
$1.bzoj 3105$
代码很简单，将数从大到小排序后一个个再插入线性基，证明要用拟阵，不会，暂时也不打算去学。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 155; const double eps = 1e-8; struct Linear_Basis{ int p[35],cnt; void init() { memset(p,0,sizeof(p)); cnt=0; } bool Insert(int x) { for(int i=31;i>=0;i--) { if((x>>i) & 1) { if(!p[i]) { p[i]=x; break; } x^=p[i]; } } if(x>0) cnt++; return (x>0); } }sol; int a[105]; int main() { int n;scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1);reverse(a+1,a+n+1); sol.init(); ll ans=0; for(int i=1;i<=n;i++) { ans+=a[i]; int f = sol.Insert(a[i]); if(f) ans-=a[i]; } printf("%lld\n",ans); return 0; }
$2.bzoj 2844$
题意:给$x$和$n$个数,求在这$n$个数张成的线性空间中，$x$是从小到大的第一次出现的位置。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100005; const int INF = 1000000007; const int mod = 10086; struct Linear_Basis{ int p[40]; int cnt; bool flag; void init() { memset(p,0,sizeof(p)); cnt=0; } bool Insert(int x) { for(int i=31;i>=0;i--) { if((x>>i) & 1) { if(!p[i]) { p[i]=x; break; } x^=p[i]; } } if(x>0) cnt++; return (x>0); } }sol; int vec[40]; int main() { int n,m;scanf("%d",&n); sol.init(); for(int i=1;i<=n;i++) { int x;scanf("%d",&x); sol.Insert(x); } scanf("%d",&m); ll ans=0; int tot=0; for(int i=0;i<=31;i++) { if(((m>>i) & 1) && sol.p[i]>0) { ans += (1ll<<tot)%mod; ans %= mod; } if(sol.p[i]>0) tot++; } for(int i=1;i<=n-sol.cnt;i++) { ans=ans*2ll%mod; } ans++;ans%=mod; printf("%lld\n",ans); return 0; }
$3.bzoj 3237,bzoj 3563,bzoj 3569$
三道本质一样的题，先从图中找出一个生成树，生成树的边称为树边，其余边成为非树边，非树边随机权值，树边的权值是与该树边共顶点的非树边权值异或和。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100005; const int INF = 1000000007; struct node { int nxt,to; }; node e[500005]; int head[maxn],tot; bool vis[maxn]; int b[500005],a[maxn]; void add(int u,int v) { e[++tot].to=v;e[tot].nxt=head[u];head[u]=tot; } void dfs0(int u,int fa) { vis[u]=1; for(int i=head[u];i;i=e[i].nxt) { int v = e[i].to; if(!vis[v]) { dfs0(v,u); } else { b[i]=rand()%INF+1; a[u]^=b[i]; a[v]^=b[i]; } } } void dfs1(int u,int fa) { vis[u]=1; for(int i=head[u];i;i=e[i].nxt) { int v = e[i].to; if(vis[v]) continue; dfs1(v,u); b[i]^=a[v]; a[u]^=a[v]; } } struct Linear_Basis{ int p[33],cnt; void init() { cnt=0; memset(p,0,sizeof(p)); } bool Insert(int x) { for(int i=31;i>=0;i--) { if((x>>i) & 1) { if(!p[i]) { p[i]=x; break; } x^=p[i]; } } if(x>0) cnt++; return (x>0); } }sol; int main() { srand(19491001); tot=0; int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v;scanf("%d%d",&u,&v); if(u>v) swap(u,v); add(u,v); } dfs0(1,-1); memset(vis,0,sizeof(vis)); dfs1(1,-1); int q;scanf("%d",&q); int ans=0; while(q--) { int k;scanf("%d",&k); sol.init(); int f=1; for(int i=1;i<=k;i++) { int id;scanf("%d",&id); //printf("x = %d\n",id^ans); if(sol.Insert(b[(id^ans)])==0) { f=0; } } if(f) { printf("Connected\n"); } else printf("Disconnected\n"); if(f) ans++; //printf("end : ans = %d\n",ans); } return 0; }
$4.bzoj 3811$
神题，还不会。
原文：https://www.cnblogs.com/ArcherLwz/p/14008030.html