含log(maxval)个数a0,a1,a2...,an,ai最高的为1位为i
其中能xor出的数与原数相同
构造
void merg(XXJ &a,XXJ &b,XXJ &c){ for (int i=60;i>=0;i--) a.a[i]=b.a[i]; for (int i=60;i>=0;i--) if (c.a[i]){ LL tp=c.a[i]; for (int j=60;j>=0;j--){ if (!(tp&(1LL<<j))) continue; if (!a.a[j]) {a.a[j]=tp;break;}else tp^=a.a[j]; } } }
求最大亦或和时合并线性基后由高到低枚举
for (int j=60;j>=0;j--) if ((fin^ans.a[j])>fin) fin^=ans.a[j];
寻找某数是否存在
int find(LL num){ for (int i=62;i>=0;i--) if (num&(1LL<<i)) num^=xxj[i]; return(num==0); }
————————————————————
BZOJ4568
#include <cstdio> #define LL long long int next[40001],des[40001],cnt,nd[20001],dep[20001],fa[20001][21],n; struct XXJ{ LL a[61]; }xxj[20001][21],ans; void merg(XXJ &a,XXJ &b,XXJ &c){ for (int i=60;i>=0;i--) a.a[i]=b.a[i]; for (int i=60;i>=0;i--) if (c.a[i]){ LL tp=c.a[i]; for (int j=60;j>=0;j--){ if (!(tp&(1LL<<j))) continue; if (!a.a[j]) {a.a[j]=tp;break;}else tp^=a.a[j]; } } } void addedge(int x,int y){ next[++cnt]=nd[x];des[cnt]=y;nd[x]=cnt; } void dfs(int po){ for (int p=nd[po];p!=-1;p=next[p]) if (!dep[des[p]]){ dep[des[p]]=dep[po]+1; fa[des[p]][0]=po; dfs(des[p]); } } void LCA_ini(){ for (int i=1;i<=20;i++) for (int j=1;j<=n;j++){ fa[j][i]=fa[fa[j][i-1]][i-1]; if (fa[j][i]!=0) merg(xxj[j][i],xxj[j][i-1],xxj[fa[j][i-1]][i-1]); } } void getlca(int x,int y){ if (dep[x]<dep[y]){ int t=x;x=y;y=t; } for (int i=20;i>=0;i--) if (dep[fa[x][i]]>=dep[y]){ merg(ans,ans,xxj[x][i]); x=fa[x][i]; } for (int i=20;i>=0;i--) if (fa[x][i]!=fa[y][i]){ merg(ans,ans,xxj[x][i]); merg(ans,ans,xxj[y][i]); x=fa[x][i];y=fa[y][i]; } if (x!=y){ merg(ans,ans,xxj[x][0]); merg(ans,ans,xxj[y][0]); x=fa[x][0];y=fa[y][0]; } merg(ans,ans,xxj[x][0]); } int main(){ int q; scanf("%d%d",&n,&q); for (int i=1;i<=n;i++) nd[i]=-1; for (int i=1;i<=n;i++){ LL t; scanf("%lld",&t); if (t) for (int j=60;j>=0;j--) if (t&(1LL<<j)){ xxj[i][0].a[j]=t; break; } } for (int i=1;i<n;i++){ int t1,t2; scanf("%d%d",&t1,&t2); addedge(t1,t2);addedge(t2,t1); } dep[1]=1; dfs(1); LCA_ini(); for (int i=1;i<=q;i++){ int t1,t2; scanf("%d%d",&t1,&t2); for (int i=0;i<=60;i++) ans.a[i]=0; getlca(t1,t2); LL fin=0; for (int j=60;j>=0;j--) if ((fin^ans.a[j])>fin) fin^=ans.a[j]; printf("%lld ",fin); } }
————————————————————————
用与求非线性相关组（BZOJ4004）
#include <cstdio> #include <algorithm> #define LL long long using namespace std; const LL mo=1e9+7; int bas[501]; struct data{ LL a[501]; int c; }a[501]; int mycomp(const data &a,const data&b){ return(a.c<b.c); } LL qpow(LL bas,int powe){ LL ret=1; for (;powe;bas*=bas,bas%=mo){ if (powe&1) ret*=bas,ret%=mo; powe=powe>>1; } return(ret); } int main(){ int n,m; scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%lld",&a[i].a[j]); for (int i=1;i<=n;i++) scanf("%d",&a[i].c); sort(a+1,a+n+1,mycomp); int ans=0,cnt=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (a[i].a[j]){ if (!bas[j]){ bas[j]=i; ans+=a[i].c;cnt++; break; }else{ LL tim=a[i].a[j]*qpow(a[bas[j]].a[j],mo-2)%mo; for (int k=j;k<=m;k++){ a[i].a[k]-=tim*a[bas[j]].a[k]%mo;a[i].a[k]%=mo; a[i].a[k]+=mo;a[i].a[k]%=mo; } } } printf("%d %d ",cnt,ans); }
-------------------------------------------------------
BZOJ4184
按时分治后dfs时间线段树求值
#include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> using namespace std; int cnt,next[10000001],des[10000001],xxj[101][51],ans[500001],n,m; map <int,int> mpa; map <int,int> mpb; priority_queue <int> heap; struct treenode{ int l,r,lc,rc,nd; }tr[1000001]; struct data{ int l,r,num; }sid[500001]; void build(int l,int r){ tr[++cnt].l=l;tr[cnt].r=r;tr[cnt].nd=-1; if (l==r) return; int mid=(l+r)>>1,t=cnt; tr[t].lc=cnt+1; build(l,mid); tr[t].rc=cnt+1; build(mid+1,r); } void edi(int po,int l,int r,int num){ if (tr[po].l==l&&tr[po].r==r){ next[++cnt]=tr[po].nd;des[cnt]=num;tr[po].nd=cnt; return; } int mid=(tr[po].l+tr[po].r)>>1; if (l<=mid) edi(tr[po].lc,l,min(mid,r),num); if (r>mid) edi(tr[po].rc,max(mid+1,l),r,num); } void edi(int a[],int num){ for (int i=30;i>=0;i--) if (num&(1<<i)){ if (!a[i]) {a[i]=num;return;} else num^=a[i]; } } int getans(int a[]){ int ret=0; for (int i=30;i>=0;i--) if ((ret^a[i])>ret) ret^=a[i]; return(ret); } void dfs(int po,int dep){ memcpy(xxj[dep],xxj[dep-1],sizeof(xxj[dep])); for (int p=tr[po].nd;p!=-1;p=next[p]) edi(xxj[dep],des[p]); if (tr[po].l==tr[po].r){ ans[tr[po].l]=getans(xxj[dep]); return; } dfs(tr[po].lc,dep+1); dfs(tr[po].rc,dep+1); } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ int t; scanf("%d",&t); if (t>0){ if (!mpa[t]) mpb[t]=i; mpa[t]++; heap.push(t); }else{ t*=-1; mpa[t]--; if (!mpa[t]) {sid[++cnt].l=mpb[t];sid[cnt].r=i-1;sid[cnt].num=t;} } } while (!heap.empty()){ int num=heap.top();heap.pop(); if (mpa[num]){ sid[++cnt].l=mpb[num];sid[cnt].r=n;sid[cnt].num=num; } } m=cnt; cnt=0; build(1,n); cnt=0; for (int i=1;i<=m;i++) edi(1,sid[i].l,sid[i].r,sid[i].num); dfs(1,1); for (int i=1;i<=n;i++) printf("%d ",ans[i]); }