【BZOJ 4568】【SCOI 2016】幸运数字&线性基详解

线性基资料来自： http://blog.csdn.net/qaq__qaq/article/details/53812883

看了一下线性基，感觉这个东西很强啊，总算找到了一个关于异或的比较强的性质。

定义

设数集T的值域范围为[1,2n−1]。 T的线性基是T的一个子集A={a1,a2,a3,…,an}。 A中元素互相xor所形成的异或集合，等价于原数集T的元素互相xor形成的异或集合。

理解为an最高位为第n位，an-1最高位为n-1位……a1最高位为第一位，这样一来如果要组合出T中的一个数，首先根据最高位判断是否使用an，然后根据次高位判断是否使用an-1，以此类推到最后一位。 由此可知，如果有若干个不超过2^n的数，这些数的线性基中最多只有n个数。

性质

1.设线性基的异或集合中不存在0。 2.线性基的异或集合中每个元素的异或方案唯一。 3.线性基二进制最高位互不相同。 4.如果线性基是满的，它的异或集合为[1,2n−1]。 5.线性基中元素互相异或，异或集合不变。

1是显然的，因为如果一个子集异或为0，则这个子集一定能划分成两个集合，这两个集合的异或相等。这样一来就出现了重复情况；由此就可以推得2；3就是根据定义（就这么理解好了）；4其实是对“满线性基”下的定义；5说明同一个T可能有多的不同的线性基。

维护

插入

从最高位开始，如果当前位为1，就用线性基中的数对它取异或。如果这个时候线性基中没有当前位为1的数，说明这个线性基不能组合出这个数，把这个数加入线性基中。

void insert(ll *ff,ll x) { int i; fd(i,60,0) if (x >> i & 1ll) if (!ff[i]) {ff[i] = x; return;} else x ^= ff[i]; }

合并

假设合并f和g两个线性基，对于g中的每个元素，判断f能否异或出这个数，如果不能则加入线性基。实际上是调用若干次insert操作。

void Merge(ll *ff,ll *gg) { int i; fd(i,60,0) if (gg[i]) insert(ff,gg[i]); }

查询

存在性

和插入操作相同，如果做完变为0，说明组合出了当前数，也就相当于存在，反之则不存在。

最大值

线性基最为强大之处——logn时间内查询。每次只需直接异或，看是否能够更大。

最小值

最小值就不要这么麻烦啦！直接取出最小的线性基就好啦！

k小值

首先根据性质5，我们将线性基中的元素相互异或，使得每个数除了最高位是1其他都是0。然后k的哪一位是1就异或上对应的线性基。这个查询因为本题不需要我也没有仔细看。

对于本题来说，和普通的倍增求树上两点之间最大边权一模一样，因为异或和最大值一样满足交换律和结合律，因此直接跑倍增。 由此受到启发，本题也可用树剖来做。

#include<cmath> #include<cstdio> #include<vector> #include <queue> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mod 1000000007 #define N 20005 #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; int nxt[N*2],head[N],tar[N*2],dep[N],fa[N][16]; ll f[N][16][65],res[65]; int tot,n,m,i,j,u,v; ll x; void link(int u,int v) {nxt[++tot] = head[u]; head[u] = tot; tar[tot] = v;} void insert(ll *ff,ll x) { int i; fd(i,60,0) if (x >> i & 1ll) if (!ff[i]) {ff[i] = x; return;} else x ^= ff[i]; } void Merge(ll *ff,ll *gg) { int i; fd(i,60,0) if (gg[i]) insert(ff,gg[i]); } void dfs(int x,int ftr) { dep[x] = dep[ftr] + 1; fa[x][0] = ftr; for (int i = head[x]; i ; i = nxt[i]) if (tar[i] != ftr) dfs(tar[i],x); } void multi() { int i,j,k; fo(j,1,15) fo(i,1,n) { fa[i][j] = fa[fa[i][j-1]][j-1]; fo(k,0,60) f[i][j][k] = f[i][j-1][k]; Merge(f[i][j],f[fa[i][j-1]][j-1]); } } void lca(int x,int y) { int i; if (dep[x] < dep[y]) swap(x,y); fd(i,15,0) if (dep[fa[x][i]] >= dep[y]) { Merge(res,f[x][i]); x = fa[x][i]; } if (x == y) {Merge(res,f[x][0]); return;} fd(i,15,0) if (fa[x][i] != fa[y][i]) { Merge(res,f[x][i]); Merge(res,f[y][i]); x = fa[x][i]; y = fa[y][i]; } Merge(res,f[x][0]); Merge(res,f[y][0]); Merge(res,f[fa[x][0]][0]); } int main() { scanf("%d%d",&n,&m); fo(i,1,n) {scanf("%lld",&x); insert(f[i][0],x);} fo(i,1,n-1) { scanf("%d%d",&u,&v); link(u,v); link(v,u); } dfs(1,0); multi(); fo(i,1,m) { memset(res,0,sizeof(res)); scanf("%d%d",&u,&v); lca(u,v); ll sum = 0; fd(j,60,0) sum = max(sum,sum^res[j]); printf("%lld\n",sum); } return 0; }