线性基学习笔记

线性代数

目录

• 线性基学习笔记
  • 数学知识
    • 向量空间（Wikipedia）
    • 线性相关与线性无关（Wikipedia）
    • 线性组合（Wikipedia）
    • 张成
    • 基（Wikipedia）
    • 线性相关性引理
  • 线性基
    • 定义
    • 算法
    • 练习
      • 动态删除

---

数学知识

向量空间（Wikipedia）

向量空间是线性代数研究的基本对象，可以简单的认为是在高中就是直角坐标系里的所有向量组成的集合。其实我们可以很多其它集合也看做向量，同时定义一下向量加法和标量乘法，就可以通过基向量的运算来表示出其它所有向量，这也是一个向量空间了。
定义$(F,V,+,\cdot)$为向量空间，其中$F$为域（$V$中元素的范围，大概类似于定义域），$V$为集合，$V$中的元素称为向量，$+$为向量加法，$\cdot$为标量乘法。并且要求运算满足$8$条公理（见维基百科）。

---

线性相关与线性无关（Wikipedia）

对于向量空间$(F,V,+,\cdot)$中的一个向量组$(\vec{v_1},\cdots,\vec{v_n})$，若存在不全为$0$的一组数$a_i \in F$，使得$\sum_{i=1}^n a_i \cdot\vec{v_i}=0$，则称这个向量组线性相关，否则称为线性无关。
线性相关有些地方就类似与高中数学的两个向量共线。

---

线性组合（Wikipedia）

对于向量空间$(F,V,+,\cdot)$中的一个向量组$(\vec{v_1},\cdots,\vec{v_n})$，一组数$a_i \in F$，和一个新向量$\vec{w}=\sum_{i=1}^n a_i \cdot\vec{v_i}$，称$\vec{w}$是向量组$(\vec{v_1},\cdots,\vec{v_n})$的一个线性组合，而且必然有$\vec{w}\in V$。
之所以叫线性组合，是因为如果将这个向量空间以直角坐标系的形式呈现，那么向量$\vec{w}$仍是直的，也就是说线性组合的运算不会弯曲向量。

性质：一组向量线性无关$\iff$其中不存在一个向量是该组的其它向量的一个线性组合

---

张成

对于向量空间$(F,V,+,\cdot)$中的一个向量组$(\vec{v_1},\cdots,\vec{v_n})$，其所有线性组合构成的集合称为其张成，记做$\text{span}(\vec{v_1},\cdots,\vec{v_n})$。
例子：高中数学中，平面的一个向量基底$(\vec{\hat{i}},\vec{\hat{j}})$，其张成就是整个平面的所有向量，其张成空间就是整个平面，因为平面上的所有向量都可以用它们的线性组合表示（即写成$\lambda\cdot\vec{\hat{i}}+\mu\cdot\vec{\hat{j}}$的形式）。

---

基（Wikipedia）

若向量空间$(F,V,+,\cdot)$中的一个向量组$\mathfrak{B}$即可张成出$V$，又是线性无关的，则称其为$V$的一个基，$\text{card}(\mathfrak{B})$为该向量空间的维数。

性质：

1. $\mathfrak{B}$是能张成$V$的极小集合，其任何真子集都不能张成出$V$；
2. $\mathfrak{B}$是该向量空间中线性无关的极大集合，该向量空间中不存在其它线性无关的向量集合使$\mathfrak{B}$是其真子集；
3. $V$中的每一个向量都可以用$\mathfrak{B}$中的一个唯一的线性组合表示。

第三点感性的证明就是如果存在不唯一的方案，那么一定说明$\mathfrak{B}$中有一个向量可以通过其它向量的线性组合表示，与定义矛盾。
总之，基向量就类似于高中数学用的基底，我们可以用它来代表一个向量空间，从而“减小”向量空间的大小。

---

线性相关性引理

• 若向量空间$(F,V,+,\cdot)$中的一个向量组$(\vec{v_1},\cdots,\vec{v_n})$是线性相关的，则有：
  
  1. $\exists \vec{v_i}\in\text{span}(\vec{v_1},\cdots,\vec{v_{i-1}},\vec{v_{i+1}},\cdots,\vec{v_n})$；
  2. $\exists \vec{v_i}$使得$\text{span}(\vec{v_1},\cdots,\vec{v_{i-1}},\vec{v_{i+1}},\cdots,\vec{v_n})=\text{span}(\vec{v_1},\cdots,\vec{v_n})$；

---

线性基

定义

• 线性基通常指OI中一种特殊的向量空间的基；
• 我们将任意自然数$x$的二进制表示$(\overline{b_m \cdots b_0})_2$看做一个$m$维向量，则线性基就是向量空间$(\{0,1\},\text{span}(\mathfrak{B}),\oplus,\cdot)$的基；

---

算法

• 不妨根据线性相关性引理来考虑（设当前处理的数为$x$）：
  
  1. 若$x=0$，则不加入$\mathfrak{B}$中（零向量不考虑）；
  2. 若$x \in\text{span}(\mathfrak{B})$，则不加入$\mathfrak{B}$中，否则加入$\mathfrak{B}$中。
• 这样做显然是支持动态插入的；
• 而我们每次要做的就是判断条件2，直接用$\mathfrak{B}$来高斯消元求解复杂度不是很优，但我们可以借鉴一下思想；
• 考虑维护一个高斯消元的对角矩阵，如果$x\&2^i$我们再考虑判断；
• 如果对角矩阵中第$i$行有数，那么就消去$x$的这一位，即$x \oplus 2^i$，否则说明高斯消元是无解的，可以将$x$加入$\mathfrak{B}$，并且应放在对角矩阵的第$i$行（如果后面还有消不掉的位，那其实也无所谓，为了方便就放在第一个可以的地方了）；
• 现在考虑维护对角矩阵。首先应将$x$的低位用对角矩阵的后几行的数消去，而前几行的数的第$i$位也应该用$x$将其消去；
• 这样就维护完成了，对角矩阵的大小是$O(\log{max\_x})$的，每次插入要遍历一次，所以总复杂度就是$O(n \log{max\_x})$的。
• 而通常来说，线性基的意思就变成了这个对角矩阵里的数了，因为它们是真正的基的数的异或和，所以仍能完成那些功能，而且更方便。

从Sengxian巨佬那里偷来的例子：
$n=5,A=\{7, 1, 4, 3, 5\}$。
一开始矩阵是这样的：

$$\begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$$
加入$7=(111)_2$，矩阵变为：
$$\begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$$
加入$1=(001)_2$，添加到最后一行，同时为了维护对角矩阵，消去第一行的最低位，矩阵变为：
$$\begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$
加入$4=(100)_2$，由于第一行已经有数了，它被异或为 $(010)_2$，加入第二行，同时为了维护对角矩阵，消去第一行的第二位，矩阵变为：
$$\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$
剩下的数都加不上了。

代码：

class LinearB{
    private:
        long long c[MAXDIM];
        void ist(long long x){
            for(int i=MAXDIM-1;i>=0;--i){
                if(~x>>i&1) continue;
                if(c[i]) x^=c[i];
                else{
                    c[i]=x;
                    for(int j=i-1;j>=0;--j){
                        if(c[i]>>j&1) c[i]^=c[j];
                    }
                    for(int j=i+1;j<MAXDIM;++j){
                        if(c[j]>>i&1) c[j]^=c[i];
                    }
                    break;
                }
            }
        }
    public:
        void init(long long a[],int n){
            for(int i=1;i<=n;++i)
                ist(a[i]);
        }
};

---

练习

1.[LOJ 113] 最大异或和

• 模板题，而最大异或和就是线性基里所有数的异或和（可以根据求解过程贪心证明）。

代码：

#include <cstdio>
const int MAXN=55,MAXDIM=55;
long long a[MAXN];
class LinearB{
    private:
        long long c[MAXDIM];
        void ist(long long x){
            for(int i=MAXDIM-1;i>=0;--i){
                if(~x>>i&1) continue;
                if(c[i]) x^=c[i];
                else{
                    c[i]=x;
                    for(int j=i-1;j>=0;--j){
                        if(c[i]>>j&1) c[i]^=c[j];
                    }
                    for(int j=i+1;j<MAXDIM;++j){
                        if(c[j]>>i&1) c[j]^=c[i];
                    }
                    break;
                }
            }
        }
    public:
        void init(long long a[],int n){
            for(int i=1;i<=n;++i)
                ist(a[i]);
        }
        long long qry_max(){
            long long ret=0;
            for(int i=0;i<MAXDIM;++i)
                ret^=c[i];
            return ret;
        }
}lb;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i]);
    lb.init(a,n);
    printf("%lld",lb.qry_max());
    return 0;
}

---

2.[LOJ 114] k大异或和

• 题目和题面不一样。。。
• 原数集的异或和集合肯定等于线性基的异或和集合；
• 仍然考虑贪心构造，肯定是将$k$二进制分解，将对应排名的线性基元素异或起来；
• 不过这是不考虑$0$的情况，如果$n>\text{card}(\mathfrak{B})$，那么肯定能异或出来$0$，这时候我们应该求不考虑$0$的第$k-1$小的。

代码：

#include <cstdio>
#include <algorithm>
#include <vector>
using std::sort;
using std::vector;
const int MAXN=1e5+5,MAXDIM=55;
long long a[MAXN];
class LinearB{
    private:
        long long span_sz;
        bool has_zero;
        long long c[MAXDIM];
        vector<long long> vec;
        void ist(long long x){
            for(int i=MAXDIM-1;i>=0;--i){
                if(~x>>i&1) continue;
                if(c[i]) x^=c[i];
                else{
                    c[i]=x;
                    for(int j=i-1;j>=0;--j){
                        if(c[i]>>j&1) c[i]^=c[j];
                    }
                    for(int j=i+1;j<MAXDIM;++j){
                        if(c[j]>>i&1) c[j]^=c[i];
                    }
                    break;
                }
            }
        }
    public:
        void init(long long a[],int n){
            for(int i=1;i<=n;++i)
                ist(a[i]);
            for(int i=0;i<MAXDIM;++i){
                if(c[i]) vec.push_back(c[i]);
            }
            //      long long !!!
            span_sz=(1LL<<vec.size())-1;
            if(n>vec.size()) has_zero=true;
            sort(vec.begin(),vec.end());
        }
        long long kth_val(long long k){
            if(has_zero) --k;
            if(k>span_sz) return -1;
            long long ret=0;
            for(int i=0;i<vec.size();++i){
                if(k>>i&1) ret^=vec[i];
            }
            return ret;
        }
}lb;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i]);
    lb.init(a,n);
    int m;
    scanf("%d",&m);
    long long k;
    for(int i=1;i<=m;++i){
        scanf("%lld",&k);
        printf("%lld\n",lb.kth_val(k));
    }
    return 0;
}

---

3.[BZOJ 4269] 再见Xor

• 最大值很好求，而次大值呢？完全不比用第$k$大那样求；
• 贪心即可证明，将最大值异或上线性基的最小值即可。

代码：

#include <cstdio>
const int MAXN=100005,MAXDIM=32;
int n;
int a[MAXN];
class LinearB{
    private:
        int c[MAXDIM];
        void ist(int x){
            for(int i=MAXDIM-1;i>=0;--i){
                if(~x>>i&1) continue;
                if(c[i]) x^=c[i];
                else{
                    c[i]=x;
                    for(int j=i-1;j>=0;--j){
                        if(c[i]>>j&1) c[i]^=c[j];
                    }
                    for(int j=i+1;j<MAXDIM;++j){
                        if(c[j]>>i&1) c[j]^=c[i];
                    }
                    break;
                }
            }
        }
    public:
        void init(int a[],int n){
            for(int i=1;i<=n;++i)
                ist(a[i]);
        }
        int qry_max(){
            int ret=0;
            for(int i=0;i<MAXDIM;++i)
                ret^=c[i];
            return ret;
        }
        int lb_min(){
            for(int i=0;i<MAXDIM;++i){
                if(c[i]) return c[i];
            }
        }
}lb;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    lb.init(a,n);
    int max=lb.qry_max();
    printf("%d %d",max,max^lb.lb_min());
    return 0;
}

---

4.[BJOI 2011] 元素

• 题意就是求一个线性基，使价值和最大；
• 那么和Kruskal算法一个思路，按价值从大到小的思路贪心即可。

代码：

#include <cstdio>
#include <algorithm>
using std::sort;
const int MAXN=1005,MAXDIM=60;
int n;
struct data{
    int val;
    long long id;
    static bool cmp_val(const data &a,const data &b){
        return a.val>b.val;
    }
}w[MAXN];
class LinearB{
    private:
        long long c[MAXDIM];
    public:
        bool ist(long long x){
            for(int i=MAXDIM-1;i>=0;--i){
                if(~x>>i&1) continue;
                if(c[i]) x^=c[i];
                else{
                    c[i]=x;
                    for(int j=i-1;j>=0;--j){
                        if(c[i]>>j&1) c[i]^=c[j];
                    }
                    for(int j=i+1;j<MAXDIM;++j){
                        if(c[j]>>i&1) c[j]^=c[i];
                    }
                    return true;
                }
            }
            return false;
        }
};
inline int greedy(){
    static LinearB lb;
    sort(w+1,w+n+1,data::cmp_val);
    int ret=0;
    for(int i=1;i<=n;++i){
        if(lb.ist(w[i].id))
            ret+=w[i].val;
    }
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lld%d",&w[i].id,&w[i].val);
    printf("%d",greedy());
    return 0;
}

---

5.[WC 2011] Xor

• 考虑任意一个环都可以产生贡献，因为我们可以沿一条链过去转一圈再原路返回；
• 那么$1$到$n$的任意一个路径都可以表示为任意一条$1$到$n$的链异或上一些环，画一画图就可以看出来了，总能异或出来；
• 之后就是构造环的线性基，求其与一条$1$到$n$的链的最大异或和，这个就是将这个链带进去，从高到低扫，如果这一位是$0$就异或，证明就是贪心，很显然。

代码：

#include <cstdio>
#include <vector>
using std::vector;
const int MAXN=50005,MAXM=100005,MAXDIM=60;
int he[MAXN];
long long dis[MAXN];
vector<long long> cir;
struct line{
    int to,nex;
    long long w;
}ed[MAXM<<1];
class LinearB{
    private:
        long long c[MAXDIM];
        void ist(long long x){
            for(int i=MAXDIM-1;i>=0;--i){
                if(~x>>i&1) continue;
                if(c[i]) x^=c[i];
                else{
                    c[i]=x;
                    for(int j=i-1;j>=0;--j){
                        if(c[i]>>j&1) c[i]^=c[j];
                    }
                    for(int j=i+1;j<MAXDIM;++j){
                        if(c[j]>>i&1) c[j]^=c[i];
                    }
                    break;
                }
            }
        }
    public:
        void init(vector<long long> &a){
            for(int i=0;i<a.size();++i)
                ist(a[i]);
        }
        long long qry_max(long long x){
            for(int i=MAXDIM-1;i>=0;--i){
                if(~x>>i&1) x^=c[i];
            }
            return x;
        }
}lb;
inline void addE(int u,int v,long long w){
    static int cnt;
    ed[++cnt]=(line){v,he[u],w};
    he[u]=cnt;
}
void DFS(int u,int fa){
    static bool vis[MAXN];
    vis[u]=true;
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(v==fa) continue;
        if(!vis[v]){
            dis[v]=dis[u]^ed[i].w;
            DFS(v,u);
        }
        else cir.push_back(dis[u]^dis[v]^ed[i].w);
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    long long w;
    for(int i=1,u,v;i<=m;++i){
        scanf("%d%d%lld",&u,&v,&w);
        addE(u,v,w),addE(v,u,w);
    }
    DFS(1,0);
    lb.init(cir);
    printf("%lld",lb.qry_max(dis[n]));
    return 0;
}

---

6.[SCOI 2016] 幸运数字

• 看到这题的操作很想树剖或者倍增；
• 不过线性基确实是支持合并的，因为一个线性基代表了那个集合的所有异或和，只需要将这个线性基插入到另一个里就可以了，复杂度是$O(\log^2{max\_x})$；
• 那么倍增即可，不过需要特判询问$u$到$u$的这种（坑啊...）。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using std::swap;
const int MAXN=20005,MAXDIM=61,MAXLOG=15;
int n;
int he[MAXN],de[MAXN],anc[MAXN][MAXLOG];
long long w[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
class LinearB{
    public:
        long long c[MAXDIM];
        void ist(long long x){
            for(int i=MAXDIM-1;i>=0;--i){
                if(~x>>i&1) continue;
                if(c[i]) x^=c[i];
                else{
                    c[i]=x;
                    for(int j=i-1;j>=0;--j){
                        if(c[i]>>j&1) c[i]^=c[j];
                    }
                    for(int j=i+1;j<MAXDIM;++j){
                        if(c[j]>>i&1) c[j]^=c[i];
                    }
                    break;
                }
            }
        }
        LinearB(){memset(c,0,sizeof(c));}
        LinearB& operator +=(const LinearB &that){
            for(int i=0;i<MAXDIM;++i){
                if(that.c[i]) ist(that.c[i]);
            }
            return *this;
        }
        LinearB operator +(const LinearB &that)const{
            LinearB ret=*this;
            ret+=that;
            return ret;
        }
        long long qry_max(){
            long long ret=0;
            for(int i=0;i<MAXDIM;++i)
                ret^=c[i];
            return ret;
        }
}lb[MAXN][MAXLOG];
inline void addE(int u,int v){
    static int cnt;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
void DFS(int u){
    de[u]=de[anc[u][0]]+1;
    lb[u][0].ist(w[u]);
    lb[u][0].ist(w[anc[u][0]]);
    for(int i=1,lim=log2(de[u]);i<=lim;++i){
        anc[u][i]=anc[anc[u][i-1]][i-1];
        lb[u][i]=lb[u][i-1]+lb[anc[u][i-1]][i-1];
    }
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(v!=anc[u][0]){
            anc[v][0]=u;
            DFS(v);
        }
    }
}
inline long long dbl_jump(int u,int v){
    if(u==v) return w[u];
    if(de[u]<de[v]) swap(u,v);
    LinearB ret;
    for(int d=de[u]-de[v],i=0;d;++i,d>>=1){
        if(d&1){
            ret+=lb[u][i];
            u=anc[u][i];
        }
    }
    if(u==v) return ret.qry_max();
    for(int i=MAXLOG-1;i>=0;--i){
        if(anc[u][i]!=anc[v][i]){
            ret+=lb[u][i]+lb[v][i];
            u=anc[u][i],v=anc[v][i];
        }
    }
    ret+=lb[u][0]+lb[v][0];
    return ret.qry_max();
}
int main(){
    int q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)
        scanf("%lld",&w[i]);
    for(int i=1,u,v;i<n;++i){
        scanf("%d%d",&u,&v);
        addE(u,v),addE(v,u);
    }
    DFS(1);
    for(int i=1,u,v;i<=q;++i){
        scanf("%d%d",&u,&v);
        printf("%lld\n",dbl_jump(u,v));
    }
    return 0;
}

---

7.[BJOI 2011] 梦想封印

• 看到删边肯定考虑离线倒着来；
• 和之前WC那道一样，肯定是$1$到$u$的链异或一些环，但是如何去重呢？
• 环很好办，求个线性基就好了，而链很麻烦；
• 我们考虑这样一个事情，就是如果两个链通过环的线性基消$1$后剩下来的部分一样，那么它们和线性基的所有异或和组成的集合必然相等。因为既然这两个链可以用线性基消成一样的，我们就可以了用一个链异或上一些线性基里的元素来变成另一个；
• 所以我们将所有$1$到$u$的链用这个方法求一个值，这是这个链的“属性”，放到std::set里就可以了对链去重了；
• 现在考虑怎么处理加边操作（设边为$(u,v)$）：
  
  1. 如果$u,v$都访问过，显然这个边是DFS树的非树边，所以构成了环；
  2. 如果其中一个访问过，说明另一个点所在连通块之前还未和$1$连通，我们DFS一下这个连通块；
  3. 如果都未访问过，说明这两个点所在连通块都还未和$1$连通，我们不需要管。
• 注意，每次修改线性基后，都应该更新一下std::set，而且只会删，因为线性基里只会增加元素。而线性基里每增加一个元素，属性值在这一位就只能是$0$，属性值的种类也就减半，所以暴力更新就可以了。

代码：

#include <cstdio>
#include <set>
using std::set;
const int MAXN=5005,MAXM=20005,MAXQ=MAXM,MAXDIM=60;
int he[MAXN],del_id[MAXQ];
long long dis[MAXN],ans[MAXQ];
bool vis[MAXN],del[MAXM];
set<long long> se;
struct graph{
    int u,v;
    long long w;
}G[MAXM];
struct line{
    int to,nex;
    long long w;
}ed[MAXM<<1];
class LinearB{
    private:
        int sz;
        long long c[MAXDIM];
        void upd_attrib(){
            static long long tmp[MAXN];
            tmp[0]=0;
            for(set<long long>::iterator iter=se.begin();iter!=se.end();++iter)
                tmp[++tmp[0]]=*iter;
            se.clear();
            for(int i=1;i<=tmp[0];++i)
                se.insert(attrib(tmp[i]));
        }
    public:
        void ist(long long x){
            for(int i=MAXDIM-1;i>=0;--i){
                if(~x>>i&1) continue;
                if(c[i]) x^=c[i];
                else{
                    ++sz;
                    c[i]=x;
                    for(int j=i-1;j>=0;--j){
                        if(c[i]>>j&1) c[i]^=c[j];
                    }
                    for(int j=i+1;j<MAXDIM;++j){
                        if(c[j]>>i&1) c[j]^=c[i];
                    }
                    upd_attrib();
                    break;
                }
            }
        }
        long long attrib(long long x){
            for(int i=MAXDIM-1;i>=0;--i){
                if(x>>i&1) x^=c[i];
            }
            return x;
        }
        int size(){return sz;}
}lb;
inline void addE(int u,int v,long long w){
    static int cnt;
    ed[++cnt]=(line){v,he[u],w};
    he[u]=cnt;
}
void DFS(int u,int fa,long long dis){
    vis[u]=true;
    ::dis[u]=dis;
    se.insert(lb.attrib(dis));
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(v==fa) continue;
        if(!vis[v]) DFS(v,u,dis^ed[i].w);
        else lb.ist(::dis[u]^::dis[v]^ed[i].w);
    }
}
inline void addE(graph &e){
    if(vis[e.u] && vis[e.v])
        lb.ist(dis[e.u]^dis[e.v]^e.w);
    else{
        addE(e.u,e.v,e.w),addE(e.v,e.u,e.w);
        if(vis[e.u]) DFS(e.v,e.u,dis[e.u]^e.w);
        else if(vis[e.v]) DFS(e.u,e.v,dis[e.v]^e.w);
    }
}
inline long long cal(){return se.size()*(1LL<<lb.size())-1;}
int main(){
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;++i)
        scanf("%d%d%lld",&G[i].u,&G[i].v,&G[i].w);
    for(int i=1;i<=q;++i){
        scanf("%d",&del_id[i]);
        del[del_id[i]]=true;
    }
    for(int i=1;i<=m;++i){
        if(!del[i]) addE(G[i]);
    }
    DFS(1,0,0);
    ans[++q]=cal();
    for(int i=q-1;i;--i){
        addE(G[del_id[i]]);
        ans[i]=cal();
    }
    for(int i=1;i<=q;++i)
        printf("%lld\n",ans[i]);
    return 0;
}

---

8.[BZOJ 2844] albus就是要第一个出场

• 看样例解释才看懂题。。。
• 如果不算重复的，很容易做，就是之前第$k$大异或和的逆操作；
• 但是怎么考虑重复的呢？
• 其实每种异或和都出现了一样的次数——$2^{n-\text{card}(\mathfrak{B})}$次；
• 我们这样考虑，对于线性基的一个异或和$x$，异或上不再线性基的一些元素的异或和$y$，而$y$肯定可以用线性基异或出来，所以再异或一下就还是$x$了；
• 但是上面用到的元素可能重复，不合题意，不过这只是构造方法，我们是可以将式子化简的（异或多次的异或掉就好了）；
• 这样显然每种都出现了这么多次；
• 又由于允许空集，所以这里算的不重复排名要强制加$1$，之后快速幂算重复次数即可。

代码：

#include <cstdio>
#include <vector>
using std::vector;
const int MAXN=100005,MAXDIM=31,P=10086;
int a[MAXN];
class LinearB{
    private:
        int c[MAXDIM];
        vector<int> vec;
        void ist(int x){
            for(int i=MAXDIM-1;i>=0;--i){
                if(~x>>i&1) continue;
                if(c[i]) x^=c[i];
                else{
                    c[i]=x;
                    for(int j=i-1;j>=0;--j){
                        if(c[i]>>j&1) c[i]^=c[j];
                    }
                    for(int j=i+1;j<MAXDIM;++j){
                        if(c[j]>>i&1) c[j]^=c[i];
                    }
                    break;
                }
            }
        }
    public:
        int size(){return vec.size();}
        void init(int a[],int n){
            for(int i=1;i<=n;++i)
                ist(a[i]);
            for(int i=0;i<MAXDIM;++i){
                if(c[i]) vec.push_back(i);
            }
        }
        int get_rk(int x){
            int ret=0;
            for(int i=0;i<vec.size();++i){
                if(x>>vec[i]&1) ret+=1<<i;
            }
            ++ret; //线性基全不选的情况
            return ret;
        }
}lb;
int pow(int x,int y){
    int ret=1;
    for(;y;x=(long long)x*x%P,y>>=1){
        if(y&1) ret=(long long)ret*x%P;
    }
    return ret;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    lb.init(a,n);
    int q;
    scanf("%d",&q);
    printf("%d",((long long)(lb.get_rk(q)%P-1+P)%P*pow(2,n-lb.size())%P+1)%P);
    return 0;
}

---

9.[清华集训 2014] 玛里苟斯

• 毕叔叔出的乱搞题，数据还贼坑Orz
• $k$很小，考虑分情况讨论：
  
  1. 当$k=1$时：
     
     • 答案就是所有异或和除上方案数；
     • 由于异或可以按位单独考虑，所以我们按位来看；
     • 如果一位有$1$，那么选奇数个和选偶数个的方案各占一半。因为对于$\forall n \in\{x \in\mathbb{N_+}\mid x>2 \}$，有：
       $$\sum_{\substack{1 \leq i \leq n \\ 2 \nmid i}}\text{C}_n^i=\sum_{\substack{1 \leq i \leq n \\ 2 \mid i}}\text{C}_n^i$$
     • 这个可以用递推式大力展开证明；
     • 那么答案就是所有数的或除$2$，注意要用特判处理小数。。。
  2. 当$k=2$时：
     
     • 每一个异或和$(\overline{b_m \cdots b_0})_2$的贡献为$(\overline{b_m \cdots b_0})_2 \times (\overline{b_m \cdots b_0})_2$，写成求和式就是$\sum_{i=0}^m \sum_{j=0}^m b_ib_j \times 2^{i+j}$，就是个二进制下的多项式乘法；
     • 而且只有$b_i$和$b_j$都为$1$时才有贡献；
     • 由于答案大小有限制，所以此时$a_i<2^{32}$，我们可以暴力枚举每两位；
     • 那么现在我们需要考虑的是二元组$(0/1,0/1)$是$(1,1)$的概率，如果不退化为只有$(0,0)$和$(1,1)$的情况（这种和$k=1$时考虑一位的方法一样）的话，那是$\frac{1}{4}$;
     • 由于卡精度，我们需要先不除$2$，最后特判是否有小数，这个看实现就可以看出只可能有$.5$的情况；
     • 细节代码里有注释。
  3. 当$k \geq 3$时：
     
     • 这时可以发现$a_i<2^{22}$，那么线性基大小小于$22$，我们可以暴力枚举每一种异或和计算；
     • 而且由上一题结论得，每种异或和出现次数一样，所以我们求期望就上下同除$2^{n-\text{card}(\mathfrak{B})}$；
     • 注意由于中间不能除$2^{\text{card}(\mathfrak{B})}$，且这个数据精心构造，所以即使unsigned long long也会溢出，我们应该存成$ans=\lfloor\frac{ans}{2^{\text{card}(\mathfrak{B})}}\rfloor\times 2^{\text{card}(\mathfrak{B})}+ans \bmod{2^{\text{card}(\mathfrak{B})}}$的形式；
     • 这种不知道为什么，小数也只可能是$.5$，不过出题人也不知道了。。。
       

代码：

#include <cstdio>
#include <vector>
using std::vector;
const int MAXN=100005;
int n,K;
unsigned long long a[MAXN];
inline void solve1(){
    unsigned long long ret=0;
    for(int i=1;i<=n;++i)
        ret|=a[i];
    printf("%llu",ret>>1);
    if(ret&1) printf(".5");
}
inline void solve2(){
    int tmp=0;
    unsigned long long ret=0;
    bool flag;
    for(int i=0;i<32;++i){
        flag=false;
        for(int j=1;j<=n;++j){
            if(a[j]>>i&1){
                flag=true;
                break;
            }
        }
        if(!flag) continue;
        for(int j=0;j<32;++j){
            flag=false;
            for(int k=1;k<=n;++k){
                if(a[k]>>j&1){
                    flag=true;
                    break;
                }
            }
            if(!flag) continue;
            flag=false;
            for(int k=1;k<=n;++k){
                if((a[k]>>i&1)!=(a[k]>>j&1)){
                    flag=true;
                    break;
                }
            }
            //tmp是目前除不了的贡献，记到一起最后除
            //单位是1/2，对于i=j=0时才可能为-2，但此时flag比为false，不存在，所以这里只有÷2的情况
            if(i+j-1-flag<0) ++tmp;
            else ret+=1LL<<i+j-1-flag; //除过了（左移位数-1-flag）
        }
    }
    ret+=tmp>>1;
    printf("%llu",ret);
    if(tmp&1) printf(".5");
}
inline void solve3(){
    static int lb[22];
    static vector<int> vec;
    for(int i=1;i<=n;++i){
        for(int j=21;j>=0;--j){
            if(~a[i]>>j&1) continue;
            if(lb[j]) a[i]^=lb[j];
            else{
                lb[j]=a[i];
                for(int k=j-1;k>=0;--k){
                    if(lb[j]>>k&1) lb[j]^=lb[k];
                }
                for(int k=j+1;k<22;++k){
                    if(lb[k]>>j&1) lb[k]^=lb[j];
                }
                break;
            }
        }
    }
    for(int i=0;i<22;++i){
        if(lb[i]) vec.push_back(lb[i]);
    }
    long long ret1=0,ret2=0,tmp1,tmp2;
    for(int i=0,tmp,lim=1<<vec.size();i<lim;++i){
        tmp=0;
        for(int j=0;j<vec.size();++j){
            if(i>>j&1) tmp^=vec[j];
        }
        tmp1=0,tmp2=1;
        for(int j=1;j<=K;++j){
            tmp1*=tmp,tmp2*=tmp;
            tmp1+=tmp2>>vec.size();
            tmp2&=lim-1;
        }
        ret1+=tmp1,ret2+=tmp2;
        ret1+=ret2>>vec.size();
        ret2&=lim-1;
    }
    printf("%lld",ret1);
    if(ret2) printf(".5");
}
int main(){
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;++i)
        scanf("%llu",&a[i]);
    if(K==1) solve1();
    else if(K==2) solve2();
    else solve3();
    return 0;
}

---

动态删除

1.[HAOI 2017] 八纵八横

• 不好删除但支持动态插入的可以考虑线段树分治；
• 之后这题和WC那题就一样了，只是需要用std::bitset存，有点毒瘤。
• 不过还有一种貌似是真动态删除的方法，常数要小很多，但是那位神佬已经忘了怎么做了，写的题解也丢了，那就这样吧。。。

代码：

#include <iostream>
#include <bitset>
#include <algorithm>
#include <vector>
using std::cin;
using std::cout;
using std::ios;
using std::bitset;
using std::swap;
using std::vector;
const int MAXN=505,MAXM=505,MAXP=1005,MAXBIT=1005,MAXDIM=MAXBIT;
int n,m,p;
int he[MAXN],opt_st[MAXP];
bitset<MAXBIT> dis[MAXN],ans[MAXP];
struct graph{
    int u,v;
    bitset<MAXBIT> w;
}G[MAXM],opt[MAXP];
vector<graph> nTreeE;
struct line{
    int to,nex;
    bitset<MAXBIT> w;
}ed[MAXN<<1];
class UFS{
    private:
        int fa[MAXN],dist[MAXN];
    public:
        void init(int n){
            for(int i=1;i<=n;++i)
                fa[i]=i,dist[i]=1;
        }
        int find(int x){
            if(x==fa[x]) return x;
            fa[x]=find(fa[x]);
            return fa[x];
        }
        void uni(int x,int y){
            if(dist[x]<dist[y]) swap(dist[x],dist[y]);
            fa[y]=x,dist[x]+=(dist[y]==dist[x]);
        }
};
class LinearB{
    private:
        bitset<MAXBIT> c[MAXDIM];
    public:
        void ist(bitset<MAXBIT> &x){
            for(int i=MAXDIM-1;i>=0;--i){
                if(x[i]==0) continue;
                if(c[i][i]) x^=c[i];
                else{
                    c[i]=x;
                    for(int j=i-1;j>=0;--j){
                        if(c[i][j]) c[i]^=c[j];
                    }
                    for(int j=i+1;j<MAXDIM;++j){
                        if(c[j][i]) c[j]^=c[i];
                    }
                    break;
                }
            }
        }
        bitset<MAXBIT> qry_max(){
            bitset<MAXBIT> ret;
            for(int i=0;i<MAXDIM;++i)
                ret^=c[i];
            return ret;
        }
};
class segT{
#define ls (u<<1)
#define rs (ls|1)
    private:
        vector<bitset<MAXBIT> > vec[MAXP<<2];
        void ist(int u,int l,int r,int lp,int rp,bitset<MAXBIT> &x){
            if(lp<=l && r<=rp){
                vec[u].push_back(x);
                return;
            }
            int mid=l+r>>1;
            if(lp<=mid) ist(ls,l,mid,lp,rp,x);
            if(rp>mid) ist(rs,mid+1,r,lp,rp,x);
        }
        void DC(int u,int l,int r,LinearB lb,bitset<MAXBIT> ans[]){
            for(int i=0;i<vec[u].size();++i)
                lb.ist(vec[u][i]);
            if(l==r){
                ans[l]=lb.qry_max();
                return;
            }
            int mid=l+r>>1;
            DC(ls,l,mid,lb,ans);
            DC(rs,mid+1,r,lb,ans);
        }
    public:
        void ist(int l,int r,bitset<MAXBIT> x){ist(1,0,p,l,r,x);}
        void DC(bitset<MAXBIT> ans[]){
            LinearB lb;
            DC(1,0,p,lb,ans);
        }
#undef ls
#undef rs
}T;
inline void out_bitset(bitset<MAXBIT> &x){
    int cur;
    for(cur=MAXBIT-1;cur;--cur){
        if(x[cur]) break;
    }
    for(;cur>=0;--cur) cout<<x[cur];
}
inline void addE(int u,int v,bitset<MAXBIT> &w){
    static int cnt;
    ed[++cnt]=(line){v,he[u],w};
    he[u]=cnt;
}
inline void spanT(){
    static UFS ufs;
    ufs.init(n);
    for(int i=1,u,v,ufa,vfa;i<=m;++i){
        u=G[i].u,v=G[i].v;
        ufa=ufs.find(u),vfa=ufs.find(v);
        if(ufa!=vfa){
            ufs.uni(ufa,vfa);
            addE(u,v,G[i].w),addE(v,u,G[i].w);
        }
        else nTreeE.push_back(G[i]);
    }
}
void DFS(int u,int fa){
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(v!=fa){
            dis[v]=dis[u]^ed[i].w;
            DFS(v,u);
        }
    }
}
inline void fast_ios(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}
int main(){
    fast_ios();
    cin>>n>>m>>p;
    for(int i=1;i<=m;++i)
        cin>>G[i].u>>G[i].v>>G[i].w;
    spanT();
    DFS(1,0);
    for(int i=0;i<nTreeE.size();++i)
        T.ist(0,p,dis[nTreeE[i].u]^dis[nTreeE[i].v]^nTreeE[i].w);
    int k=0;
    char cmd[10];
    for(int i=1,x;i<=p;++i){
        cin>>cmd;
        //add
        if(cmd[1]=='d'){
            opt_st[++k]=i;
            cin>>opt[k].u>>opt[k].v>>opt[k].w;
        }
        //cancel
        else if(cmd[1]=='a'){
            cin>>x;
            T.ist(opt_st[x],i-1,dis[opt[x].u]^dis[opt[x].v]^opt[x].w);
            opt_st[x]=0;
        }
        else{
            cin>>x;
            T.ist(opt_st[x],i-1,dis[opt[x].u]^dis[opt[x].v]^opt[x].w);
            cin>>opt[x].w;
            opt_st[x]=i;
        }
    }
    for(int i=1;i<=k;++i){
        if(opt_st[i]) T.ist(opt_st[i],p,dis[opt[i].u]^dis[opt[i].v]^opt[i].w);
    }
    T.DC(ans);
    for(int i=0;i<=p;++i){
        out_bitset(ans[i]);
        cout<<'\n';
    }
    return 0;
}