线性基复习总结-白红宇

线性基复习总结

阅读量：5115 次

发布时间：2019-06-13

本文共 10041 字，大约阅读时间需要 33 分钟。

在八十中听lyd讲了一些奇怪的东西

(至今不理解小伙伴们为什么要去听弦图和三维凸包

不过线性基还是很有用的

因为比较简单，所以飞快的把所有题目都刷完了OwO

在东北育才听邹雨恒学长讲了一道很不错的题目，然而一直找不到提交地址

至今没找到，sad story。。

貌似当初还坑了一道HEOI的题目OwO(有时间去补补

所谓线性基，就是向量空间下的一组基底(线性无关)

求法是利用高斯消元，不难证明k维向量空间的线性基最多有k个

貌似如果不是在异或空间里，唯一的用处就是判断是否线性相关了OwO

这个东西和拟阵配合起来可以得到一些贪心的做法

如果在异或空间里，由于二进制的特殊性，问题一般就比较多样化

消法一般有两种，一种是直接消成上三角阵，一种是消成对角线阵

第一种跑得比较快，但第二种贪心起来比较价简单，也算各有利弊

这样是因为譬如1,3两个数，用第一种消法得到1,3两个线性基，然而因为3^1=2，所以贪心起来要多判断一些东西

第二种消法直接得到1,2,从大到小选线性基异或只会越来越大

同时对角阵有一个特性是有线性基的位上只有线性基的那一位为1，其余均为0

但是这里要注意没有线性基的位不一定为0，譬如只有一个数3

hdu 3949 XOR

OwO 因为一直习惯消成上三角，然后被坑了好久

消成对角线直接逐位确定就可以了，特判下0

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long LL;const int maxn=10010;int T,n,m,cnt,kase;LL a[maxn],Num[72],k;void Get_base(){    memset(Num,0,sizeof(Num));    for(int i=1;i<=n;++i){        for(int j=62;j>=0;--j){            if(a[i]>>j&1){                if(Num[j])a[i]^=Num[j];                else{                    Num[j]=a[i];                    for(int k=j-1;k>=0;--k)if(Num[k]&&Num[j]>>k&1)Num[j]^=Num[k];                    for(int k=j+1;k<=62;++k)if(Num[k]>>j&1)Num[k]^=Num[j];                    break;                }            }        }    }return;}int main(){    scanf("%d",&T);    while(T--){        scanf("%d",&n);        for(int i=1;i<=n;++i)scanf("%lld",&a[i]);        Get_base();scanf("%d",&m);cnt=0;        for(int i=0;i<=62;++i)if(Num[i])cnt++;        kase++;        printf("Case #%d:\n",kase);        while(m--){            scanf("%lld",&k);            if(cnt==n)k++;            if(k>(1LL<
          
           =0;--i){ if(Num[i]){ LL now=(1LL<<(tmp-1)); if(k>now)k-=now,ans^=Num[i]; tmp--; } }printf("%lld\n",ans); } }return 0;}

BZOJ 2115 XOR

任取一条S->T的路径d，然后利用DFS树求出所有的简单环

问题转化成求这些简单环的异或和的一个子集T，使得T的异或和与d的异或和最大

然后搞出线性基贪心就可以了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std; typedef long long LL;const int maxn=50010;int n,m,u,v;int h[maxn],cnt=0,tot=0;bool vis[maxn];LL w;LL dis[maxn];LL A[300010];struct edge{    int to,next;    LL w;}G[300010]; void add(int x,int y,LL z){++cnt;G[cnt].to=y;G[cnt].next=h[x];G[cnt].w=z;h[x]=cnt;}void DFS(int u){    vis[u]=true;    for(int i=h[u];i;i=G[i].next){        int v=G[i].to;        if(!vis[v]){            dis[v]=dis[u]^G[i].w;            DFS(v);        }else A[++tot]=dis[u]^G[i].w^dis[v];    }return;}void read(int &num){    num=0;char ch=getchar();    while(ch<'!')ch=getchar();    while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();}void Gauss(){    int to,now=1;    for(LL i=1LL<<62;i;i>>=1){        for(to=now;to<=tot;++to){            if(A[to]&i)break;        }        if(to==tot+1)continue;        swap(A[to],A[now]);        for(int j=1;j<=tot;++j){            if(j==now)continue;            if(A[j]&i)A[j]^=A[now];        }now++;    }return;} int main(){    read(n);read(m);    for(int i=1;i<=m;++i){        read(u);read(v);        scanf("%lld",&w);        add(u,v,w);add(v,u,w);    }    DFS(1);    Gauss();    LL ans=dis[n];    for(int i=1;A[i];++i){        if((ans^A[i])>ans)ans^=A[i];    }printf("%lld\n",ans);    return 0;}

CQOI 新Nim游戏

JLOI 装备购买

OwO 都是直接利用拟阵贪心，排序之后塞进线性基里就可以了

BZOJ 2844 albus就是要第一个出场

跟hdu那道题互为对偶问题，如果懒的话可以直接二分搞QAQ

考虑有n个数，消完后得到k个线性基，则xor起来会有2^k种不同的答案

不难发现每种答案的方案数为2^(n-k)

这样我们可以消成对角阵之后逐位确定就可以了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std; const int maxn=100010;const int mod=10086;int n,k,cnt,ans,tmp;int a[maxn],p[maxn];int Num[42]; void read(int &num){    num=0;char ch=getchar();    while(ch<'!')ch=getchar();    while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();}void Get_base(){    for(int i=1;i<=n;++i){        for(int j=30;j>=0;--j){            if(a[i]>>j&1){                if(Num[j])a[i]^=Num[j];                else{                    Num[j]=a[i];                    for(int k=j-1;k>=0;--k)if(Num[k]&&Num[j]>>k&1)Num[j]^=Num[k];                    for(int k=j+1;k<=30;++k)if(Num[k]>>j&1)Num[k]^=Num[j];                    break;                }            }        }    }return;} int main(){    read(n);p[0]=1;    for(int i=1;i<=n;++i)p[i]=(p[i-1]<<1)%mod;    for(int i=1;i<=n;++i)read(a[i]);    read(k);Get_base();    for(int i=0;i<=30;++i)if(Num[i])cnt++;    tmp=cnt;    for(int i=30;i>=0;--i){        if(Num[i]){            if(k>>i&1){                ans=ans+(1LL<<(tmp-1))*p[n-cnt]%mod;                ans%=mod;            }tmp--;        }    }ans++;ans%=mod;    printf("%d\n",ans);    return 0;}

BZOJ 2728 与非

不难发现这个操作可以表示二进制运算的全集

然后由于每个数可以取任意多次(lyd问我的时候我没看到这句话，就口胡说可能有一些性质把,太羞耻了呜呜

线性基就是那些运算时的等价类(即某些位无论怎么样运算都是一样的

在一个等价类的充要条件是这些位在任意数中都是一样的

之后搞出这些线性基逐位确定即可

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std; const int maxn=1010;typedef long long LL;int n,k,cnt;int fa[maxn];LL a[maxn],w[maxn];LL L,R; bool cmp(const int &a,const int &b){return a>b;}bool check(int i,int j){    for(int k=1;k<=n;++k){        int A=(a[k]>>i&1);        int B=(a[k]>>j&1);        if(A^B)return false;    }return true;}LL DFS(LL now,int len,int la){    if(now>=(1LL<<(len+1)))return 1LL<
          
           >len&1)return DFS(now-w[len],len-1,la-1)+(1LL<<(la-1)); else return DFS(now,len-1,la-1); }} int main(){ scanf("%d%d",&n,&k); scanf("%lld%lld",&L,&R); for(int i=1;i<=n;++i)scanf("%lld",&a[i]); for(int i=0;i
           
            =0;--i){ if(fa[i]==i){ for(int j=i-1;j>=0;--j)if(check(i,j))fa[j]=i; } } for(int i=k-1;i>=0;--i){ if(fa[i]==i){ w[i]|=(1LL<
            
             =0;--j)if(fa[j]==i)w[i]|=(1LL<

BZOJ 4568

因为线性基可以合并，所以显然用个奇怪的数据结构维护一下就可以了

做法有很多种，目测树链剖分+线段树会T，log太多啦

第一种做法是倍增，处理i向上2^j的点们的线性基，然后倍增合并就可以了

第二种做法是树分治，我们对于每一层重心处理每个点到这层重心的链的线性基

每次查询只需要在分治树上搞到LCA然后之后把两条链的线性基合并就可以了

(LCA是因为分治到这步的时候u和v两个点分开了，所以两条链不相交而且合起来就是u->v的链

为了省事每层重心用map记录的位置，莫名多log，然后就跑得好慢呜呜

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          using namespace std; const int maxn=20010;const int oo=0x7fffffff;typedef long long LL;int n,m,u,v,g,sum,now;int h[maxn],cnt=0;int fa[maxn],dep[maxn],f[maxn],w[maxn];bool vis[maxn];LL c[maxn];LL Ans[61],ans;struct edge{ int to,next;}G[maxn<<1];struct base{ int cnt; vector
           
            V[61]; map
            
             p; void init(int u,LL v){ for(int i=0;i<=60;++i)V[i].push_back(0); p[u]=0; for(int i=60;i>=0;--i){ if(v>>i&1){V[i][cnt]=v;break;} }return; } void Get_new(int u,int f,LL v){ int now=p[f]; for(int i=0;i<=60;++i)V[i].push_back(V[i][now]); ++cnt;p[u]=cnt; for(int i=60;i>=0;--i){ if(v>>i&1){ if(V[i][cnt])v^=V[i][cnt]; else {V[i][cnt]=v;break;} } }return; }}b[maxn]; void add(int x,int y){ ++cnt;G[cnt].to=y;G[cnt].next=h[x];h[x]=cnt;}void cmax(int &a,int b){if(b>a)a=b;}void Get_G(int u,int fa){ w[u]=1;f[u]=0; for(int i=h[u];i;i=G[i].next){ int v=G[i].to; if(vis[v]||v==fa)continue; Get_G(v,u);w[u]+=w[v]; cmax(f[u],w[v]); }cmax(f[u],sum-w[u]); if(f[u]
             
              =0;--j){ if(v>>j&1){ if(Ans[j])v^=Ans[j]; else{Ans[j]=v;break;} } } }ans=0; for(int i=60;i>=0;--i)ans=max(ans,ans^Ans[i]); printf("%lld\n",ans); } return 0;}

BZOJ 3569

OwO 鬼畜题目

做法是利用随机化，我们弄出一棵DFS树

不难发现不连通当且仅当存在一条树边，满足这条树边和所有覆盖到这条树边的非树边都被删除了

给每个非树边随机一个权值，然后树边的权值是覆盖他的非树边的权值和

那么判断是否联通就只需要判断给定边是否存在一个子集异或和为0

用线性基搞一搞就可以了，因为随机的权值所以冲突概率很小

如果不强制在线直接一发分治+并查集就可以了，每次回溯的时候撤销并查集操作

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std; const int maxn=500010;const int mod=(1<<30)-1;int n,m,q,tot,la,k,x;int fa[maxn];int vis[maxn],dep[maxn];bool check[maxn];int h[maxn],cnt=0;int Ans[42];struct edge{    int to,next;}G[maxn<<1];struct Edge{    int u,v,w;}c[maxn]; void add(int x,int y){    ++cnt;G[cnt].to=y;G[cnt].next=h[x];h[x]=cnt;}int ufs(int x){return fa[x]==x?x:fa[x]=ufs(fa[x]);}void read(int &num){    num=0;char ch=getchar();    while(ch<'!')ch=getchar();    while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();}void DFS(int u,int f){    for(int i=h[u];i;i=G[i].next){        int v=G[i].to;        if(v==f)continue;        dep[v]=dep[u]+1;        DFS(v,u);vis[u]^=vis[v];    }return;} int main(){    read(n);read(m);tot=n;    for(int i=1;i<=n;++i)fa[i]=i;    for(int i=1;i<=m;++i){        read(c[i].u);read(c[i].v);c[i].w=(rand()&mod);        int d1=ufs(c[i].u),d2=ufs(c[i].v);        if(d1!=d2){            fa[d1]=d2;tot--;check[i]=true;            add(c[i].u,c[i].v);add(c[i].v,c[i].u);        }else vis[c[i].u]^=c[i].w,vis[c[i].v]^=c[i].w;    }read(q);    if(tot!=1){        while(q--)printf("Disconnected\n");        return 0;    }DFS(1,-1);    for(int i=1;i<=m;++i){        if(check[i]){            if(dep[c[i].u]
          
           =0;--i){ if(v>>i&1){ if(Ans[i])v^=Ans[i]; else{Ans[i]=v;break;} } } } for(int i=0;i<=29;++i)if(Ans[i])cnt--; if(!cnt)printf("Connected\n"),la++; else printf("Disconnected\n"); }return 0;}

codeforces 662 A

考虑我们求出a序列的异或和S

之后令ci=ai^bi

原问题转化为是否存在c的一个子集和S的异或和为0

我们求c的线性基判断就可以了

至于有多少个嘛，前面albus那道题目已经提过了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=500010;typedef long long LL;int n;LL Num[72],ans;LL a[maxn],b[maxn],S=0;void Get_base(){	for(int i=1;i<=n;++i){		for(int j=62;j>=0;--j){			if(a[i]>>j&1){				if(!Num[j]){Num[j]=a[i];break;}				else a[i]^=Num[j];			}		}	}return;}int main(){	scanf("%d",&n);	for(int i=1;i<=n;++i)scanf("%I64d%I64d",&a[i],&b[i]);	for(int i=1;i<=n;++i)S^=a[i],a[i]^=b[i];	Get_base();	bool flag=false;int cnt=0;;	for(int i=62;i>=0;--i){		if(S>>i&1)S^=Num[i];		if(Num[i])cnt++;	}	if(S){printf("1/1");return 0;}	ans=1;	for(int i=1;i<=cnt;++i)ans<<=1;	printf("%I64d/%I64d\n",ans-1,ans);	return 0;	}