线性基学习笔记

xtx1092515503 · 2020-07-20 13:43:15 · 个人记录

如果有线性代数基础的话会更易理解。推荐配合本人的线性代数学习笔记食用。

线性基是针对某个序列生成的一个集合，它具有以下两条性质：

1. 线性基中任意选择一些数的异或值所构成的集合，等于原序列中任意选择一些数的异或值所构成的集合。

2. 线性基是满足上述条件的最小集合。

有了上面这两条性质，我们便可以得出如下几条推论：

3. 原序列中任何数，都可以由线性基中一些数异或起来得到（由性质1直接得出）

4. 线性基中不存在一组数，使得它们的异或值为0（如果存在x\operatorname{xor}y\operatorname{xor}z=0，它就等价于x\operatorname{xor}y=z，就可以删掉z使得异或集合不变，违背了性质2）

5. 线性基中不存在两组取值集合，使得它们的异或和相等（不然你把这两个集合异或在一起就会得到异或和为0的集合）

现在介绍线性基的构建方法：

我们用x_{(2)}表示x的二进制表示，用d_x表示线性基数组。

我们又有\sum\limits_{j\operatorname{mod}2\equiv1}C_k^j=\begin{cases}0\ (k=0)\\2^{k-1}\ (k>0)\end{cases}

故2^{tot-k}\times\sum\limits_{j\operatorname{mod}2\equiv1}C_k^j=\begin{cases}0\ (k=0)\\2^{tot-1}\ (k>0)\end{cases}

于是我们发现只要存在一个d_x的第i位上为1，这位上就会有2^{tot-1}种方案（即半数方案）异或值为1。而如果不存在这样一个d_x，则这位上无论如何都是0。

因此我们只需要求出所有非零的d_x \operatorname{or}在一起的结果，这个结果的非0位有2^{tot-1}种方式做出贡献。因此总答案即为(\bigvee\limits_{d_i\neq 0}d_i)\times 2^{tot-1}。

现在我们回到本题。很明显，同前几题一样，仍然可以搜出所有的环并丢入线性基中。但是这回，因为(u,v)不是唯一的，这是否意味着我们要暴力每一组(u,v)，然后到线性基中求值呢？

不需要。我们发现如果设节点i到某个指定节点的距离为dis_i的话，则u到v的距离实际上就是dis_u\operatorname{xor}dis_v。

因此我们实际上是从集合\{dis_i\}中选择任意两个值异或在一起并在线性基中求值。但是这回我们不是求线性基中所有东西的异或和了——而是求线性基中所有东西的（异或和再异或上(dis_u\operatorname{xor}dis_v)）的和。

我们可以把该集合中所有数放在一起，一起按位求值。

我们设一个tmp=\bigvee\limits_{d_i\neq 0}d_i。则tmp的第i位如果为1，则它有一半的方案为0，一半的方案为1，因此会对集合\{dis_i\}中每一对数都能产生2^{tot-1}种方案。设此集合大小为sz，则共2^{tot-1}\times\dfrac{sz(sz-1)}{2}种方案。

而如果tmp的第i位为0的话，无论如何异或和的第i位都是0，因此只有在集合\{dis_i\}选取两个第i位不同的数拼一起最终结果才是1。设\{dis_i\}中共有cnt个数第i位是1，则共有2^{tot}\times cnt\times(sz-cnt)种方案。

最终的统计答案函数：

int calc(){
    ll tmp=0;
    int ret=0,sz=v.size();
    for(int i=62;i>=0;i--)if(d[i])tmp|=d[i];
    for(int i=62;i>=0;i--){
        int cnt=0;
        for(ll j:v)cnt+=((j>>i)&1);
        if(tmp&(1ll<<i))(ret+=((1ll<<i)%mod)*((1ll<<(tot-1))%mod)%mod*((1ll*sz*(sz-1)/2)%mod)%mod)%=mod;
        else(ret+=((1ll<<i)%mod)*((1ll<<tot)%mod)%mod*(1ll*cnt*(sz-cnt)%mod)%mod)%=mod;
    }
    return ret;
}

然后只要注意这张图可能不连通，要对于每个连通块分开讨论即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n,m,head[101000],cnt,res;
ll dis[101000];
vector<ll>v;
struct lb{//linear basis?
    ll d[64];
    int tot;
    void print(){
        for(int i=0;i<=62;i++)if(d[i])printf("%d:%lld\n",i,d[i]);
    }
    void clear(){memset(d,0,sizeof(d)),tot=0;}
    lb(){memset(d,0,sizeof(d)),tot=0;}
    void operator +=(ll x){
        for(int i=62;i>=0;i--){
            if(!(x&(1ll<<i)))continue;
            if(d[i])x^=d[i];
            else{d[i]=x,tot++;break;}
        }
    }
    ll& operator [](int x){
        return d[x];
    }
    void operator +=(lb &x){
        for(int i=62;i>=0;i--)if(x[i])*this+=x[i];
    }
    friend lb operator +(lb &x,lb &y){
        lb z=x;
        for(int i=62;i>=0;i--)if(y[i])z+=y[i];
        return z;
    }
    int calc(){//calculate the number of possible xor values, from the vector v
        ll tmp=0;
        int ret=0,sz=v.size();
        for(int i=62;i>=0;i--)if(d[i])tmp|=d[i];
        for(int i=62;i>=0;i--){
            int cnt=0;
            for(ll j:v)cnt+=((j>>i)&1);
            if(tmp&(1ll<<i))(ret+=((1ll<<i)%mod)*((1ll<<(tot-1))%mod)%mod*((1ll*sz*(sz-1)/2)%mod)%mod)%=mod;
            else(ret+=((1ll<<i)%mod)*((1ll<<tot)%mod)%mod*(1ll*cnt*(sz-cnt)%mod)%mod)%=mod;
        }
        return ret;
    }
}LB;
struct node{
    int to,next;
    ll val;
}edge[400100];
void ae(int u,int v,ll w){
    edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++; 
    edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++; 
}
bool vis[100100];
void dfs(int x){
    vis[x]=true,v.push_back(dis[x]);
    for(int i=head[x];i!=-1;i=edge[i].next){
        if(!vis[edge[i].to])dis[edge[i].to]=dis[x]^edge[i].val,dfs(edge[i].to);
        else LB+=dis[x]^dis[edge[i].to]^edge[i].val;
    }
}
int main(){
    scanf("%d%d",&n,&m),memset(head,-1,sizeof(head));
    for(ll i=1,x,y,z;i<=m;i++)scanf("%lld%lld%lld",&x,&y,&z),ae(x,y,z);
    for(int i=1;i<=n;i++)if(!vis[i])dfs(i),(res+=LB.calc())%=mod,LB.clear(),v.clear();
    printf("%d\n",res);
    return 0;
}

II.【清华集训2014】玛里苟斯

当k=1的情况之前已经说过，总和是(\bigvee\limits_{d_i\neq 0}d_i)\times 2^{tot-1}。如果我们设\bigvee\limits_{d_i\neq 0}d_i=tmp的话，则是tmp\times 2^{tot-1}。然后现在因为是求期望，因此除以2^{tot}即可。则最终结果为\dfrac{tmp}{2}。

因为答案在2^{64}以内，所以tmp直接用unsigned long long存一下，然后最后一位特判到底是无小数还是输出.5即可。

此部分代码：

void calc1(){
    if(tmp&1)printf("%llu.5\n",tmp>>1);
    else printf("%llu\n",tmp>>1);
}

当k=2时，我们设tmp的第i位为b_i。则每一位上都有\dfrac{2^{tot-1}}{2^{tot}}=1/2的概率出现一个1，则总和即为\sum\limits_{i=0}^{63}b_i\times2^{i}\times (1/2)。但是我们还要平个方，于是便得到了(\sum\limits_{i=0}^{63}b_i\times2^{i-1})^2。

暴力拆开，我们要求的东西就是\sum\limits_{i=0}^{63}\sum\limits_{j=0}^{63}b_ib_j2^{i+j-2}。

则显然，只有b_i与b_j都为1的地方才能贡献出2^{i+j-2}。

但是这里又有一种情况，就是在所有a_i（即原数组）中，总有第i位同第j位相等。这就意味着第i位与第j位绑定了，它们总是相同。如果绑定了，这两者因为始终相等，概率就不是两个1/2乘在一起，而是直接一个1/2了！

我们设是否绑定为一个bool值sm来表示，如果为true就是绑定上了。则最终答案即为\sum\limits_{i=0}^{63}\sum\limits_{j=0}^{63}b_ib_j2^{i+j-2+sm}。

等等，那输出怎么办？它要求输出精确值呀！

没关系！当i+j\geq2时，结果肯定是整数；

当i+j=1时，末尾是0或0.5；

当i+j=0时，有且只有i=j=0才会出现这种情况，而此时因为i=j，所以肯定就绑定上了！因此它最终是b_0\times b_0\times2^{-1}，结尾仍是0或0.5。

所以最终结尾仍是0或0.5。

但是这又有问题了——它只保证结果小于2^{63}，但是没有保证中间结果小于2^{63}！

我们要么用double储存，要么用__int128，要么也可以用两个unsigned long long拼一起模拟__int128。

这里采取两个ull拼一起的方法。

此部分代码：

void calc2(){
    for(int i=0;i<32;i++)for(int j=0;j<32;j++){
        if(!(tmp&(1ull<<i)))continue;
        if(!(tmp&(1ull<<j)))continue;
        bool sm=true;
        for(int p=1;p<=n;p++)if(((a[p]>>i)&1)!=((a[p]>>j)&1)){sm=false;break;}
        if(i+j-2+sm<0)floa++;
        else inte+=(1ull<<(i+j-2+sm));
    }
    inte+=(floa>>1),floa&=1;
    if(floa)printf("%llu.5\n",inte);
    else printf("%llu\n",inte);
}

当k\geq 3时，因为答案小于2^{63}，你开一个3次根，结果肯定小于2^{22}。所以直接暴力枚举2^{22}种线性基的子集即可通过。当然，这里仍得使用两个ull进行拼接。

此部分代码：

void calc3(){
    for(int i=0;i<64;i++)if(d[i])arr[tot++]=i;
    for(ll i=0;i<(1llu<<tot);i++){
        ll s=0;
        for(int j=0;j<tot;j++)if(i&(1llu<<j))s^=d[arr[j]];
        ll p=0,q=1;
        for(int l=0;l<k;l++)p*=s,q*=s,p+=(q>>tot),q&=(1llu<<tot)-1;
        inte+=p,floa+=q;
        inte+=(floa>>tot),floa&=(1llu<<tot)-1;
    }
    if(floa)printf("%llu.5\n",inte);
    else printf("%llu\n",inte);
}

Part6.线性基区间修改

有的时候，我们会遇到这样的题，要你支持两种操作：

1. 区间异或上某数
2. 求区间上线性基的某种应用（即上文中介绍的线性基的诸多用法之一）

这时应该如何处理呢？

I.[Ynoi2013]无力回天NOI2017

这里就是例子之一，区间异或+区间最大异或和。

考虑到线性基只具有可加性，并不具有可修改性；故我们不能直接上线段树套线性基。

我们考虑对序列作差分——考虑令一个b_i=a_i\operatorname{xor}a_{i+1}。此时，区间修改在差分数组上就只需要修改一头一尾的值。

而如果要求区间的线性基的话，我们只需要求出差分数组的线性基，然后再加入区间末尾的一个数即可。可以发现此种线性基就等价于原本的线性基（因为线性基是异或等价的）。

于是我们只需要使用两棵线段树，一棵维护差分数组的线性基，复杂度O(n\log^2n)；一棵维护原序列的元素（因为我们最终是要加入区间末尾的那个数的），复杂度O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[50100];
struct lb{//linear basis?
    int d[32];
    void print(){
        for(int i=0;i<=29;i++)if(d[i])printf("%d:%lld\n",i,d[i]);
    }
    lb(){memset(d,0,sizeof(d));}
    void operator +=(int x){
        for(int i=29;i>=0;i--){
            if(!(x&(1ll<<i)))continue;
            if(d[i])x^=d[i];
            else{d[i]=x;break;}
        }
    }
    int& operator [](int x){
        return d[x];
    }
    void operator +=(lb &x){
        for(int i=29;i>=0;i--)if(x[i])*this+=x[i];
    }
    friend lb operator +(lb x,lb y){
        lb z=x;
        for(int i=29;i>=0;i--)if(y[i])z+=y[i];
        return z;
    }
    int num(){for(int i=29;i>=0;i--)if(d[i])return d[i];return 0;}
    int calc(int ip=0){
        for(int i=29;i>=0;i--)if((ip^d[i])>ip)ip^=d[i];
        return ip;
    }
};
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
namespace AES{//adjecent elements' segtree
    lb seg[200100];
    void build(int x,int l,int r){
        if(r-l==1){seg[x]+=a[l]^a[r];return;}
        build(lson,l,mid),build(rson,mid,r),seg[x]=seg[lson]+seg[rson];
    }
    void modify(int x,int l,int r,int P,int val){
        if(l>P||r<=P)return;
        if(r-l==1){val^=seg[x].num();seg[x]=lb();seg[x]+=val;return;}
        modify(lson,l,mid,P,val),modify(rson,mid,r,P,val),seg[x]=seg[lson]+seg[rson];
    }
    lb query(int x,int l,int r,int L,int R){
        if(L<=l&&r<=R)return seg[x];
        if(mid>=R)return query(lson,l,mid,L,R);
        if(mid<=L)return query(rson,mid,r,L,R);
        return query(lson,l,mid,L,R)+query(rson,mid,r,L,R);
    }
}
namespace OSS{//original sequence's segtree
    int seg[200100];
    void pushdown(int x){seg[lson]^=seg[x],seg[rson]^=seg[x],seg[x]=0;}
    void build(int x,int l,int r){
        if(l==r){seg[x]=a[l];return;}
        build(lson,l,mid),build(rson,mid+1,r);
    }
    void modify(int x,int l,int r,int L,int R,int val){
        if(l>R||r<L)return;
        if(L<=l&&r<=R){seg[x]^=val;return;}
        pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val);
    }
    int query(int x,int l,int r,int P){
        if(l==r)return seg[x];
        pushdown(x);
        return P<=mid?query(lson,l,mid,P):query(rson,mid+1,r,P);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    if(n!=1)AES::build(1,1,n);OSS::build(1,1,n);
    for(int i=1,a,b,c,d;i<=m;i++){
        scanf("%d",&a),scanf("%d%d%d",&b,&c,&d);
        if(a==1){
            OSS::modify(1,1,n,b,c,d);
            AES::modify(1,1,n,b-1,d);
            AES::modify(1,1,n,c,d);
        }else{
            lb res;
            if(b!=c)res=AES::query(1,1,n,b,c);
            res+=OSS::query(1,1,n,c);
            printf("%d\n",res.calc(d));
        }
    }
    return 0;
}

II.CF587E Duff as a Queen

和上题几乎一致，可以被看作是双倍经验，代码就不贴了。

INF.总结

线性基是一种很奇妙的东西，在求关于异或的东西的时候非常实用。同时，要注意它要与其它一些可以使用异或的数据结构区分，如01trie等。

它主要的用途有：

1. 最大/最小/k大异或和
2. 异或和数量
3. 异或和的和

同时又可以找到“子集”“子序列”等字眼，或者是图论中的某条路径的异或和时，就可以往线性基方向想了。

希望我的讲解能带你们听懂线性基。

参考材料：

a_forever_dream的博客

yangsongyi的博客

sengxian的博客