专栏文章

线性基 学习笔记

xxujindong_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minuwv7g
此快照首次捕获于
2025/12/02 08:45
3 个月前
此快照最后确认于
2025/12/02 08:45
3 个月前
查看原文

异或线性基

把每一个二进制数的看作一个位数维的向量，异或相当于模二意义下的加法，这样的线性基为异或线性基。异或线性基就是对于给定的数，求出一组数，从中选数异或能产生给定数异或的所有结果，且这组数的数量最小。
异或线性基解决的问题一般会从序列里挑任意个数异或起来。根据定义，线性基的异或能表示原序列异或的所有可能，而且线性基大小只有位数个，减少了复杂度。

插入

钦定线性基中每个数的最高有效位不同。
如果当前数插入后线性相关了，就不插，因为这个数在线性基中的组合能完全替代这个数的作用。否则需要插入。
从高位向低位遍历，如果当前位为 11 就把插入的数异或线性基的这一位元素，这保证了遍历到某一位时，更高的位都为 00。如果线性基的这一位没有则插入这个数，此时插入的值与之前异或过的数构成了原来插入的数。如果最后为零说明插不进去。
CPP
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;
}

异或最大值

从高位往低位枚举，若异或这个数能变大就贪心地异或。因为能变大说明是 0xor⁡1=10\operatorname{xor}1=1，剩下的数不会影响这一位。
CPP
T query1(T ans=0){
  for(int i=maxn-1;i>=0;i--)ans=max(ans,ans^b[i]);
  return ans;
}

异或最小值

原序列能异或出的最小值为线性基中最小值，因为其他数的最高位更高，最小值异或其他数时这些数的最高位会被保留。特别地，还要考虑有没有插入失败过。如果失败过，最小值为 00。
CPP
T query2(){
  for(int i=0;i<maxn;i++)if(b[i])return b[i];
}

异或第 k 小

从高到低贪心，若线性基这一位有值，异或与不异或会让这一位为 00 或 11，更低位任选的方案数是 2num2^{num}，numnum 是更低位线性基有值的个数。用类似的方法还可以查异或 <k<k 的个数等。
CPP
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<ji<j，若 aja_j 第 ii 位为 11 就异或 aia_i。
消元后，保证每一行的第一个 11 是这一列的唯一元素，或者说是简化行阶梯形矩阵。这也刻画了线性基代表的线性空间，若两个线性基的最简线性基相同，两者本质相同。
简化行阶梯形矩阵也简化了一些问题，如异或第 kk 小，更高位选的情况相同，选了第 ii 个比不选一定大，将 kk 二进制拆分取对应位即可。

线性基求并

直接把 BB 内的元素插入到 AA 里即可。
CPP
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,BA,B，求一个基 CC 使 CC 的张成是 A,BA,B 的张成的交。
从小到大枚举 BB，假设枚举到 BiB_i，当前答案是 B0∼Bi−1B_0\sim B_{i-1} 与 AA 的交。同时动态维护一个基 A′A' 表示 AA 和 B0∼Bi−1B_0\sim B_{i-1} 的并，记录 A′A' 中每个元素来源于 AA 的部分。
考虑加入 BiB_i 会让答案产生什么变化。若 BB 能被 A′A' 表出，设 BB 的表出为 axor⁡ba\operatorname{xor}b，其中 a,ba,b 分别为来源于 A,BA,B 的部分。此时对于交空间中新增的元素，即能被 AA 表出，也能被 axor⁡ba\operatorname{xor}b 和 B0∼Bi−1B_0\sim B_{i-1} 表出。设这个元素在 AA 中的表出为 dd，在 B0∼Bi−1B_0\sim B_{i-1} 中的表出为 cc，则 d=axor⁡bxor⁡cd=a\operatorname{xor}b\operatorname{xor}c。这说明 axor⁡d=bxor⁡ca\operatorname{xor}d=b\operatorname{xor}c，也就是说这个元素的表出在 BB 中的部分在B0∼Bi−1B_0\sim B_{i-1} 与 AA 的交中。此时只需要在交中添加 aa。
因此得到算法：从小到大枚举 BB，维护一个基 A′A' 表示 AA 和 BB 前缀的并，若 BiB_i 能被 A′A' 表出，则在答案加入表出中来源于 AA 的部分。
如下，a 为 AA 与 BB 前缀的并的线性基， c 为 a 中元素的表示在 AA 中的部分。
CPP
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;
}

前缀线性基、带删线性基

线性基不可差分，所以要通过其他方法取出区间的线性基。对于每个元素，多记录元素插入的时间，让时间尽量靠后，此时 rr 的前缀线性基中时间大于等于 ll 的就是 [l,r][l,r] 的线性基。
CPP
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];
      }
    }
  }
}
线性基的删除类似，将数据离线，让删除时间尽可能晚。

例题

P4570
结论：一个序列的线性基大小一定。
假如有若干个数线性相关，即 xor⁡i=1ndi=0\operatorname{xor}_{i=1}^nd_i=0。那么其中只有最后一个元素插不进去。此时，改变插入顺序不会改变插入个数，因为 xor⁡i=1n−1di=dn\operatorname{xor}_{i=1}^{n-1}d_i=d_n 说明剩下的 n−1n-1 个数可以完全代替这个数的作用。
那么贪心地从大往小插入即可。
CPP
#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
可以看作一个序列能异或出几个不同的数。求出线性基，线性基线性无关且表示原序列异或的所有可能，所以答案为 2cnt2^{cnt}，其中 cntcnt 为线性基大小。
CPP
#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⇝n1\rightsquigarrow n 的路径和一些环组成。其中路径和环的连接可以忽略，因为一来一回抵消了。那么把所有环丢进线性基，求与路径的最大异或和即可。
其中路径可以任意找，因为 1⇝n1\rightsquigarrow n 的两条路径相交成若干个环，一条路径可以通过异或若干环变成其他所有路径。
此时考虑如何找出一些环，使这些环的异或能表出图上所有环。可以证明，跑出一棵生成树后，只保留包含一条非树边的环，这些环能表出图上所有环。对于任意一个环，将其异或上其包含的所有非树边对应的环。假如这样做之后还有边，一定是若干树边。而环的异或还是环，环必然有非树边，矛盾。
CPP
#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
考虑重复，有一个很强的结论：每种数被表出的方案数都是 2n−cnt2^{n-cnt}。对于不在线性基中的数可以任选，而线性基有且仅有一种方案配对。
想不考虑重复怎么做。在线性基中，若线性基在某一位所有数都是 00，则线性基表出的数在这一位都为 00，否则考虑固定基中某个在这一位为 11 的数，则线性基表出的数在这一位一半为 00，一半为 11。此时就可以直接确定一个数的排名。
CPP
#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⁡\log。
观察到线性基插入成功一次就少一个位，而线性基只有 3030 个位，所以超过 3030 个数就必然线性相关。用树状数组维护值，查询时直接暴力跳，把数扔掉线性基里判断即可。
CPP
#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
线性基很难做到整体异或值。考虑差分，第一个操作变为单点修改。
设差分数组为 bb。当查询 [l,r][l,r]，发现 ai=alxor⁡xor⁡j=l+1ibja_i=a_l\operatorname{xor}\operatorname{xor}_{j=l+1}^i b_j。这说明 al,b[l+1,r]a_l,b_{[l+1,r]} 可以表出原数组，那么只需要维护 bb 的基。还需要另一个树状数组维护 aa 的区间修改和单点查询。
CPP
#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−k2^{-k}，kk 为选出的子集数。对于此题，差分变为单点修改，维护 5050 个序列，每个位置有一半的概率为 aia_i 或 00，每个序列用 BIT 维护异或和，修改某数时只修改包含这个数的序列。原序列的 ala_l 也用 BIT 维护。
CPP
#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
首先对于集合 TT，f(T)f(T) 的线性基大小比 TT 最多少 11，因为设 TT 的线性基是 e1∼ke_{1\sim k}，f(T)f(T) 中就有 eixor⁡e1(2≤i≤k)e_i\operatorname{xor}e_1(2\leq i\leq k)。而若 TT 中有 00，f(T)f(T) 中有 e1∼ke_{1\sim k}，f(T)f(T) 的线性基大小就和 TT 相同。
设当前 SS 的线性基大小为 kk，我们将 k1k_1 个基分到 T1T_1，k2k_2 个基分到 T2T_2，满足 k1+k2=kk_1+k_2=k，由上面得 f(T1)∪f(T2)f(T_1)\cup f(T_2) 的线性基大小至少为 k1+k2−2k_1+k_2-2。而除了第一次操作外，SS 中都有 00，此时 00 分到的一边线性基大小和 TT 相同，则 f(T1)∪f(T2)f(T_1)\cup f(T_2) 的线性基大小至少为 k1+k2−1k_1+k_2-1。发现这总是能做到的，将 SS 中表示含有 e1e_1 的放到 T1T_1，其他放到 T2T_2，则 f(T1)f(T_1) 中 e1e_1 就没了。
对于第一次操作，我们可以将所有数都异或上 a1a_1，因为这总不改变 ff。答案就是线性基大小。注意 n=1n=1 没有第一次操作。
CPP
#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,⋯1,2,3,\cdots 表出等于能被这几个集合的交的线性基表出。所以可以做线性基前缀交，二分第一个不能被表出的位置。O(nlog⁡2V)−O(log⁡nlog⁡V)O(n\log^2V)-O(\log n\log V)，大概 1e9，寄。
观察性质，答案位置上的线性基一定比上一个位置少了数，而线性基只有 log⁡V\log V 的位置，有效位置也是 log⁡V\log V，在这里面二分，O(nlog⁡2V)−O(log⁡Vlog⁡log⁡V)O(n\log^2V)-O(\log V\log\log V)。如果实现太烂会被卡。
更好的做法是取出每一位消失前最后出现的元素建出一个新基，答案为组合出 xx 的元素的最早消失时间。
CPP
#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的经验，可以将初始的环扔进线性基，加边时在线性基中加入 disxxor⁡disyxor⁡zdis_x\operatorname{xor}dis_y\operatorname{xor}z，离线后使用带删线性基。修改等于先删除后插入。 `
CPP
#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;
}

实数线性基

实数线性基的定义类似，都是维护出最多的线性无关的向量表出所给的向量。同样钦定线性基中第 ii 个向量的最高位为 ii，消元时把异或消元变为正常的消元即可。
P3265
类似异或的情况，将向量按价值从小到大插入线性基即可。可以用 double 计算，也可模一个大质数。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...