线性基

感觉上跟高斯消元很像但是实际上好写一些。

很重要的思想是贪心。证明不会。

构造：依次考虑，如果没有就插入，有就异或。

取最大值：依次考虑，如果异或之后变大就异或。

合并：log²暴力。

性质：线性基中的元素任意异或不会为0。线性基能异或出所有成功插入进它的元素。

 1 struct Base {
 2     LL a[63];
 3     Base() {
 4         memset(a, 0, sizeof(a));
 5     }
 6     inline void insert(LL x) {
 7         for(int i = 62; i >= 0 && x; i--) {
 8             if(((x >> i) & 1) == 0) {
 9                 continue;
10             }
11             if(!a[i]) {
12                 a[i] = x;
13                 break;
14             }
15             x ^= a[i];
16         }
17         return;
18     }
19     inline LL getMax(LL ans) {
20         for(int i = 62; i >= 0; i--) {
21             if((ans ^ a[i]) > ans) {
22                 ans ^= a[i];
23             }
24         }
25         return ans;
26     }
27     inline void merge(const Base &w) {
28         for(int i = 62; i >= 0; i--) {
29             if(w.a[i]) {
30                 insert(w.a[i]);
31             }
32         }
33         return;
34     }
35 };

模板

题目：

bzoj2460 贪心插入。正确性不会。

bzoj2115 构出搜索树，发现所有环都能够取到，于是把所有环的异或和插入线性基。随便找一条路径的权值，扔进线性基中找最大值。

loj#2013 树上倍增/点分治 + 线性基合并。注意点分治不能处理单个点的情况，特判。

CF724G 前半部分跟bzoj2115一样，后面拆位考虑每一位的贡献。组合数学一波。注意2 ^ i * xxx可能会爆long long

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 
  5 typedef long long LL;
  6 const int N = 100010;
  7 const LL MO = 1e9 + 7;
  8 
  9 struct Edge {
 10     int nex, v;
 11     LL len;
 12 }edge[N * 4]; int tp;
 13 
 14 int vis[N], cnt, top, e[N];
 15 LL base[63], d[N], stk[N], pw[63];
 16 
 17 inline void insert(LL x) {
 18     for(int i = 62; i >= 0 && x; i--) {
 19         if(!(x >> i)) {
 20             continue;
 21         }
 22         if(!base[i]) {
 23             base[i] = x;
 24             cnt++;
 25             break;
 26         }
 27         x ^= base[i];
 28     }
 29     return;
 30 }
 31 
 32 inline void add(int x, int y, LL z) {
 33     tp++;
 34     edge[tp].v = y;
 35     edge[tp].len = z;
 36     edge[tp].nex = e[x];
 37     e[x] = tp;
 38     return;
 39 }
 40 
 41 inline void clear() {
 42     memset(base, 0, sizeof(base));
 43     cnt = top = 0;
 44     return;
 45 }
 46 
 47 void DFS(int x) {
 48     stk[++top] = d[x];
 49     for(int i = e[x]; i; i = edge[i].nex) {
 50         int y = edge[i].v;
 51         if(d[y] != -1) {
 52             insert(d[y] ^ d[x] ^ edge[i].len);
 53             continue;
 54         }
 55         d[y] = d[x] ^ edge[i].len;
 56         DFS(y);
 57     }
 58     return;
 59 }
 60 
 61 inline LL cal() {
 62     LL ans = 0;
 63     for(int i = 62; i >= 0; i--) {
 64         // cal i pos
 65         bool f = 0; LL cnt0 = 0, cnt1 = 0;
 66         for(int j = 62; j >= i; j--) {
 67             if((base[j] >> i) & 1) {
 68                 f = 1;
 69                 break;
 70             }
 71         }
 72         for(int j = 1; j <= top; j++) {
 73             ((stk[j] >> i) & 1) ? cnt1++ : cnt0++;
 74         }
 75         if(f) {
 76             LL cnt2 = cnt0 + cnt1;
 77             (ans += cnt2 * (cnt2 - 1) / 2 % MO * pw[cnt - 1] % MO * pw[i] % MO) %= MO;
 78         }
 79         else {
 80             (ans += cnt0 * cnt1 % MO * pw[cnt] % MO * pw[i] % MO) %= MO;
 81         }
 82     }
 83     return ans;
 84 }
 85 
 86 int main() {
 87     int n, m;
 88     pw[0] = 1;
 89     for(int i = 1; i <= 62; i++) {
 90         pw[i] = pw[i - 1] * 2 % MO;
 91     }
 92     scanf("%d%d", &n, &m);
 93     int x, y; LL z;
 94     for(int i = 1; i <= m; i++) {
 95         scanf("%d%d%lld", &x, &y, &z);
 96         add(x, y, z);
 97         add(y, x, z);
 98     }
 99     LL ans = 0;
100     memset(d, -1, sizeof(d));
101     for(int i = 1; i <= n; i++) {
102         if(d[i] == -1) {
103             d[i] = 0;
104             DFS(i);
105             ans = (ans + cal()) % MO;
106             clear();
107         }
108     }
109     printf("%lld
", ans);
110     return 0;
111 }

AC代码

bzoj4644 经典傻逼题

每个点的点权为与它相连的边的权值异或和。求最大权点集即可。

线段树分治 + 线性基 + bitset。