CONTENT: 线性基、字典树、线段树
UPDATE: 2019.02.06 | 更新格式、Introduction及新增CF 1101G
UPDATE (2019.02.26)
- 更新格式
- 新增Introduction
- 新增CF 1101G
BB
最近训练的时候第一次听说了“线性基”，线段树处理二进制问题也是第一次见，蒟蒻实在是太嫩了 _(:з」∠)_
至于字典树那自然是很常见的了
本文中一些题意直接搬以下链接中博主的
另外还要说一点就是，HYSBZ就是BZOJ，如果各位搜不到的话换成BZOJ试试
Introduction
线性基属线性代数方面的东西，蒟蒻理解为能异或组合出数组中所有元素的一组基，貌似在异或题中比较常见 qwq
Sum of xor sum - 计蒜客
Description
有多次询问，每次询问[l,r]区间中所有子区间异或和的和
Solution —— 线段树
没想到可以这么玩
按位拆数，最后再按位统计
对于每一位建一棵线段树维护区间中异或和为0的子区间个数(用sum[0]代表)，以及异或和为1的子区间个数(用sum[1]代表)，为了使得结果能够在线段树的pushUp操作中合并，额外引入l[0],l[1]分别代表包含区间左端点的区间中异或和为0和1的个数，r[0],r[1]分别代表包含区间右端点的区间中异或和为0和1的个数，val代表整段区间的异或值
那么，以下显然是成立的
if(lc.val == 0) { //如果左区间的异或和为0
//包含左端点的区间0的个数等于包含左端点的左区间0的个数 + 右区间中包含右区间左端点的区间0的个数
ret.l[0] = lc.l[0] + rc.l[0];
//同理
ret.l[1] = lc.l[1] + rc.l[1];
} else { //如果左区间的异或和为1
//包含左端点的区间0的个数等于左区间0的个数 + 右区间中包含右区间左端点的区间1的个数
//加上右区间1的个数是因为左区间异或和为1，那么右边的部分自然要为1才能异或和为0
ret.l[0] = lc.l[0] + rc.l[1];
//同理
ret.l[1] = lc.l[1] + rc.l[0];
}
//同理
if(rc.val == 0) {
ret.r[0] = rc.r[0] + lc.r[0];
ret.r[1] = rc.r[1] + lc.r[1];
} else {
ret.r[0] = rc.r[0] + lc.r[1];
ret.r[1] = rc.r[1] + lc.r[0];
}
//整段区间的异或值自然等于左右区间异或值异或
ret.val = lc.val ^ rc.val;
//整段区间中所有异或和为0的区间的个数为
//左右区间的结果 + 跨过左区间右端点和右区间左端点的部分
//这个部分自然用左区间右端点的r和右区间左端点的l来维护
ret.sum[0] = (lc.sum[0] + rc.sum[0] + (lc.r[0] * rc.l[0]) + (lc.r[1] * rc.l[1]));
ret.sum[1] = (lc.sum[1] + rc.sum[1] + (lc.r[0] * rc.l[1]) + (rc.r[1] * rc.l[0]));
那么能合并自然就能建树了，查询的时候直接多次向左合并到ans中
最后按位统计答案就可以了
（因为以为合并方向取决于从哪边走过来而WA了无数次，智商为0 = =||）
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const int N = 1e5 + 2;
const ll MOD = 1000000007;
const int inf = 0x3f3f3f3f;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
struct Interval {
int l[21][2], r[21][2];
int sum[21][2];
int val[21];
};
Interval seg[N << 2], ans;
int a[21][N];
int read() {
char ch = getchar();
int x = 0;
int f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
Interval merge(Interval a, Interval b) {
Interval ret;
memset(&ret, 0, sizeof(ret));
for(int i = 0; i <= 20; i++) {
if(a.val[i] == 0) {
ret.l[i][0] = a.l[i][0] + b.l[i][0];
ret.l[i][1] = a.l[i][1] + b.l[i][1];
} else {
ret.l[i][0] = a.l[i][0] + b.l[i][1];
ret.l[i][1] = a.l[i][1] + b.l[i][0];
}
if(b.val[i] == 0) {
ret.r[i][0] = b.r[i][0] + a.r[i][0];
ret.r[i][1] = b.r[i][1] + a.r[i][1];
} else {
ret.r[i][0] = b.r[i][0] + a.r[i][1];
ret.r[i][1] = b.r[i][1] + a.r[i][0];
}
ret.val[i] = a.val[i] ^ b.val[i];
ret.sum[i][0] = ((ll)a.sum[i][0] + (ll)b.sum[i][0] + ((ll)a.r[i][0] * b.l[i][0])%MOD + ((ll)a.r[i][1] * b.l[i][1])%MOD)%MOD;
ret.sum[i][1] = ((ll)a.sum[i][1] + (ll)b.sum[i][1] + ((ll)a.r[i][0] * b.l[i][1])%MOD + ((ll)a.r[i][1] * b.l[i][0])%MOD)%MOD;
}
return ret;
}
void pushUp(int rt) {
seg[rt] = merge(seg[rt << 1], seg[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
if(l == r) {
for(int i = 0; i <= 20; i++) {
seg[rt].sum[i][0] = seg[rt].l[i][0] = seg[rt].r[i][0] = (a[i][l] == 0);
seg[rt].sum[i][1] = seg[rt].l[i][1] = seg[rt].r[i][1] = a[i][l];
seg[rt].val[i] = a[i][l];
}
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushUp(rt);
}
void query(int ql, int qr, int l, int r, int rt) {
if(ql <= l && r <= qr) {
ans = merge(ans, seg[rt]);
return;
}
int m = (l + r) >> 1;
if(ql <= m) query(ql, qr, lson);
if(m < qr) query(ql, qr, rson);
}
int main() {
int t = read();
while(t--) {
//memset(seg, 0, sizeof(seg));
int n = read(), q = read();
for(int i = 1; i <= n; i++) {
int tmp = read();
for(int j = 0; j <= 20; j++) {
a[j][i] = ((tmp >> j) & 1);
}
}
build(1, n, 1);
while(q--) {
int l = read(), r = read();
memset(&ans, 0, sizeof(ans));
query(l, r, 1, n, 1);
ll res = 0;
for(int i = 0; i <= 20; i++) {
res = (res + ((ll)ans.sum[i][1] * (1LL << i))%MOD)%MOD;
}
printf("%lld\n", res);
}
}
}
XOR HDU - 3949
Description
给定n个数和Q个询问，每次询问这些数（至少一个，不能不选）能够组成的异或和中第k小的数是什么（不计重）
Solution —— 线性基
算是线性基模板题了
不过要特别注意原给定数就是线性相关的，那样会异或出0，需要特别留意
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int HIGHEST = 63;
const int N = 1e4 + 15;
typedef long long ll;
ll a[N], b[HIGHEST + 5], c[HIGHEST + 5], pp;
void build(int n) {
for(int i = 0; i < n; i++) {
for(int j = HIGHEST; j >= 0; j--) {
if((a[i] >> j & 1) == 0) continue;
if(b[j]) a[i] ^= b[j];
else {
b[j] = a[i];
for(int k = j - 1; k >= 0; k--) if(b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
for(int k = j + 1; k <= HIGHEST; k++) if(b[k] >> j & 1) b[k] ^= b[j];
break;
}
}
}
}
int main() {
int t, csn = 1;
scanf("%d", &t);
while(t--) {
memset(b, 0, sizeof(b));
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
build(n);
pp = 0;
for(int j = 0; j <= HIGHEST; j++) {
if(b[j]) c[pp++] = b[j];
}
printf("Case #%d:\n", csn++);
int q;
scanf("%d", &q);
while(q--) {
ll k;
scanf("%lld", &k);
if(pp < n) k--;
if(k == 0) {
puts("0");
} else {
ll xorsum = 0;
for(int i = 0; i <= HIGHEST && k; i++, k >>= 1) {
if(i >= pp) {
xorsum = -1;
break;
}
if(k&1) xorsum ^= c[i];
}
printf("%lld\n", xorsum);
}
}
}
}
albus就是要第一个出场 - HYSBZ - 2844
Description
给定n个数和一个数 Q。将n个数组成的集合的所有子集（可以为空）的异或值从小到大排序得到序列B，请问Q在B中第一次出现的下标是多少？保证Q在B中出现
Solution —— 线性基
根据博客上博主的介绍，一个基本结论是每个数重复出现 n - |B| 次，因此推出Q是不重复序列中第几个后再算就行
怎么推呢？个人采用的方法是先推出线性基数组c[]，然后再用Q与c[]中的元素异或，如果变小了那么记录位于第几位做的贡献，然后用异或结果代替Q，继续做直到Q为0为止
这种做法的正确性在于如果某一个c[i]并不是线性表出Q的一部分，那么Q异或c[i]会变大，因为c[i]的最高位为1的那一位，Q必定是为0的
最后再加个快速幂算即可
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int HIGHEST = 31;
const int N = 1e5 + 15;
const int MOD = 10086;
typedef long long ll;
int a[N], b[HIGHEST + 5], c[HIGHEST + 5];
void build(int n) {
for(int i = 0; i < n; i++) {
for(int j = HIGHEST; j >= 0; j--) {
if((a[i] >> j & 1) == 0) continue;
if(b[j]) a[i] ^= b[j];
else {
b[j] = a[i];
for(int k = j - 1; k >= 0; k--) if(b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
for(int k = j + 1; k <= HIGHEST; k++) if(b[k] >> j & 1) b[k] ^= b[j];
break;
}
}
}
}
int quickPow(int a, int b) {
int ans = 1, base = a;
while(b) {
if(b&1) ans = (ans * base)%MOD;
base = (base * base)%MOD;
b >>= 1;
}
return ans;
}
int main() {
int n;
while(~scanf("%d", &n)) {
memset(b, 0, sizeof(b));
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
build(n);
int cnt = 0;
for(int j = 0; j <= HIGHEST; j++) {
if(b[j]) c[cnt++] = b[j];
}
int num, k = 0;
scanf("%d", &num);
for(int i = 0; i < cnt; i++) {
if((num ^ c[i]) < num) {
k += (1 << i);
num ^= c[i];
}
}
printf("%d\n", (k%MOD * quickPow(2, n - cnt) + 1)%MOD);
}
}
XOR - 计蒜客
Description
给定n个数和k，多次询问，每次问区间[l,r]中选一些元素异或完后与k相或的最大结果
Solution —— 线性基 + 线段树
用线段树维护区间的线性基，合并直接合并就好了
但是本题的一个大坑是，并不是把[l,r]的线性基拿出来异或完之后再与k相或就是最大值了，比如 k = (10110)， a1 = (01001), a2 = (10111)，那么异或最大值应该是 (11110)，与k相或是 k | (11110) = (11110)，但实际上 a1 | k = (11111)结果更大
所以建树前可以将ai上是1而k对应位也是1的位置0，拿到的异或最大值再与k相或的结果就是正确的了，而先处理ai并不会影响本题的结果，因此这种做法是可取的
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int HIGHEST = 31;
const int N = 1e4 + 100;
typedef long long ll;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
struct Vec{
int vec[HIGHEST + 5];
};
Vec sum[N << 2], ans;
int a[N];
void init(){
memset(sum, 0, sizeof(sum));
}
inline int read(){
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
void insert(Vec& ret, int val){
for(int j = HIGHEST; j >= 0; j--){
if((val >> j & 1) == 0) continue;
if(ret.vec[j]) val ^= ret.vec[j];
else{
ret.vec[j] = val;
for(int k = j - 1; k >= 0; k--) if(ret.vec[k] && (ret.vec[j] >> k & 1)) ret.vec[j] ^= ret.vec[k];
for(int k = j + 1; k <= HIGHEST; k++) if(ret.vec[k] >> j & 1) ret.vec[k] ^= ret.vec[j];
break;
}
}
}
Vec merge(Vec a, Vec b){
for(int i = 0; i <= HIGHEST; i++){
if(a.vec[i] == 0) continue;
insert(b, a.vec[i]);
}
return b;
}
void pushUp(int rt){ sum[rt] = merge(sum[rt << 1], sum[rt << 1 | 1]); }
void build(int l, int r, int rt){
if(l == r){
insert(sum[rt], a[l]);
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushUp(rt);
}
void query(int ql, int qr, int l, int r, int rt){
if(ql <= l && r <= qr){
ans = merge(sum[rt], ans);
return;
}
int m = (l + r) >> 1;
if(ql <= m) query(ql, qr, lson);
if(m < qr) query(ql, qr, rson);
}
int main(){
int t;
t = read();
while(t--){
init();
int n, q, k;
n = read();
q = read();
k = read();
for(int i = 1; i <= n; i++){
a[i] = read();
a[i] = (a[i] & (~k));
}
build(1, n, 1);
while(q--){
int l, r;
l = read();
r = read();
memset(ans.vec, 0, sizeof(ans.vec));
query(l, r, 1, n, 1);
int xorsum = 0;
for(int i = 0; i <= HIGHEST; i++){
xorsum ^= ans.vec[i];
}
printf("%d\n", k | xorsum);
}
}
}
带劲的and和 HDU - 6411
Solution —— 并查集 + 按位统计思维
先用并查集将同属于一个联通块的价值丢在一起（用Vector），然后再排序，解决max的问题
最关键的就是解决与的问题，实际上可以将数字动态加入all数组中（准确的将是用all数组记录当前及之前数字对应位置上为1的个数），然后按位统计贡献即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100000 + 15;
const int inf = 0x3f3f3f3f;
const int HIGHEST = 1 << 31;
const int MOD = 1e9 + 7;
typedef long long ll;
vector<int> vec[N];
int ft[N];
int a[N];
int cur[32], all[32];
void getBin(int x) {
for(int i = 0; i < 32; i++) {
cur[i] = ((x&HIGHEST) != 0);
x <<= 1;
}
}
inline void init(int n) {
for(int i = 1; i <= n; i++) {
ft[i] = i;
vec[i].clear();
}
}
int find(int x) {
return ft[x] == x ? x : ft[x] = find(ft[x]);
}
void merge(int x, int y) {
int p = find(x), q = find(y);
if(p != q) ft[q] = p;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n, m;
scanf("%d%d", &n, &m);
init(n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
while(m--) {
int a, b;
scanf("%d%d", &a, &b);
merge(a, b);
}
for(int i = 1; i <= n; i++) {
vec[find(i)].push_back(a[i]);
}
ll ans = 0;
for(int i = 1; i <= n; i++) {
if(vec[i].size() >= 2) {
memset(all, 0, sizeof(all));
sort(vec[i].begin(), vec[i].end());
for(int j = 0; j < vec[i].size(); j++) {
getBin(vec[i][j]);
for(int k = 0; k < 32; k++) {
if(cur[k]) ans += (((ll)vec[i][j] * all[k])%MOD * (1LL << (31 - k))%MOD)%MOD;
all[k] += cur[k];
if(ans >= MOD) ans %= MOD;
}
}
}
}
printf("%lld\n", ans);
}
return 0;
}
Chip Factory HDU - 5536
Description
从给定数字中选择三个不同的数字使得 (a+b)^c 最大
Solution —— 字典树（或 暴力）
暴力就不说了，训练时辛辛苦苦写了字典树没过，还被别人暴力过了 = =||
直接预处理c，将其丢入字典树中
然后只需要枚举a+b即可，枚举时先把字典树中的a和b删了，再跑a+b，跑完更新答案再还原
注意不能倒过来先预处理a+b，因为会爆空间（训练时就是因为先预处理a+b死活都过不去 QAQ ）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
const int N = 1e3 + 15;
const int M = 1e6 + 15;
const int HIGHEST = 1 << 31;
using namespace std;
int a[N];
int cur[32];
int cnt[M];
int nxt[M][2];
int tot;
inline void init() {
nxt[0][0] = nxt[0][1] = -1;
tot = 1;
}
void update(int val) {
int p = 0;
for(int i = 0; i < 32; i++) {
int idx = cur[i];
if(nxt[p][idx] == -1) {
nxt[p][idx] = tot++;
cnt[nxt[p][idx]] = 0;
nxt[nxt[p][idx]][0] = nxt[nxt[p][idx]][1] = -1;
}
cnt[nxt[p][idx]] += val;
p = nxt[p][idx];
}
}
int query() {
int ret = 0;
int p = 0;
for(int i = 0; i < 32; i++) {
int idx = cur[i];
if(nxt[p][idx^1] != -1 && cnt[nxt[p][idx^1]] > 0) {
ret += (1 << (31 - i));
p = nxt[p][idx^1];
} else if(nxt[p][idx] != -1 && cnt[nxt[p][idx]] > 0) {
p = nxt[p][idx];
} else {
break;
}
}
return ret;
}
void getBin(int x) {
for(int i = 0; i < 32; i++) {
if(x&HIGHEST) cur[i] = 1;
else cur[i] = 0;
x <<= 1;
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
init();
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < n; i++) {
getBin(a[i]);
update(1);
}
int ans = 0;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
getBin(a[i]);
update(-1);
getBin(a[j]);
update(-1);
getBin(a[i] + a[j]);
ans = max(ans, query());
getBin(a[i]);
update(1);
getBin(a[j]);
update(1);
}
}
printf("%d\n", ans);
}
return 0;
}
(Zero XOR Subset)-less - CodeForces 1101G
Link
https://cn.vjudge.net/problem/CodeForces-1101G
Description
给定一个数组a[1], a[2], …, a[n]，将元素划分为几个段，要求每个段非空，且每个段的所有元素的异或和的任意线性组合均非0
Sample Input
4
5 5 7 2
3
1 2 3
3
3 1 10
Sample Output
2
-1
3
Solution —— 线性基
设选定的段为 [0, x_1], (x_1, x_2], (x_2, x_3], ..., (x_{k-1}, x_k]，设异或前缀和为pr[]，那么这些段的异或和为pr[1], pr[1] XOR pr[2], pr[2] XOR pr[3], ..., pr[k-1] XOR pr[k]，那么可以发现任意线性组合实际上可以表示为pr[]的线性组合，那么用线性基搞搞求大小就行
最后就剩下-1的情况，首先pr[n] = 0的时候肯定是-1，然后选不到最后一个数的时候也是-1，但是发现好像第二个情况比较麻烦而且好像被第一个情况包含了？只考虑第一种情况就ac了emmmm （还是蒟蒻太菜了 T^T
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int HIGHEST = 31;
const int N = 2e5 + 15;
typedef long long ll;
int a[N], b[HIGHEST + 5], c[HIGHEST + 5];
void build(int n) {
for(int i = 1; i <= n; i++) {
for(int j = HIGHEST; j >= 0; j--) {
if((a[i] >> j & 1) == 0) continue;
if(b[j]) a[i] ^= b[j];
else {
b[j] = a[i];
for(int k = j - 1; k >= 0; k--) if(b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
for(int k = j + 1; k <= HIGHEST; k++) if(b[k] >> j & 1) b[k] ^= b[j];
break;
}
}
}
}
int main() {
int n;
while(~scanf("%d", &n)) {
memset(b, 0, sizeof(b));
a[0] = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i] ^= a[i - 1];
}
if(a[n] == 0) {
puts("-1");
continue;
}
build(n);
int cnt = 0;
for(int j = 0; j <= HIGHEST; j++) {
cnt += (b[j] != 0);
}
printf("%d\n", cnt);
}
}
