线性基求交

定义线性空间 \(V_i\) 的基底为 \(B_i\)，现在我们希望求出 \(V_1\cap V_2\) 的基底 \(W\)。

• 引理：令 \(T=V_1\cap B_2\)，若 \(B_1\cup(B_2/T)\) 线性无关，则 \(T\) 是所求的 \(W\) 之一。

  证明：考虑反面证明，若 \(T\) 非法则线性有关，设 \(v\in V_1\cap V_2\) 且不能被 \(T\) 表出。

  那么有 \(v=x\oplus y,x\in T,y\in B_2/T\)，且 \(y>0\)。

  因为 \(x\in T\implies x\in V_1\)，同时 \(v\in V_1\)，所以 \(x\oplus v=y\in V_1\)

  \(y\) 就可以被 \(B_1\) 表出

  则 \(B_1\cup (B_2/T)\) 线性相关。

考虑如何求出 \(W\)，可以考虑枚举 \(x:1\to |B_2|\)：

• \(b_x\in B_2\)

  1. \(b_x\) 可以被 \(B_1\cup \lbrace b_1,b_2\dots b_{x-1}\rbrace\) 表出

     设 \(b_x=p\oplus q,p\in V_1,q\) 被 \(\lbrace b_1,b_2\dots b_{x-1}\rbrace\) 表出，则将 \(q\) 加入 \(W\)。

  2. 否则不做任何操作。

证明这样可以求出 \(W\)，只需要证明 \(V_{B_2-W}\cap V_1=\lbrace 0\rbrace\) 即可。

设 \(x\in V_{B_2/W}\cap V_1,x>0\)

则有 \(x\) 可以被 \(B_1\) 以及 \(B_2/W\) 表出，那么取出 \(B_2/W\) 里下标最大的 \(b_k\)，则有 \(b_k\) 可以被 \(B_2/W/\lbrace b_k\rbrace\cup B_1\) 表出，那么与假设不符。

证毕。

实现：

struct node{
    int d[32];
    node(){
        memset(d,0,sizeof d);
    }
    void ins(int x){
        for(int i=31;i>=0;--i)if((x>>i)&1){
            if(d[i])x^=d[i];
            else {d[i]=x;return ;}
        }
    }
    bool count(int x){
        for(int i=31;i>=0;--i)if((x>>i)&1){
            if(!d[i])return false;
            x^=d[i];
        }
        return true;
    }
    node operator&(const node b)const {
        node tmpa;memcpy(tmpa.d,d,sizeof d);
        node uda=tmpa,res;
        for(int i=0;i<32;++i)if(b.d[i]){
            int x=b.d[i],sur=0,tag=1;
            for(int j=i;j>=0;--j)if((x>>j)&1){
                if(tmpa.d[j])x^=tmpa.d[j],sur^=uda.d[j];
                else {tmpa.d[j]=x,uda.d[j]=sur,tag=0;break;}//uda.d[i] 指该元素使用的 B_1 中元素 xor 和
            }
            if(tag)res.ins(sur);
        }
        return res;
    }
};

例题：

牛客884B

给定 \(n\) 个线性基，问 \([l,r]\) 的线性基是否都能够表出 \(x\)

考虑先建立线段树，该节点代表子树内所有线性基的交。

然后查询时在分的log个线性基里各自查询即可。

复杂度 \(O(nk\log n+nk^2)\)，其中 \(k\) 是线性基维度。