为什么说线性基插入的时候一定要高斯消元？

NewMarchqwq · 2025-08-25 15:12:41 · 闲话

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;

int gb(int S,int l,int r){return (S>>l)&((1<<(r-l+1))-1);}
void sb(int&S,int l,int r,int x){S^=(gb(S,l,r)^x)<<l;}
bool ins1(int&S,int x){
  drep(i,4,0)if (x>>i&1){
    int h=gb(S,i*5,i*5+4);
    if (h){
      x^=h;
      continue;
    }
    sb(S,i*5,i*5+4,x);
    return 1;
  }
  return 0;
}
bool ins2(int&S,int x){
  drep(i,4,0)if (x>>i&1){
    int h=gb(S,i*5,i*5+4);
    if (h){
      x^=h;
      continue;
    }
    drep(j,i-1,0)if (x>>j&1)x^=gb(S,j*5,j*5+4);
    drep(j,4,i+1){
      h=gb(S,j*5,j*5+4);
      if (h>>i&1)sb(S,j*5,j*5+4,h^x);
    }
    sb(S,i*5,i*5+4,x);
    return 1;
  }
  return 0;
}

int main() {
  {
    auto ins=ins1;
    int S=0,T=0;
    ins(S,31),ins(S,30),ins(S,28);
    ins(T,31),ins(T,30),ins(T,29);
    cout<<S<<' '<<T<<'\n';
    rep(i,0,4)cout<<gb(S,i*5,i*5+4)<<" \n"[i==4];
    rep(i,0,4)cout<<gb(T,i*5,i*5+4)<<" \n"[i==4];
  }
  {
    auto ins=ins2;
    int S=0,T=0;
    ins(S,31),ins(S,30),ins(S,28);
    ins(T,31),ins(T,30),ins(T,29);
    cout<<S<<' '<<T<<'\n';
    rep(i,0,4)cout<<gb(S,i*5,i*5+4)<<" \n"[i==4];
    rep(i,0,4)cout<<gb(T,i*5,i*5+4)<<" \n"[i==4];
  }
  return 0;
}

hhhzc