线性基学习笔记

Diposting di | Edited on

总结

线性基的题型相对比较固定，看到下面的类型基本上都是线性基了：

  1. 最大异或和
  2. 第 k 大异或和/异或和是第几大
  3. 求所有异或值的和

线性基中的题目中还用到一个技巧：

  • 任意一条 1到 n 的路径的异或和，都可以由任意一条 1 到 n 路径的异或和与图中的一些环的异或和来组合得到。

这便是线性基的全部东西了。

模板

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
struct Linear_Basis{
	long long d[65],p[65];
	int cnt;
	Linear_Basis(){
		memset(d,0,sizeof(d));
		memset(p,0,sizeof(p));
		cnt=0;
	}

	bool ins(long long val){
		for (int i=62;i>=0;i--) {
			if (val&(1LL<<i)){
				if (!d[i]){
					d[i]=val;
					break;
				}
				val^=d[i];
			}
		}
		return val>0;
	}

	long long query_max(long long D=0LL){
		long long ret=D;
		for (int i=62;i>=0;i--)
			if ((ret^d[i])>ret) ret^=d[i];
		return ret;
	}

    long long query_min(long long D=0LL){
        long long ret=D;
        for(int i=0;i<=62;i++){
            if(d[i]) ret^=d[i];
        }
        return ret;
    }

	void rebuild(){
		for (int i=1;i<=62;i++)
			for (int j=0;j<i;j++)
				if (d[i]&(1LL<<j)) d[i]^=d[j];
		cnt=0;
		for (int i=0;i<=62;i++)
			if (d[i]) p[cnt++]=d[i];
	}
    //第K大
	long long kthquery(long long k){
		long long ret=0;
		if (k>=(1LL<<cnt)) return -1;
		for (int i=0;i<=62;i++)
			if (k&(1LL<<i)) ret^=p[i];
		return ret;
	}
	Linear_Basis merge(const Linear_Basis &n1,const Linear_Basis &n2){
	    Linear_Basis ret=n1;
	    for(int i=62;i>=0;i--)
            if(n2.d[i])ret.ins(n2.d[i]);
        return ret;
	}
};

A.BZOJ-2460 [BeiJing2011]元素

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
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1e5+50;
//线性基
struct Linear_Basis{
	long long d[65],p[65];
	int cnt;
	Linear_Basis(){
		memset(d,0,sizeof(d));
		memset(p,0,sizeof(p));
		cnt=0;
	}

	bool ins(long long val){
		for (int i=62;i>=0;i--) {
			if (val&(1LL<<i)){
				if (!d[i]){
					d[i]=val;
					break;
				}
				val^=d[i];
			}
		}
		return val>0;
	}

	long long query_max(long long D=0LL){
		long long ret=D;
		for (int i=62;i>=0;i--)
			if ((ret^d[i])>ret) ret^=d[i];
		return ret;
	}

    long long query_min(long long D=0LL){
        long long ret=D;
        for(int i=0;i<=62;i++){
            if(d[i]) ret^=d[i];
        }
        return ret;
    }

	void rebuild(){
		for (int i=1;i<=62;i++)
			for (int j=0;j<i;j++)
				if (d[i]&(1LL<<j)) d[i]^=d[j];
		cnt=0;
		for (int i=0;i<=62;i++)
			if (d[i]) p[cnt++]=d[i];
	}
    //第K大
	long long kthquery(long long k){
		long long ret=0;
		if (k>=(1LL<<cnt)) return -1;
		for (int i=0;i<=62;i++)
			if (k&(1LL<<i)) ret^=p[i];
		return ret;
	}
};
struct node{
    ll a,b;
    bool operator <(node a)const{
        return this->b>a.b;
    }
}my[1100];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    Linear_Basis LB=Linear_Basis();
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>my[i].a>>my[i].b;
    }
    sort(my,my+n);
    ll ans=0;
    for(int i=0;i<n;i++){
        if(LB.ins(my[i].a))ans+=my[i].b;
    }
    cout<<ans<<endl;
    return 0;
}