线性基求交

线性基求交。

大概就是 \(A,B\) 线性基求交。

答案 \(C\) 一定满足 \(\forall x\in C,x\in A,B\) 。

所以我们考虑 \(A\) 的每一个基，看他在没在 \(B\) 中出现。

如果出现，保留，否则考虑只可能是 \(x\in B,x=d_i \oplus \sum d_{k_j},k_j<i\) 这种。

所以这代表了 \(B\) 和小于 \(i\) 的 \(d_i\) 一定能表示处 \(d_i\)。

所以如果表示出来就加入 \(x=d_i \oplus \sum d_{k_j}\) 就好了。

单次复杂度 \(\mathcal{O(\log^2)}\)

代码:

struct base{
    ll b[70];
    void merge(base a){
        static bool vis[70];memset(vis,0,sizeof(vis));
        for(int i=0;i<=63;i++){
            if(b[i]){
                ll res=0,ret=1,x=b[i];
                for(int j=i;j>=0;j--){
                    if((x>>j)&1){
                        if(!a.b[j]){
                            a.b[j]=x;vis[j]=1;ret=0;
                            break;
                        }
                        x^=a.b[j];if(vis[j]) res^=a.b[j];
                    }
                }
                if(ret) b[i]=b[i]^res;
                else b[i]=0;
            }
        }
    }
};

UOJ698

这个题我赛时想到了，但是少加了个东西，被hack了，但是很简单。

首先线性基求前缀交，然后你就可以对这个二分了，复杂度 \(\mathcal{O(nB^2+qB\log^2n)}\)

然后实际上你可以发现，这些线性基都是子空间，如果把他们的元素重新交换什么的，你就可以把每次求交改成删数。

这样你通过最初的那个基，你就可以打上时间戳即可。

这个元素重新构造的操作是必要的，我赛事没干这个，就被hack，原因也很显然。

那么如何重构？，很简单你先把 \(B_{i+1}\) 的元素先加入，然后在加入 \(B_i\) 本身的元素。

所以复杂度 \(\mathcal{O(nB^2+qB)}\)

我一直卡一个题解说的二分，很难受，没想到考试写的就是正解。

---

线性基可以让我们在 \(O(\log B)\) 的时间内求出一个集合表示一个数 \(x\) 的方案数。。注意。