线性基 学习笔记

xujindong_ · 2025-09-19 09:10:50 · 个人记录

异或线性基

把每一个二进制数的看作一个位数维的向量，异或相当于模二意义下的加法，这样的线性基为异或线性基。异或线性基就是对于给定的数，求出一组数，从中选数异或能产生给定数异或的所有结果，且这组数的数量最小。

异或线性基解决的问题一般会从序列里挑任意个数异或起来。根据定义，线性基的异或能表示原序列异或的所有可能，而且线性基大小只有位数个，减少了复杂度。

基是线性代数的概念，我们可以用严谨的语言去描述：

我们研究的是线性空间，可以看作向量的推广，包含向量集合 V 和标量的域 \mathbb P，且有两个特殊运算向量加法 + 和数乘 \cdot。要求 (V,+) 是交换群，\mathbb P 是域。数乘指标量和向量的运算 \mathbb P\times V\to V，且满足以下性质：

• 数乘对向量加法分配律 \forall\mathbf u,\mathbf v\in V,a\in\mathbb P,a(\mathbf u+\mathbf v)=a\mathbf u+a\mathbf v；
• 数乘对标量加法分配律 \forall\mathbf u\in V,a,b\in\mathbb P,(a+b)\mathbf u=a\mathbf u+b\mathbf u；
• 数乘结合律 \forall\mathbf u\in V,a,b\in\mathbb P,(ab)\mathbf u=a(b\mathbf u)；
• 标量乘法单位元 1\in\mathbb P,\forall\mathbf u\in V,1\mathbf u=\mathbf u。

称 a_1,a_2,\cdots,a_n 为 V 的一个向量组，对 k_1,k_2,\cdots,k_n\in\mathbb P， \sum_{i=1}^n k_ia_i 为该向量组的一个线性组合。若存在一组不全为 0 的 k 使线性组合出零向量，则称该向量组线性相关，否则线性无关。

对一个向量组，其线性组合出的所有向量也构成一个线性空间，称为该向量组张成的线性空间 \operatorname{span}(a)。

称线性空间 V 的一组基为 V 的一个极大线性无关组，也就是选出最多的线性无关向量。V 的维数 \dim V 为线性基的元素个数。

异或线性基就是定义在 \mathbb Z_2^n 上的线性空间的基。还有实数线性基是定义在 \mathbb R^n 上的线性空间的基。其作用可以类比平面/空间向量基本定理，用一些基向量可以描述整个线性空间。

插入

钦定线性基中每个数的最高有效位不同。

如果当前数插入后线性相关了，就不插，因为这个数在线性基中的组合能完全替代这个数的作用。否则需要插入。

从高位向低位遍历，如果当前位为 1 就把插入的数异或线性基的这一位元素，这保证了遍历到某一位时，更高的位都为 0。如果线性基的这一位没有则插入这个数，此时插入的值与之前异或过的数构成了原来插入的数。如果最后为零说明插不进去。

bool insert(T k){
  for(int i=maxn-1;i>=0;i--){
    if(k>>i&1){
      if(!b[i])return b[i]=k,1;
      k^=b[i]; 
    }
  }
  return 0;
}

异或最大值

从高位往低位枚举，若异或这个数能变大就贪心地异或。因为能变大说明是 0\operatorname{xor}1=1，剩下的数不会影响这一位。

T query1(T ans=0){
  for(int i=maxn-1;i>=0;i--)ans=max(ans,ans^b[i]);
  return ans;
}

异或最小值

原序列能异或出的最小值为线性基中最小值，因为其他数的最高位更高，最小值异或其他数时这些数的最高位会被保留。特别地，还要考虑有没有插入失败过。如果失败过，最小值为 0。

T query2(){
  for(int i=0;i<maxn;i++)if(b[i])return b[i];
}

异或第 k 小

从高到低贪心，若线性基这一位有值，异或与不异或会让这一位为 0 或 1，更低位任选的方案数是 2^{num}，num 是更低位线性基有值的个数。用类似的方法还可以查异或 <k 的个数等。

T kth(int k,T ans=0){
  for(int i=maxn-1,num=cnt;i>=0;i--){
    if(!b[i])continue;
    num--;
    if(k<=1<<num){
      if(ans>>i&1)ans^=b[i];
    }
    else{
      k-=1<<num;
      if(~ans>>i&1)ans^=b[i];
    }
  }
  return ans;
}

最简线性基

我们可以对线性基进一步消元，枚举 i<j，若 a_j 第 i 位为 1 就异或 a_i。

消元后，保证每一行的第一个 1 是这一列的唯一元素，或者说是简化行阶梯形矩阵。这也刻画了线性基代表的线性空间，若两个线性基的最简线性基相同，两者本质相同。

简化行阶梯形矩阵也简化了一些问题，如异或第 k 小，更高位选的情况相同，选了第 i 个比不选一定大，将 k 二进制拆分取对应位即可。

void rebuild(){
  for(int i=0;i<maxn;i++)for(int j=0;j<i;j++)if(b[i]>>j&1)b[i]^=b[j];
}

线性基求并

直接把 B 内的元素插入到 A 里即可。

template<typename T,int maxn>basis<T,maxn>merge(basis<T,maxn>a,basis<T,maxn>b){
  for(int i=0;i<maxn;i++)a.insert(b.b[i]);
  return a;
}

线性基求交

对于两个线性基 A,B，求一个基 C 使 C 的张成是 A,B 的张成的交。

从小到大枚举 B，假设枚举到 B_i，当前答案是 B_0\sim B_{i-1} 与 A 的交。同时动态维护一个基 A' 表示 A 和 B_0\sim B_{i-1} 的并，记录 A' 中每个元素来源于 A 的部分。

考虑加入 B_i 会让答案产生什么变化。若 B 能被 A' 表出，设 B 的表出为 a\operatorname{xor}b，其中 a,b 分别为来源于 A,B 的部分。此时对于交空间中新增的元素，即能被 A 表出，也能被 a\operatorname{xor}b 和 B_0\sim B_{i-1} 表出。设这个元素在 A 中的表出为 d，在 B_0\sim B_{i-1} 中的表出为 c，则 d=a\operatorname{xor}b\operatorname{xor}c。这说明 a\operatorname{xor}d=b\operatorname{xor}c，也就是说这个元素的表出在 B 中的部分在B_0\sim B_{i-1} 与 A 的交中。此时只需要在交中添加 a。

因此得到算法：从小到大枚举 B，维护一个基 A' 表示 A 和 B 前缀的并，若 B_i 能被 A' 表出，则在答案加入表出中来源于 A 的部分。

如下，a 为 A 与 B 前缀的并的线性基， c 为 a 中元素的表示在 A 中的部分。

template<typename T,int maxn>basis<T,maxn>merge(basis<T,maxn>a,basis<T,maxn>b){
  basis<T,maxn>c=a,ans;
  for(int i=0;i<maxn;i++){
    if(!b.b[i])continue;
    T k=0,t=b.b[i];
    for(int j=i;j>=0;j--){
      if(t>>j&1){
        if(a.b[j])k^=c.b[j],t^=a.b[j];
        else{
          c.b[j]=k,a.b[j]=t;
          break;
        }
      }
    }
    if(!t)ans.b[i]=k,ans.cnt++;
  }
  return ans;
}

前缀线性基、带删线性基

线性基不可差分，所以要通过其他方法取出区间的线性基。对于每个元素，多记录元素插入的时间，让时间尽量靠后，此时 r 的前缀线性基中时间大于等于 l 的就是 [l,r] 的线性基。

void build(int n,T b[]){
  for(int i=1;i<=n;i++){
    for(int j=0;j<maxn2;j++)a[i][j]=a[i-1][j],p[i][j]=p[i-1][j];
    int t=i,k=b[i];
    for(int j=maxn2-1;j>=0;j--){
      if(k>>j&1){
        if(!a[i][j]){
          a[i][j]=k,p[i][j]=t;
          break;
        }
        if(p[i][j]<t)swap(a[i][j],k),swap(p[i][j],t);
        k^=a[i][j];
      }
    }
  }
}

线性基的删除类似，将数据离线，让删除时间尽可能晚。

正交线性基

对于线性基 A，我们可以求出另一组基 A^\perp，使得 \operatorname{span}(A^\perp) 包含所有与 \operatorname{span}(A) 正交的向量。

在异或线性基中，\operatorname{popcount}(i\operatorname{and}j) 对应内积，下面记作 \langle i,j\rangle。正交就是 \operatorname{popcount}(i\operatorname{and}j)\bmod 2=0。由于 \mathbb F_2 不是内积空间，不便用线性代数分析。

首先，与子空间 A 正交的向量构成闭合子空间，因为与 A 正交的向量的线性组合仍然与 A 正交。

然后我们可以证明正交线性基的秩是 n-\operatorname{rank}(A)。将 A 消成最简线性基，称最高位的 1 为关键位。考虑哪些数在正交线性基中，枚举非关键位的取值，共 2^{n-\operatorname{rank}} 种，则我们可以唯一确定关键位的取值使它与线性基 A 的元素正交，因为消成最简线性基后关键位是所在的唯一的 1。

考虑怎么构造。我们有以下方式：正交线性基的关键位是线性基中没有的位，然后转置线性基的非关键位。如下图：

设两个基为 A,B。这样做完后，若 A 的第 i 行最高位是 i 位，那 B 的第 i 行最低位是 i 位。考虑 A 的 i 行和 B 的 j 行。A,B 都为 1 的位只在 i,j 之间。

对于第 i 位和第 j 位，A_{i,i} 和 B_{j,j} 为 1，A_{i,j}=B_{j,i} 是由非关键位转置过来的。

对于中间的第 k 位，若 B_{j,k}=1，则 A_{k,j}=1，因为 k 行的最高位是 k 位，则 A_{k,k}=1，A_{i,k} 必须为 0。

综上 \operatorname{popcount}(A_i\operatorname{and}B_j) 只为 0/2。

void orthogonalize(){
  rebuild();
  for(int i=0;i<maxn;i++){
    b[i]^=1ll<<i;
    for(int j=0;j<i;j++)if(b[i]>>j&1)b[i]^=1ll<<j,b[j]^=1ll<<i;
  }
}

例题

P4570

结论：一个序列的线性基大小一定。

假如有若干个数线性相关，即 \operatorname{xor}_{i=1}^nd_i=0。那么其中只有最后一个元素插不进去。此时，改变插入顺序不会改变插入个数，因为 \operatorname{xor}_{i=1}^{n-1}d_i=d_n 说明剩下的 n-1 个数可以完全代替这个数的作用。

那么贪心地从大往小插入即可。

#include<bits/stdc++.h>
using namespace std;
int n;
long long b[63],ans;
pair<int,long long>t[1005];
bool insert(long long k){
  for(int i=62;i>=0;i--){
    if(k>>i&1){
      if(!b[i])return b[i]=k,1;
      k^=b[i];
    }
  }
  return 0;
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>t[i].second>>t[i].first;
  sort(t+1,t+n+1);
  for(int i=n;i>=1;i--)if(insert(t[i].second))ans+=t[i].first;
  return cout<<ans<<'\n',0;
}

P3857

可以看作一个序列能异或出几个不同的数。求出线性基，线性基线性无关且表示原序列异或的所有可能，所以答案为 2^{cnt}，其中 cnt 为线性基大小。

#include<bits/stdc++.h>
using namespace std;
const int mod=2008;
int n,m,f;
long long ans=1,a[50];
char s[55];
void insert(long long k){
  for(int i=49;i>=0;i--){
    if(k>>i&1){
      if(!a[i]){
        a[i]=k;
        break;
      }
      k^=a[i]; 
    }
  }
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    cin>>s;
    long long t=0;
    for(int j=0;j<n;j++)t=t*2+(s[j]=='O');
    insert(t);
  }
  for(int i=0;i<n;i++)if(a[i])ans<<=1;
  return cout<<ans%mod<<'\n',0;
}

P4151

首先，这条路径由一条 1\rightsquigarrow n 的路径和一些环组成。其中路径和环的连接可以忽略，因为一来一回抵消了。那么把所有环丢进线性基，求与路径的最大异或和即可。

其中路径可以任意找，因为 1\rightsquigarrow n 的两条路径相交成若干个环，一条路径可以通过异或若干环变成其他所有路径。

此时考虑如何找出一些环，使这些环的异或能表出图上所有环。可以证明，跑出一棵生成树后，只保留包含一条非树边的环，这些环能表出图上所有环。对于任意一个环，将其异或上其包含的所有非树边对应的环。假如这样做之后还有边，一定是若干树边。而环的异或还是环，环必然有非树边，矛盾。

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long dis[50005],b[63],w;
bool vis[50005];
vector<pair<int,long long> >e[50005];
bool insert(long long k){
  for(int i=62;i>=0;i--){
    if(k>>i&1){
      if(!b[i])return b[i]=k,1;
      k^=b[i];
    }
  }
  return 0;
}
void dfs(int pos){
  vis[pos]=1;
  for(int i=0;i<e[pos].size();i++){
    if(vis[e[pos][i].first])insert(dis[pos]^e[pos][i].second^dis[e[pos][i].first]);
    else dis[e[pos][i].first]=dis[pos]^e[pos][i].second,dfs(e[pos][i].first);
  }
}
int main(){
  cin>>n>>m;
  for(int i=1,u,v;i<=m;i++)cin>>u>>v>>w,e[u].push_back(make_pair(v,w)),e[v].push_back(make_pair(u,w));
  dfs(1);
  for(int i=62;i>=0;i--)dis[n]=max(dis[n],dis[n]^b[i]);
  return cout<<dis[n]<<'\n',0;
}

P4869

考虑重复，有一个很强的结论：每种数被表出的方案数都是 2^{n-cnt}。对于不在线性基中的数可以任选，而线性基有且仅有一种方案配对。

想不考虑重复怎么做。在线性基中，若线性基在某一位所有数都是 0，则线性基表出的数在这一位都为 0，否则考虑固定基中某个在这一位为 1 的数，则线性基表出的数在这一位一半为 0，一半为 1。此时就可以直接确定一个数的排名。

#include<bits/stdc++.h>
using namespace std;
const int mod=10086;
int n,q,b[31],ans=1,cnt;
bool insert(int k){
  for(int i=30;i>=0;i--){
    if(k>>i&1){
      if(!b[i])return b[i]=k,1;
      k^=b[i]; 
    }
  }
  return 0;
}
int main(){
  cin>>n;
  for(int i=1,t;i<=n;i++){
    cin>>t;
    if(!insert(t))ans=ans*2%mod;
  }
  cin>>q;
  for(int i=0,p=1;i<=30;i++){
    if(b[i]){
      if(q>>i&1)cnt+=p;
      p=p*2%mod;
    }
  }
  return cout<<(ans*cnt+1)%mod<<'\n',0;
}

P5556

一个显然的做法是树剖+线段树+线性基。但这太逊了，一共四只 \log。

观察到线性基插入成功一次就少一个位，而线性基只有 30 个位，所以超过 30 个数就必然线性相关。用树状数组维护值，查询时直接暴力跳，把数扔掉线性基里判断即可。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],b[100005],dep[100005],fa[100005],sz[100005],son[100005],top[100005],dfn[100005],cnt;
vector<int>e[100005];
template<typename T,int maxn>struct BIT{
  T tr[maxn];
  void build(int n,T a[]){
    for(int i=1;i<=n;i++){
      tr[i]^=a[i];
      if(i+(i&-i)<=n)tr[i+(i&-i)]^=tr[i];
    }
  }
  void add(int x,T k){
    for(;x<=n;x+=(x&-x))tr[x]^=k;
  }
  T query(int x,T ans=0){
    for(;x;x-=(x&-x))ans^=tr[x];
    return ans;
  }
};
BIT<int,100005>t;
template<typename T,int maxn>struct basis{
  T b[maxn];
  bool insert(T k){
    for(int i=maxn-1;i>=0;i--){
      if(k>>i&1){
        if(!b[i])return b[i]=k,1;
        k^=b[i]; 
      }
    }
    return 0;
  }
};
basis<int,30>temp;
void dfs1(int pos,vector<int>e[]){
  dep[pos]=dep[fa[pos]]+1,sz[pos]=1;
  for(int i=0;i<e[pos].size();i++){
    if(!dep[e[pos][i]]){
      fa[e[pos][i]]=pos,dfs1(e[pos][i],e),sz[pos]+=sz[e[pos][i]];
      if(sz[e[pos][i]]>sz[son[pos]])son[pos]=e[pos][i];
    }
  }
}
void dfs2(int pos,vector<int>e[]){
  dfn[pos]=++cnt;
  if(son[pos])top[son[pos]]=top[pos],dfs2(son[pos],e);
  for(int i=0;i<e[pos].size();i++)if(!top[e[pos][i]])top[e[pos][i]]=e[pos][i],dfs2(e[pos][i],e);
}
void init(int s,vector<int>e[]){
  dfs1(s,e),fa[s]=s,top[s]=s,dfs2(s,e);
}
void add(int u,int v,int k){
  while(top[u]!=top[v]){
    if(dep[top[u]]>dep[top[v]])t.add(dfn[top[u]],k),t.add(dfn[u]+1,k),u=fa[top[u]];
    else t.add(dfn[top[v]],k),t.add(dfn[v]+1,k),v=fa[top[v]];
  }
  if(dep[u]>dep[v])swap(u,v);
  t.add(dfn[u],k),t.add(dfn[v]+1,k);
}
bool query(int u,int v){
  memset(temp.b,0,sizeof(temp));
  if(dep[u]<dep[v])swap(u,v);
  while(dep[u]!=dep[v]){
    if(!temp.insert(t.query(dfn[u])))return 1;
    u=fa[u];
  }
  while(u!=v){
    if(!temp.insert(t.query(dfn[u]))||!temp.insert(t.query(dfn[v])))return 1;
    u=fa[u],v=fa[v];
  }
  return !temp.insert(t.query(dfn[u]));
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>b[i];
  for(int i=1,u,v;i<n;i++)cin>>u>>v,e[u].push_back(v),e[v].push_back(u);
  init(1,e);
  for(int i=1;i<=n;i++)a[dfn[i]]=b[i];
  for(int i=n;i>=1;i--)a[i]^=a[i-1];
  t.build(n,a);
  for(int i=1,u,v,k;i<=m;i++){
    string opt;
    cin>>opt>>u>>v;
    if(opt=="Update")cin>>k,add(u,v,k);
    else puts(query(u,v)?"YES":"NO");
  }
  return 0;
}

P11620

线性基很难做到整体异或值。考虑差分，第一个操作变为单点修改。

设差分数组为 b。当查询 [l,r]，发现 a_i=a_l\operatorname{xor}\operatorname{xor}_{j=l+1}^i b_j。这说明 a_l,b_{[l+1,r]} 可以表出原数组，那么只需要维护 b 的基。还需要另一个树状数组维护 a 的区间修改和单点查询。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[50005];
template<typename T,int maxn>struct BIT{
  T tr[maxn];
  void add(int x,T k){
    for(;x<=n;x+=(x&-x))tr[x]^=k;
  }
  T query(int x,T ans=0){
    for(;x;x-=(x&-x))ans^=tr[x];
    return ans;
  }
};
BIT<int,50005>t;
struct basis{
  int b[31],cnt;
  basis(){
    cnt=0,memset(b,0,sizeof(b));
  }
  bool insert(int k){
    if(cnt==31)return 0;
    for(int i=30;i>=0;i--){
      if(k>>i&1){
        if(!b[i])return cnt++,abi]=k,1;
        k^=b[i];
      }
    }
    return 0;
  }
  int query(int ans){
    for(int i=30;i>=0;i--)ans=max(ans,ans^b[i]);
    return ans;
  }
};
basis tr[200005];
basis merge(basis a,basis b){
  for(int i=0;i<=30;i++)a.insert(b.b[i]);
  return a;
}
void pushup(int pos){
  tr[pos]=merge(tr[pos<<1],tr[pos<<1|1]);
}
void build(int pos,int nl,int nr,int a[]){
  if(nl==nr)tr[pos].insert(a[nl]);
  else{
    int mid=(nl+nr)>>1;
    build(pos<<1,nl,mid,a),build(pos<<1|1,mid+1,nr,a),pushup(pos);
  }
}
void add(int pos,int nl,int nr,int g,int k){
  if(nl==nr){
    tr[pos]=basis(),tr[pos].insert(k);
    return;
  }
  int mid=(nl+nr)>>1;
  if(g<=mid)add(pos<<1,nl,mid,g,k);
  if(g>mid)add(pos<<1|1,mid+1,nr,g,k);
  pushup(pos);
}
basis query(int pos,int nl,int nr,int gl,int gr){
  if(gl<=nl&&nr<=gr)return tr[pos];
  int mid=(nl+nr)>>1;
  basis ans;
  if(gl<=mid)ans=merge(ans,query(pos<<1,nl,mid,gl,gr));
  if(gr>mid)ans=merge(ans,query(pos<<1|1,mid+1,nr,gl,gr));
  return ans;
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=n;i>=1;i--)a[i]^=a[i-1],t.add(i,a[i]);
  build(1,1,n,a);
  for(int i=1,opt,l,r,k;i<=m;i++){
    cin>>opt>>l>>r>>k;
    if(opt==1){
      t.add(l,k),add(1,1,n,l,a[l]^=k);
      if(r<n)t.add(r+1,k),add(1,1,n,r+1,a[r+1]^=k);
    }
    else{
      basis temp;
      if(l<r)temp=query(1,1,n,l+1,r);
      temp.insert(t.query(l)),cout<<temp.query(k)<<'\n';
    }
  }
  return 0;
}

另外，有更加简单的随机化做法。对于一些数，我们从中选若干子集的异或和，将这些数的基当成整组数的线性基。假如这个基比真实的基少了元素，那么空间的大小会减半，这要求我们选出的每个子集的异或和都落在剩下的一半空间，也就是正确率约为 2^{-k}，k 为选出的子集数。对于此题，差分变为单点修改，维护 50 个序列，每个位置有一半的概率为 a_i 或 0，每个序列用 BIT 维护异或和，修改某数时只修改包含这个数的序列。原序列的 a_l 也用 BIT 维护。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[50005],tr[55][50005],b[30];
bool vis[50005][55];
void add(int x,int k,int id){
  for(;x<=n;x+=x&-x)tr[id][x]^=k;
}
int query(int x,int id,int ans=0){
  for(;x;x-=x&-x)ans^=tr[id][x];
  return ans;
}
bool insert(int k){
  while(k){
    int i=31-__builtin_clz(k);
    if(!b[i])return b[i]=k,1;
    k^=b[i]; 
  }
  return 0;
}
int main(){
  srand(time(0)),ios::sync_with_stdio(0),cin.tie(0),cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=0;i<=50;i++)for(int j=1;j<=n;j++)if(!i||rand()&1)add(j,a[j]^a[j-1],i),vis[j][i]=1;
  for(int i=1,opt,l,r,k;i<=m;i++){
    cin>>opt>>l>>r>>k;
    if(opt==1){
      for(int j=0;j<=50;j++)if(vis[l][j])add(l,k,j);
      for(int j=0;j<=50;j++)if(vis[r+1][j])add(r+1,k,j);
    }
    else{
      memset(b,0,sizeof(b));
      for(int j=0;j<=50;j++)insert(j?query(r,j)^query(l,j):query(l,j));
      for(int j=29;j>=0;j--)k=max(k,k^b[j]);
      cout<<k<<'\n';
    }
  }
  return 0;
}

AT_arc155_e

首先对于集合 T，f(T) 的线性基大小比 T 最多少 1，因为设 T 的线性基是 e_{1\sim k}，f(T) 中就有 e_i\operatorname{xor}e_1(2\leq i\leq k)。而若 T 中有 0，f(T) 中有 e_{1\sim k}，f(T) 的线性基大小就和 T 相同。

设当前 S 的线性基大小为 k，我们将 k_1 个基分到 T_1，k_2 个基分到 T_2，满足 k_1+k_2=k，由上面得 f(T_1)\cup f(T_2) 的线性基大小至少为 k_1+k_2-2。而除了第一次操作外，S 中都有 0，此时 0 分到的一边线性基大小和 T 相同，则 f(T_1)\cup f(T_2) 的线性基大小至少为 k_1+k_2-1。发现这总是能做到的，将 S 中表示含有 e_1 的放到 T_1，其他放到 T_2，则 f(T_1) 中 e_1 就没了。

对于第一次操作，我们可以将所有数都异或上 a_1，因为这总不改变 f。答案就是线性基大小。注意 n=1 没有第一次操作。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
bitset<305>a[305];
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>a[i];
  if(n==1)return puts(a[1].any()?"1":"0"),0;
  for(int i=2;i<=n;i++)a[i]^=a[1];
  for(int c=0,r=2;c<m;c++){
    int pos=r;
    while(pos<=n&&!a[pos][c])pos++;
    if(pos>n)continue;
    swap(a[r],a[pos]);
    for(int j=r+1;j<=n;j++)if(a[j][c])a[j]^=a[r];
    ans++,r++;
  }
  return cout<<ans<<'\n',0;
}

UOJ698

能被 1,2,3,\cdots 表出等于能被这几个集合的交的线性基表出。所以可以做线性基前缀交，二分第一个不能被表出的位置。O(n\log^2V)-O(\log n\log V)，大概 1e9，寄。

观察性质，答案位置上的线性基一定比上一个位置少了数，而线性基只有 \log V 的位置，有效位置也是 \log V，在这里面二分，O(n\log^2V)-O(\log V\log\log V)。如果实现太烂会被卡。

更好的做法是取出每一位消失前最后出现的元素建出一个新基，答案为组合出 x 的元素的最早消失时间。O(n\log^2V)-O(\log V)。

#include<bits/stdc++.h>
using namespace std;
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T &a){
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename... Args>void in(T &a,Args&...args){
  in(a),in(args...);
}
int n,q,p[70],cnt;
unsigned long long x;
struct basis{
  unsigned long long b[64];
  int cnt;
  basis(){
    memset(b,0,sizeof(b)),cnt=0;
  }
  bool insert(unsigned long long k,bool f){
    if(cnt==64)return 0;
    for(int i=63;i>=0;i--){
      if(k>>i&1){
        if(!b[i]){
          if(f)b[i]=k,cnt++;
          return 1;
        }
        k^=b[i];
      }
    }
    return 0;
  }
};
basis t[100005],c,ans;
basis merge(basis a,basis b){
  c=a,ans=basis();
  for(int i=0;i<64;i++){
    if(!b.b[i])continue;
    unsigned long long k=0,t=b.b[i];
    for(int j=i;j>=0;j--){
      if(t>>j&1){
        if(a.a[j])k^=c.b[j],t^=a.b[j];
        else{
          c.b[j]=k,a.b[j]=t;
          break;
        }
      }
    }
    if(!t)ans.b[i]=k,ans.cnt++;
  }
  return ans;
}
int main(){
  in(n,q);
  for(int i=1,k;i<=n;i++){
    in(k);
    for(int j=1;j<=k;j++)in(x),t[i].insert(x,1);
  }
  for(int i=2;i<=n;i++)t[i]=merge(t[i],t[i-1]);
  for(int i=0;i<64;i++)for(p[i]=1;t[p[i]].b[i];p[i]++);
  while(q--){
    in(x);
    int ans=n+1;
    for(int i=63;i>=0;i--)if(x>>i&1)ans=min(ans,p[i]),x^=t[p[i]-1].b[i];
    cout<<ans<<'\n';
  }
  return 0;
}

P3733

根据 P4151的经验，可以将初始的环扔进线性基，加边时在线性基中加入 dis_x\operatorname{xor}dis_y\operatorname{xor}z，离线后使用带删线性基。修改等于先删除后插入。 `

#include<bits/stdc++.h>
using namespace std;
int n,m,q,cnt1,cnt2,id[1005],p[1005];
struct query{
  int u,v,t;
  bitset<1000>w;
}a[1005];
bool vis[505];
bitset<1000>dis[505],w;
struct basis{
  bitset<1000>b[1000];
  int p[1000];
  bool insert(bitset<1000>k,int t){
    for(int i=999;i>=0;i--){
      if(k[i]){
        if(t>p[i])swap(k,b[i]),swap(t,p[i]);
        if(!t)return 1;
        k^=b[i]; 
      }
    }
    return 0;
  }
  bitset<1000>query1(int t){
    bitset<1000>ans;
    for(int i=999;i>=0;i--)if(p[i]>t&&!ans[i])ans^=b[i];
    return ans;
  }
};
basis t;
vector<pair<int,bitset<1000>>>e[505];
void dfs(int pos){
  vis[pos]=1;
  for(int i=0;i<e[pos].size();i++){
    if(vis[e[pos][i].first])t.insert(dis[pos]^e[pos][i].second^dis[e[pos][i].first],q+1);
    else dis[e[pos][i].first]=dis[pos]^e[pos][i].second,dfs(e[pos][i].first);
  }
}
int main(){
  cin>>n>>m>>q,cnt2=q+1;
  for(int i=1,u,v;i<=m;i++)cin>>u>>v>>w,e[u].push_back(make_pair(v,w)),e[v].push_back(make_pair(u,w));
  dfs(1);
  for(int i=1,x,y;i<=q;i++){
    string opt;
    cin>>opt;
    if(opt=="Add")cin>>x>>y>>w,id[i]=++cnt1,a[cnt1]=query{x,y,q+1,w},p[cnt1]=cnt1;
    else if(opt=="Cancel")cin>>x,a[p[x]].t=i;
    else cin>>x>>w,a[p[x]].t=i,id[i]=--cnt2,a[cnt2]=query{a[p[x]].u,a[p[x]].v,q+1,w},p[x]=cnt2;
  }
  for(int i=0;i<=q;i++){
    if(id[i])t.insert(dis[a[id[i]].u]^a[id[i]].w^dis[a[id[i]].v],a[id[i]].t);
    bitset<1000>ans=t.query1(i);
    int j=999;
    while(!ans[j])j--;
    for(;j>=0;j--)putchar(ans[j]?'1':'0');
    putchar('\n');
  }
  return 0;
}

实数线性基

实数线性基的定义类似，都是维护出最多的线性无关的向量表出所给的向量。同样钦定线性基中第 i 个向量的最高位为 i，消元时把异或消元变为正常的消元即可。

P3265

类似异或的情况，将向量按价值从小到大插入线性基即可。可以用 double 计算，也可模一个大质数。

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000009;
int n,m,cnt,sum;
struct vec{
  int v[505],c;
}z[505],a[505];
bool cmp(vec a,vec b){
  return a.c<b.c;
}
template<typename T>T qpow(T a,T b,T n,T ans=1){
  for(a%=n;b;b>>=1)b&1&&(ans=1ll*ans*a%n),a=1ll*a*a%n;
  return ans;
}
template<typename T>T inv(T a,T b){
  return qpow(a,b-2,b);
}
bool insert(vec k){
  for(int i=1;i<=m;i++){
    if(k.v[i]){
      if(!a[i].c)return a[i]=k,a[i].c=1;
      int t=1ll*k.v[i]*inv(a[i].v[i],mod)%mod;
      for(int j=i;j<=m;j++)k.v[j]=(k.v[j]-1ll*t*a[i].v[j]%mod+mod)%mod;
    }
  }
  return 0;
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>z[i].v[j];
  for(int i=1;i<=n;i++)cin>>z[i].c;
  sort(z+1,z+n+1,cmp);
  for(int i=1;i<=n;i++)if(insert(z[i]))cnt++,sum+=z[i].c;
  return cout<<cnt<<' '<<sum<<'\n',0;
}

CF1336E2

建出线性基，我们知道这些数表出数的方案数都是 2^{n-\operatorname{rank}(A)}。这是经典结论，因为基外数任选，基内有唯一的方式表出。

现在已经有一个 O(2^{\operatorname{rank}(A)}) 的暴力。考虑用 FWT 研究，假设我们现在有两个集合幂级数 f_i=[i\in\operatorname{span}(A)],g_i=[\operatorname{popcount}(i)=c]，则 \operatorname{popcount} 为 c 的选法是 [x^\varnothing]fg=\operatorname{IFWT}(\operatorname{FWT}(f)\cdot\operatorname{FWT}(g))，也就是异或卷积。

研究 \operatorname{FWT}(f) 的点值，有 \operatorname{FWT}(f)_i=\sum_{j=0}^{2^m-1}(-1)^{\langle i,j\rangle}f_j。注意到这等于 0 或 2^{\operatorname{rank}(A)}，有值当且仅当与 A 正交。将 \operatorname{span}(A) 也就是 f 有值的位置用线性基表出，因为内积有对异或分配律，若 i 和其中一个元素不正交，就可以翻转这个选取状态构造双射。那么 \operatorname{FWT}(f) 有值的位置就是 \operatorname{span}(A^\perp)。

再研究 g 的点值，发现只和 \operatorname{popcount} 有关。枚举 j 和 i 的交集大小，内外是组合数，\operatorname{popcount} 为 k 的位置点值是 \sum_{i=0}^k(-1)^iC_k^iC_{m-k}^{c-i}。因此统计 \operatorname{span}(A^\perp) 中每种 \operatorname{popcount} 的选法就可以算出所有位置的和，[x^\varnothing]\operatorname{IFWT} 就是所有位置加起来除以 2^m。

因为正交线性基的秩是 n-\operatorname{rank}(A)，两个暴力取较小的就是 O(2^\frac m2)。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,rk,cnt[54],C[54][54];
long long a;
template<typename T,int maxn>struct basis{
  T b[maxn];
  basis(){
    memset(b,0,sizeof(b));
  }
  bool insert(T k){
    while(k){
      int d=__lg(k);
      if(!b[d])return b[d]=k,1;
      k^=b[d];
    }
    return 0;
  }
  void rebuild(){
    for(int i=0;i<m;i++)for(int j=0;j<i;j++)if(b[i]>>j&1)b[i]^=b[j];
  }
  void orthogonalize(){
    rebuild();
    for(int i=0;i<m;i++){
      b[i]^=1ll<<i;
      for(int j=0;j<i;j++)if(b[i]>>j&1)b[i]^=1ll<<j,b[j]^=1ll<<i;
    }
  }
};
basis<long long,53>b;
template<typename T>T qpow(T a,T b,T n,T ans=1){
  for(a%=n;b;b>>=1)b&1&&(ans=1ll*ans*a%n),a=1ll*a*a%n;
  return ans;
}
void solve(){
  vector<long long>v;
  long long now=0;
  for(int i=0;i<m;i++)if(b.b[i])v.push_back(b.b[i]);
  cnt[0]=1;
  for(int i=1;i<v.size();i++)v[i]^=v[i-1];
  for(int i=1;i<1<<v.size();i++)now^=v[__builtin_ctz(i)],cnt[__builtin_popcountll(now)]++;
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>a,rk+=b.insert(a);
  if(rk<=m/2){
    solve();
    for(int i=0;i<=m;i++)cout<<1ll*qpow(2,n-rk,mod)*cnt[i]%mod<<(i==m?'\n':' ');
    return 0;
  }
  b.orthogonalize(),solve();
  for(int i=0;i<=m;i++)for(int j=0;j<=i;j++)C[i][j]=j?(C[i-1][j]+C[i-1][j-1])%mod:1;
  for(int i=0;i<=m;i++){
    int ans=0;
    for(int j=0;j<=m;j++)for(int k=max(i+j-m,0);k<=min(i,j);k++)ans=(ans+1ll*(k&1?mod-1:1)*cnt[j]%mod*C[j][k]%mod*C[m-j][i-k])%mod;
    cout<<1ll*qpow(2,(n-m+mod-1)%(mod-1),mod)*ans%mod<<(i==m?'\n':' ');
  }
  return 0;
}