博客

线性基：

对一组数建立线性基得到：一组数a1,a2、、、an,其中ax：存最高位的1在第x位的元素值。

线性基作用

：线性基的子集的抑或和的 值域与原数抑或和的值域相同。

性质1：

线性基的任意子集的抑或和都不为0

构造线性基：

对原数组的每一个数p,从高位到低位扫描，找到第一位为1的，若该位上的线性基ai不存在，则ai=p,否则p=p^ai,继续扫描下一位。

像如果原数是2,3，则插入线性基中的是1,2

ll b[63], nb[63], tot=0,flag=false; //b为线性基  nb用来求第K小异或值,基线性基中数 tot为nb元素个数,flag为true表示线性基外有数

void insert(ll  x)
 { //插入
    for(int i = 62; i >= 0; i--) 
    {
        if(x & (1ll << i)) 
        {
            if(!b[i])
            {
                b[i] = x;
                return;
            }
            x ^= b[i];
        }
    }
    flag = true;
}

查询xor最大、小值：

ll Max(ll x) 
{  //求最大值
    ll res = x;
    for(int i = 62; i >= 0; i--) 
         res = max(res, res ^ b[i]);
    return res;
}

ll Min(ll x) 
{  //求最小值
    ll res = x;
    for(int i = 0; i <= 62; i++) 
        if(b[i])
            res ^= b[i];
    return res;
}

验证一个数x能否被xor出

bool fin(ll x) 
{ //验证存在性
    if(x == 0 && b[0])
        return 1;
    for(int i = 62; i >= 1; i--) 
    {
        int j = i - 1;
        if(x & (1 << j)) 
        {
            x ^= b[i];
            if(!x)
                return 1;
        }
    }
    return 0;
}

求抑或第k大

把k二进制拆分，如果k的第i位上是1，ans^=b[i]

ll b[63], nb[63], tot=0,flag=false; //b为线性基  nb用来求第K小异或值,基线性基中数 tot为nb元素个数,flag为true表示线性基外有数

void insert(ll  x)
 { //插入
    for(int i = 62; i >= 0; i--) 
    {
        if(x & (1ll << i)) 
        {
            if(!b[i])
            {
                b[i] = x;
                return;
            }
            x ^= b[i];
        }
    }
    flag = true;
}


ll Rebuild() {  //第K大
    for(int i = 62; i >= 0; i--) 
    {
         if(b[i] == 0)
             continue;
         for(int j = i - 1; j >= 0; j--) 
         {
             if(b[j] == 0)
                continue;
             if(b[i] & (1ll << j))
                b[i] ^= b[j];
         }
     }
     for(int i = 0; i <= 62; i++) 
     {
         if(b[i])
            nb[tot++] = b[i];
     }
}

ll Kth_Max(ll k) {
    if(flag)
         k--; 
    ll res = 0;
    if(k == 0)
        return 0;
    if(k >= (1ll << tot))
        return -1;
    for(int i = 62; i >= 0; i--) 
    {
        if(k & (1ll << i))
             res ^= nb[i];
    }
    return res;
}

实例

A – 元素

theme：给定n个魔石的编号和魔力值，如果一堆魔石中有子串的抑或和为0，则这堆魔石没有魔力。问最多能达到多少魔力值？

solution：按魔力值排序，依次插入线性基，如果该元素可以插入，说明该数某一为1的位有价值，则该魔石被选。

#include<bits/stdc++.h>
#define far(i,s,n) for(int i=s;i<n;++i)
typedef long long ll;
using namespace std;

ll b[63];
struct _a
{
    ll num;
    ll magic;
    bool operator<(_a b)const
    {
        return magic>b.magic;
    }
}a[2000];

void Insert(ll  x,int &flag)
 { //插入
    for(int i = 62; i >= 0; i--)
    {
        if(x & (1ll << i))
        {
            if(!b[i])
            {
                flag = 1;
                b[i] = x;
                return;
            }
            x ^= b[i];
        }
    }
}

int main()
{
    int n;
    cin>>n;
    far(i,0,n)
        scanf("%lld%lld",&a[i].num,&a[i].magic);
    sort(a,a+n);
    ll ans=0;
    far(i,0,n)
    {
        int flag=0;
        Insert(a[i].num,flag);
        if(flag)
            ans+=a[i].magic;
    }
    cout<<ans<<endl;
}

实例：求任选元素抑或和第k大

hdu3949:XOR

theme:给定n个数，q次询问，求任选元素抑或和第k大。

solution:套上面第k大模板即可，注意每组案例重置b、nb、flag、tot为0

#include<bits/stdc++.h>
#define far(i,s,n) for(int i=s;i<n;++i)
typedef long long ll;
using namespace std;

ll b[63], nb[63], tot=0,flag=false; //b为线性基  nb用来求第K小异或值,基线性基中数 tot为nb元素个数,flag为true表示线性基外有数

void Insert(ll  x)
 { //插入
    for(int i = 62; i >= 0; i--)
    {
        if(x & (1ll << i))
        {
            if(!b[i])
            {
                b[i] = x;
                return;
            }
            x ^= b[i];
        }
    }
    flag = true;
}


ll Rebuild() {  //第K大
    for(int i = 62; i >= 0; i--)
    {
         if(b[i] == 0)
             continue;
         for(int j = i - 1; j >= 0; j--)
         {
             if(b[j] == 0)
                continue;
             if(b[i] & (1ll << j))
                b[i] ^= b[j];
         }
     }
     for(int i = 0; i <= 62; i++)
     {
         if(b[i])
            nb[tot++] = b[i];
     }
}

ll Kth_Max(ll k) {
    if(flag)
         k--;
    ll res = 0;
    if(k == 0)
        return 0;
    if(k >= (1ll << tot))
        return -1;
    for(int i = 62; i >= 0; i--)
    {
        if(k & (1ll << i))
             res ^= nb[i];
    }
    return res;
}

int main()
{
    int t;
    cin>>t;
    for(int Case=1;Case<=t;++Case)
    {
        printf("Case #%d:\n",Case);
        memset(b,0,sizeof(b));
        memset(nb,0,sizeof(nb));
        tot=0,flag=false;
        int n;
        scanf("%d",&n);
        far(i,0,n)
        {
            ll x;
            scanf("%lld",&x);
            Insert(x);
        }
        Rebuild();
        int q;
        scanf("%d",&q);
        far(i,0,q)
        {
            ll k;
            scanf("%lld",&k);
            ll ans=Kth_Max(k);
            printf("%lld\n",ans);
        }
    }
}