1
template<typename T>
2
class LinearBasis{
3
private:
4
    int BITMAX;
5
    bool zero;  // 是否存在（能合成或自带的0）
6

7
    vector<T> b;
8
    bool outdate;
9

10
public:
11
    vector<T> p;
12
    void rebuild(){
13
        if (outdate==false)
14
            return ;
15
        int cnt=0;
16
        b.clear();
17
        for (int i=0;i<BITMAX;i++){
18
            for (int j=i-1;j>=0;j--)
19
                if (p[i]&(1LL<<j))
20
                    p[i]^=p[j];
21
            if (p[i])
22
                b.push_back(p[i]);
23
        }
24
        outdate=false;
25
    }
26

27
    LinearBasis(int BITMAX=sizeof(T)*8):
28
        BITMAX(BITMAX),zero(false),outdate(false){
29
        p.resize(BITMAX,0);
30
    }
31
    void insert(T x){
32
        for (int i=BITMAX-1;i>=0;i--){
33
            if (x&(1LL<<i)){
34
                if (!p[i]){
35
                    p[i]=x,outdate=true;
36
                    return ;
37
                }
38
                x^=p[i];
39
            }
40
        }
41
        if (x==0)
42
            zero=true;
43
    }
44
    bool check(T x){
45
        for (int i=BITMAX-1;i>=0;i--)
46
            if (x&(1LL<<i)){
47
                if (!p[i])
48
                    return false;
49
                x^=p[i];
50
            }
51
        return true;
52
    }
53
    T query_max(){
54
        T ans=0;
55
        for (int i=BITMAX-1;i>=0;i--)
56
            if ((ans^p[i])>ans)
57
                ans^=p[i];
58
        return ans;
59
    }
60
    T query_min(T k=1){
61
        k-=zero;
62
        if (k==0)
63
            return 0;
64
        rebuild();
65
        if (k>=(1LL<<b.size()))
66
            return -1;
67
        ll ans=0;
68
        for (int i=0;i<b.size();i++)
69
            if (k&(1LL<<i))
70
                ans^=b[i];
71
        return ans;
72
    }
73
    int size(void){
74
        rebuild();
75
        return b.size();
76
    }
77
};
78

79
void solve(void){
80
    LinearBasis<int> lbase;  // 不知道为什么如果写成全局变量，多组数据会有点问题
81

82
}