线性基

2019-10-21 总结线性基 0 评论

线性基

求最大值

暴力从高到低位枚举，如果加入这一位的基答案会更大则加入

求异或值第小

算出所有线性基后再对于每一个有基的位消元使得没有其他的基这一位为。最后找出所有这样的基从小到大依次标号为。问第小的时候就for一遍当第项为时就异或上

Q：为什么多了对每一位有基的位消元这一步？

A：因为这样就能保证对于所有，且一旦异或上一个那么前面的的一共种选/不选方式的值都不如这里选了，当前的排名自然就，于是这样做就是可行的

注意特判如果能表示出来则要减一

求交

首先两个线性基的交也是个线性基，因为比如且那么一定有（即如果两个线性基都能表示出和那么它们也一定都能表示出）

然后有个引理就是：线性基是线性基和的交当且仅当和也可组成一个线性基（即和线性无关）

充分性：

即如果是和的交那么和线性无关。考虑如果和线性相关的话就相当于和还有交，与条件矛盾。

必要性：

即如果和线性无关则是与的交。考虑一个如果是和的交且不能用表示，那么即和线性相关，又因为能表示那么一定是由那部分表示的，并且也可以表示出那么与都能表示出，所以两者不是线性无关与条件矛盾。

然后考虑依次加入中每个基且保证加入前和线性无关：

如果它不能能够被和表示则它一定不是 和的交可以不管。（它属于）
如果它可以被和表示则我们考虑换基。把用表示，比如（这时候有交出现了：且不能在中直接加入因为单凭无法表示）我们把换成再加入中，那么可以发现能表示的东西不变，且此时与又线性无关了

struct Base{
  ll r[N];
  inline base(){memset(r,0,sizeof r);}
  inline void ins(ll x){
    for(int i=N-1;~i;i--)if(x>>i&1){
      if(!r[i]){
        r[i]=x;
        return;
      }else x^=r[i];
    }
  }
  inline const int& operator [] (const int &x)const{return r[x];}
  inline int& operator [](int x){return r[x];}
  inline base operator +(const base &t)const{
    base b,c=*this,ans;
    for(int i=0;i<N;i++)if(t[i]){
      ll v=t[i],vb=t[i],flag=1;
      for(int j=N-1;~j;j--)if(v>>j&1){
        if(c[j]){
          v^=c[j];
          vb^=b[j];
        }else{
          c[j]=v;
          b[j]=vb;
          flag=0;
          break;
        }
      }
      if(flag) ans.ins(vb);
    }
    return ans;
  }
};

删除

（保证删除的向量一定之前插入过）

方法一

离线，以时间为下标线段树分治，但要事先知道每个向量的出现时间段

方法二

离线，对每个向量记录他还有多久被删去，插入时如果比这一位的基后删则交换一下，把的这个作为基并继续插入之前这一位的基，删除时看一下剩下的是不是它，是的话直接删就行这玩意想半天觉得很假发现确实是假的（比如先插一个和现在就剩个和，再把删了应该剩下实际上剩下）怪不得 http://uoj.ac/problem/91 只有两个人的题解写这个还写的基本上一模一样……都了

实际上挂是那两个人写假了正确性是没问题的比如插入和先删除那么插入时会把换成再插入。删除时实际上是什么也不做，查询时只考虑删除时间大于当前时间的基向量。

然后有个问题就是这样做的正确性：大概是考虑一个被删除的向量，考虑它出现的最低的个基向量（也即是它最后插入的位置）比它低的位一定不含它（因为已经在这里插入了），比它高的位中

不包含它的，删不删除它不影响
包含他，意味着之前存在某个时间当前这一位的被删除时间晚于包含它的那一位包含的某个向量，那之后被删除的这一位跑下来肯定是因为有比其更晚被删除的加入，那么　被换后往下走时一定会经过　且被删除时间晚于那么就应该是换成往下走，这与　最终位置比　位置高矛盾，所以得到不存在比当前这一位高的含有这个被删除的向量

（只是当前这一位基可能是由以前的向量和这一个要被删除的向量构成，但还是只有它这一位基含有这个向量，只删除这一个基就行）

例题：UOJ91

Description

我有一个数列每个都是小于的非负整数。现在请您实现三种操作，格式说明如下：：对于所有，将修改为。其中是一个小于的非负整数。：对于所有，将修改为。其中是一个小于的非负整数。 33：从中选出若干个数，使得选出的数异或和最大。请输出这个最大值。这里表示按位异或运算，的异或和是指。

Constraints

Solution

首先原序列差分后的线性基和原序列的线性基等价

那么每次操作就只有修改两个位置或者删除一段区间的向量

把修改看成删除再插入，即把上一个当前位置的向量的出现时间右端点改成当前，把插入新的值的出现时间设为

离线后按照上面的做即可，复杂度　

#include<bits/stdc++.h>
#define FIO "uoj91"
#define ll long long

using namespace std;

const int N=2e3+5,M=N<<2;

#define bs bitset<N>

int n,m,q;
bs a[N],b[N];
char s[N];

inline bs rd(){
  bs a;
  scanf("%s",s);
  reverse(s,s+m);
  for(int i=0;i<m;i++)a[i]=s[i]-'0';
  return a;
}

int l[M],r[M],h[N],cnt;
bs w[M];
inline void add(int id,int tim){
  ++cnt;
  w[cnt]=b[id];
  l[cnt]=tim;
  r[cnt]=q;
  r[h[id]]=tim-1;
  h[id]=cnt;
}

int id[M],rig[N];
//!!! id -> M
inline bool cmp(const int &a,const int &b){
  return l[a]<l[b];
}

bs bas[N];
inline void ins(bs v,int r,int l){
  for(int i=m-1;~i;i--)if(v[i]){
    if(rig[i]<l){rig[i]=r;bas[i]=v;return;}
    if(rig[i]<r)swap(rig[i],r),swap(v,bas[i]);
    v^=bas[i];
  }
}

inline bs qry(int tim){
  bs ret;
  for(int i=m-1;~i;i--)if(rig[i]>=tim&&!ret[i])
    ret^=bas[i];
  return ret;
}

bool isq[N];

int main(){
  freopen(FIO".in","r",stdin);
  freopen(FIO".out","w",stdout);
  scanf("%d%d%d",&n,&m,&q);
  for(int i=1;i<=n;i++){
    a[i]=rd();
    b[i]=a[i]^a[i-1];
    add(i,1);
  }
  for(int i=1;i<=q;i++){
    int opt,x,y;
    bs w;
    scanf("%d",&opt);
    switch(opt){
      case 1:{
               scanf("%d%d",&x,&y);w=rd();
               for(int j=x;j<=y;j++)
                 a[j]^=w;
               b[x]^=w;
               add(x,i);
               if(y^n){
                b[y+1]^=w;
                add(y+1,i);
               }
               break;
             }
      case 2:{
               scanf("%d%d",&x,&y);w=rd();
               for(int j=x;j<=y;j++){
                 a[j]=w;
                 //!!! = not ^=
                 if(j>x&&h[j]){
                   r[h[j]]=i-1;
                   b[j].reset();
                   h[j]=0;
                 }
                }
               b[x]=w^a[x-1];
               add(x,i);
               if(y^n){
                b[y+1]=w^a[y+1];
                add(y+1,i);
               }
               break;
             }
      case 3:{
               isq[i]=1;
               break;
             }
    }
  }

  for(int i=1;i<=cnt;i++)id[i]=i;
  sort(id+1,id+cnt+1,cmp);

  for(int i=1,j=1;i<=q;i++){
    while(j<=cnt&&l[id[j]]<=i)ins(w[id[j]],r[id[j]],i),j++;
    if(isq[i]){
      bs ans=qry(i);
      for(int i=m-1;~i;i--)printf("%d",(int)ans[i]);
      puts("");
    }
  }

  return 0;
}

方法三

以上两种方法都需要离线，我们考虑一个在线做法：对于每个基向量，维护其是由那些向量构成的（如果插入失败即这个向量能用之前的一些向量表示同样记录它是由那些表示的，即记录哪些之前的向量异或当前的可以得到）

每次删除向量时考虑分类讨论

如果存在之前的某个的构成包含，则用构成那个的其他的向量代替出现在其他基或其他向量中的比如之前有（其中是某个基的向量，是某个插入失败的向量）那么比如要删除，由左式得到，把所有出现的地方换成再删掉这个即可（这个就相当于代替了的作用，并且由于被删除，这个式子不能再用来把其他项换回来）（比如把换成）
如果不存在某个包含的可以被和表示出来，那么被删除后一定会降秩。找到最低的包含的基向量，把其他高于它也包含的异或上这一个基向量（它们对应的向量的构成也要异或），这样其他的基所表示的东西不变（一个基向量异或另一个基向量前后总的线性空间大小肯定不变），且只有这一个基向量含有了，那么就只删除这一个基就行。（这里不用考虑向量因为到了这一步就说明没有包含的）

刚才那题的用这个写法实现在线，可以见　https://www.cnblogs.com/daklqw/p/11545965.html

然后有道强制在线的题：UOJ453

Description

给定的矩阵，求有多少对分别是和的矩阵、满足

有组询问，每个询问会对的一行进行修改并求答案，强制在线

Constraints

Solution

左乘一个矩阵相当于对矩阵进行行线性变换，右乘一个矩阵相当于对矩阵进行列线性变换

发现答案只与的秩有关，两个秩相同的的答案可以相互转换一一对应，算出所有的秩为的答案之和再除以秩为的矩阵个数就是答案

对于一特定的秩为的矩阵和特定的矩阵，矩阵的每一列就对应一个线性变换到的那一列的方法，对于特定的和的这一列，这一列的方案数是。每一列都是这样，一共有列，得到对于特定的矩阵和，的方案数是

设行列秩为的矩阵数为

转移大概是

但我们知道对于秩为的矩阵，进行列线性变换后变成的矩阵时秩不一定还等于

考虑计算的秩是时有多少种秩为的可以由经过列线性变换得到

有个不会证的定理

的列满秩（秩为）矩阵乘上的矩阵得到的的矩阵的秩等于这个的矩阵的秩

把左边列满秩的行列矩阵看成是行列（只是最后有列全是），那么考虑所有列的线性变换就是一个任意的行列的矩阵。但是（线性变换矩阵的）最后的行没有意义因为左边只有前列有值，最后列全是。所以线性变换矩阵只有前行有用相当于一个行列的矩阵。由于我们要算乘出来行列秩为的矩阵有多少种情况，由之前的定理得到就是这个行列的秩为的情况数。

所以答案就是

带修改就是动态维护线性基的秩，照着上面的搞法做就行

可以记录一个表示第个基向量（这个只是从前往后的第个，是个标号跟它是哪一位的基无关）在第位和第位的基向量放在了第个。

如果就代表第个基向量没有插入任何一位，用它来替换其他的位置就行（相当于不用分类讨论，每次只要找含有的最小的把它删了就行，如果它是个基再把秩数减一即可）

#include<bits/stdc++.h>
#define ll long long
#define FIO "uoj453"
using namespace std;

const int N=1e3+5,MOD=1000000007;

inline int add(int a,const int &b){return (a+=b)>=MOD?a-MOD:a;}
inline int sub(int a,const int &b){return (a-=b)<   0?a+MOD:a;}
inline int mul(const int &a,const int &b){return 1ll*a*b%MOD;}
inline int& inc(int &a,const int &b){return a=add(a,b);}
inline int& dec(int &a,const int &b){return a=sub(a,b);}
inline int& pro(int &a,const int &b){return a=mul(a,b);}
inline int qpow(int a,int b){int c=1;for(;b;b>>=1,pro(a,a))if(b&1)pro(c,a);return c;}

#define bs bitset<N>

int p,q,s,m,k;
int bin[N];
int ans[N],fp[N][N],fs[N][N];
bs C[N];

int rk;

inline bs rd(){
  bs ret;
  for(int i=1,x;i<=s;i++){
    scanf("%d",&x);
    ret[i]=x;
  }
  return ret;
}

bs id[N];
int pos[N],rnk[N];

inline void ins(int x){
  pos[x]=0;
  for(int i=s;i;i--)if(C[x][i]){
    if(!rnk[i]){
      rnk[i]=x;
      rk++;
      pos[x]=i;
      break;
    }
    id[x]^=id[rnk[i]];
    C[x]^=C[rnk[i]];
  }
}

inline int erase(int x){
  int mn=s+1,now=0;
  for(int i=1;i<=p;i++)if(id[i][x]&&pos[i]<mn)now=i,mn=pos[i];
  for(int i=1;i<=p;i++)if(id[i][x]&&i^now)C[i]^=C[now],id[i]^=id[now];
  if(pos[now])rk--,rnk[pos[now]]=0,pos[now]=0;
  C[now].reset();id[now].reset();
  return now;
}

int main(){
  freopen(FIO".in","r",stdin);
  freopen(FIO".out","w",stdout);
  scanf("%d%d%d%d%d",&p,&q,&s,&m,&k);

  for(int i=1;i<=p;i++)
    C[i]=rd(),id[i][i]=1,ins(i);

  bin[0]=1;for(int i=1;i<N;i++)bin[i]=mul(bin[i-1],2);

  fp[0][0]=fs[0][0]=1;
  for(int i=1;i<N;i++){
    for(int j=0;j<=min(i,p);j++){
      fp[i][j]=mul(fp[i-1][j],bin[j]);
      if(j)inc(fp[i][j],mul(fp[i-1][j-1],sub(bin[p],bin[j-1])));
    }
    for(int j=0;j<=min(i,s);j++){
      fs[i][j]=mul(fs[i-1][j],bin[j]);
      if(j)inc(fs[i][j],mul(fs[i-1][j-1],sub(bin[s],bin[j-1])));
    }
  }

  for(int r=1;r<=min(p,q);r++){
    for(int x=r;x<=min(p,q);x++)
      inc(ans[r],mul(fp[q][x],mul(fs[x][r],qpow(2,(q-x)*s))));
    pro(ans[r],qpow(fp[s][r],MOD-2));
  }

  int lst;

  printf("%d\n",lst=ans[rk]);

  while(m--){
    int j,x;
    scanf("%d",&j);
    j=j^(k*lst);
    x=erase(j);
    C[x]=rd();
    id[x][j]=1;
    ins(x);
    printf("%d\n",lst=ans[rk]);
  }

  return 0;
}

只选偶数的线性基

比如一个矩阵只能选偶数个位置可以将所有横着或者竖着相邻的位置对插入这样一定异或出来是有偶数个有值。如果要选奇数个就最开始加入一个只有一个格子的。

对于有特殊性质的线性基的奇怪写法

比如一列最多只有两个的情况每个向量只能选或不选，求最后异或出来为的方案数

把有两个的看成是两个对应列连的一条边，把只有一个的看成是对应点上的权值

最后会形成若干个连通块使用并查集维护每个连通块的点数、边数和权值。

假设现在有一个个点条边点上的权值和是的连通块，分类讨论：

：那么这个连通块的矩阵就不满秩，只能像上面所说的表示出所有选偶数的情况。这时我们取条边的条形成一个树（必定能找到不然就不是一个连通块），其他任意的边的加入都可以由这条树边对应的向量异或出来，所以答案就是除了条边的其他任选的方案：
：除了那条可以任意表示剩余条边的情况外还有个可以单点翻转的，但是不能翻转奇数个否则无法消成，而任意偶数次都可以。我们可以任选前个单点的情况最后一个根据前面的奇偶性来选/不选，所以答案是

本文链接： https://20021123.xyz/2019/10/21/线性基/

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！

不知不觉Never Settle

Never Settle

线性基

线性基

求最大值

求异或值第 小

求交

删除

方法一

方法二

Description

Constraints

Solution

方法三

Description

Constraints

Solution

只选偶数的线性基

对于有特殊性质的线性基的奇怪写法

不知不觉Never Settle

求异或值第小