P3812

发表于 分类于
【模板】线性基

【模板】线性基

实际上是将向量转化为 01 矩阵后高斯消元简化基底。

这个板子只包括查询最大。我们再加一些奇奇怪怪的东西。

  1. 向线性基中插入一个数：

    1
    2
    3
    4
    5
    6
    inline void ins(ll x) {
      for(ll i=51;i>=0;i--) {
        if((x>>i)&1) {if(!p[i]) {p[i]=x;break;}else x^=p[i];}
        if(x==0) {tag_zero=1;return;}
      }
    }

  2. 查询 $x$ 是否能被表出：

    1
    2
    3
    inline bool ask(ll x) {
      for(ll i=51;i>=0;i--) {if((x>>i)&1) x^=p[i];}return x==0;
    }

  3. 查询可以被异或出的最大值：

    1
    2
    3
    4
    5
    inline ll askmax() {
      ll res=0;
      for(ll i=51;i>=0;i--) {if((res^p[i])>res) res^=p[i];}
      return res;
    }

  4. 查询最小值：

    1
    2
    3
    4
    inline ll askmin() {
      if(tag_zero) return 0;
      for(ll i=0;i<=51;i++) if(p[i]) return p[i];
    }

    这里记得在插入的时候记录 0 出现的标签。

  5. 查询 $k$ 小与排名：

  • 首先我们需要 rebuild 一个 $d$ 数组：

    1
    2
    3
    4
    5
    6
    7
    inline void Rebuild() {
      cnt=0;
      for(ll i=51;i>=0;i--) {
        for(ll j=i-1;j>=0;j--) {if((p[i]>>j)&1) p[i]^=p[j];}
      }
      for(ll i=0;i<=51;i++) if(p[i]) d[cnt++]=p[i];
    }

    稍微解释一下这个东西在干什么。实际上这个东西在高斯消元，把原本的倒三角形的矩阵尽量消到一个行向量中只有一个值为 1。

  • 接下来我们查询 $k$ 小。

    1
    2
    3
    4
    5
    6
    inline ll Kth(ll k) {
      if(k-tag_zero==0) return 0;k-=tag_zero;
      if(k>=(1ll<<cnt)) return -1;ll res=0;
      for(ll i=51;i>=0;i--) if((k>>i)&1) res^=d[i];
      return res;
    }

    背板当然是最方便的。

  • 查询排名：

    1
    2
    3
    4
    inline ll Rk(ll x) {
      ll res=0;for(ll i=cnt-1;i>=0;i--) if(x>=d[i]) {res+=(1<<i);x^=d[i];}
      return res+tag_zero;
    }

没了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=50;

ll n,tag_zero,cnt;

ll p[N+5],d[N+5];

inline void Ins(ll x) {
  for(ll i=51;i>=0;i--) {
    if((x>>i)&1) {if(!p[i]) {p[i]=x;break;}else x^=p[i];}
    if(x==0) {tag_zero=1;return;}
  }
}

inline ll Askmax() {
  ll res=0;
  for(ll i=51;i>=0;i--) {if((res^p[i])>res) res^=p[i];}
  return res;
}

inline ll Askmin() {
  if(tag_zero) return 0;
  for(ll i=0;i<=51;i++) if(p[i]) return p[i];
}

inline bool Ask(ll x) {
  for(ll i=51;i>=0;i--) {if((x>>i)&1) x^=p[i];}return x==0;
}

inline void Rebuild() {
  cnt=0;
  for(ll i=51;i>=0;i--) {
    for(ll j=i-1;j>=0;j--) {if((p[i]>>j)&1) p[i]^=p[j];}
  }
  for(ll i=0;i<=51;i++) if(p[i]) d[cnt++]=p[i];
}

inline ll Kth(ll k) {
  if(k-tag_zero==0) return 0;k-=tag_zero;
  if(k>=(1ll<<cnt)) return -1;ll res=0;
  for(ll i=51;i>=0;i--) if((k>>i)&1) res^=d[i];
  return res;
}

inline ll Rk(ll x) {
  ll res=0;for(ll i=cnt-1;i>=0;i--) if(x>=d[i]) {res+=(1<<i);x^=d[i];}
  return res+tag_zero;
}

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

int main() {

  n=read();

  for(ll i=1;i<=n;i++) {ll x=read();Ins(x);}

  write(Askmax());

  return 0;
}