线性基

数学

作业部落链接：https://www.zybuluo.com/xzyxzy/note/1076707

前言

网上优秀博客：https://blog.sengxian.com/algorithms/linear-basis
机房大佬们的总结 yyb%yl%zsy orz

一、理解

所谓基大概就是指
在一个集合内定义一种运算，用基中的元素可以运算出所有用集合中的元素运算的结果
可以理解成基是一个集合的。。浓缩？

然后线性基呢就是这个运算是异或运算

二、性质

线性基中以每一位为最高位的1的数至多只有一个
所以把一个元素加入线性基中，那么

    if(x&(1<<j))
    {
        if(!p[j]){p[j]=x;break;}//一定要break！！
        else x^=p[j];
    }

三、题目

• ※【模板】线性基 https://www.luogu.org/problemnew/show/P3812
• [BeiJing2011] 元素 http://www.lydsy.com/JudgeOnline/problem.php?id=2460
• [CQOI2013] 新Nim游戏 https://www.luogu.org/problemnew/show/P4301
• ※[WC2011] 最大XOR和路径 https://www.luogu.org/problemnew/show/P4151
• [SCOI2016] 幸运数字 https://www.luogu.org/problemnew/show/P3292
• [BZOJ3811] 玛里苟斯 http://www.lydsy.com/JudgeOnline/problem.php?id=3811
• [BZOJ2844] albus就是要第一个出场 http://www.lydsy.com/JudgeOnline/problem.php?id=2844
• ※[HDU2949] XOR https://vjudge.net/problem/HDU-3949
• ※2018.3.16考试题T1
• ※2018.3.22考试题T1

四、应用

• 求最大异或和
• 求K小异或和

一个技巧

• 求1-n路径最大异或值就是任意一条1到n的路径异或上图中的一些环得到的

代码

最大异或和（较简单【模板】线性基）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define ll long long
using namespace std;
ll read()
{
    char ch=getchar();ll h=0,t=1;
    while(ch!='-'&&(ch>'9'||ch<'0'))ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
    return h*t; 
}
ll N,A[70],ans;
int main()
{
    N=read();
    for(int i=1;i<=N;i++)
    {
        ll x=read();
        for(int j=63;j>=0;j--)
            if(x&(1LL<<j))
            {
                if(!A[j]){A[j]=x;break;}
                else x^=A[j];
            }
    }
    for(int i=63;i>=0;i--)
        if((ans^A[i])>ans)ans^=A[i];
    printf("%lld\n",ans);
    return 0;
}

K小异或和（比较难以理解，纠结了一个晚上，想通了[HDU2949] XOR）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define ll long long
using namespace std;
ll read()
{
    char ch=getchar();ll h=0,t=1;
    while(ch!='-'&&(ch>'9'||ch<'0'))ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
    return h*t; 
}
ll T,p[100],Q[100],cnt,N,M,CC=0;
void Insert(ll x)
{
    for(ll i=63;i>=0;i--)
    {
        if(!(x>>i))continue;
        if(!p[i]){p[i]=x;return;}
        else x^=p[i];
    }
    CC=1;//表示线性基可以异或出０
}
void Rebuild()
{
    for(ll i=63;i>=0;i--)
        for(ll j=i-1;j>=0;j--)
            if(p[i]&(1LL<<j))
                p[i]^=p[j];
  /*
    重建线性基，使得p[i]某非最高位上有1当且仅当p[该位]=0
    使得能够保证异或上p[i]一定会使答案增大
   */
    for(ll i=0;i<=63;i++)
        if(p[i])Q[cnt++]=p[i];
}
void Query(ll k)
{
    if(k>=(1LL<<cnt)){puts("-1");return;}//超过所有能够异或出来的结果个数 (线性基中cnt个元素选或者不选)
    ll res=0;
    for(ll i=cnt-1;i>=0;i--)
        if(k&(1LL<<i))res^=Q[i];
    /*
      在线性基Q[0]~Q[cnt-1]中,从小到大是
      Q[0],Q[1],Q[1]^Q[0],Q[2],Q[2]^Q[0],Q[2]^Q[1],Q[2]^Q[0]^Q[1].....
      所以第k大的组成元素就是所有k的二进制位上的数的异或和
     */
    printf("%lld\n",res);
}
int main()
{
    T=read();
    for(ll w=1;w<=T;w++)
    {
        N=read();cnt=0;CC=0;
        memset(p,0,sizeof(p));
        memset(Q,0,sizeof(Q));
        for(ll i=1;i<=N;i++)Insert(read());
        Rebuild();
        M=read();
        printf("Case #%lld:\n",w);
        for(ll i=1;i<=M;i++)
        {
            ll k=read()-CC;//查询第k小异或和
            if(!k)puts("0");
            else Query(k);
        }
    }
    return 0;
}