标签：le 01Trie sum 个数 笔记 贡献 异或

异或

异或基本性质

1. 交换律：a ^ b=b ^ a
2. 结合律：a ^ (b ^ c) = (a ^ b) ^ c
3. 自反律：a ^ a = 0

---

异或题型总结

01Trie

概述：使用01Trie的题目，大多涉及某个数和某个数异或后满足某些条件。

界外科学

套路题。

观察到 \(1\le n \le 36\) ，想到可以用折半搜索将前半边和后半边的所有满足度以及对应的总价值预处理出来，问题转化为如何找出两个总价值异或后小于等于 \(m\)，并且价格最大。

可以将前面的异或值放到01Trie上，用树形DP预处理出每个节点的子树内最大总价值是多少。

设 \(p_m\) 表示 \(m\) 的当前位，\(p_x\) 表示 \(x\) 的当前位（枚举右半边的所有值）。

1. \(p_m=p_x=1\) ，将01Trie上\(1\)的分支的dp值计入，因为\(1\oplus1 < 1\)，所以右边的必然满足条件。
2. \(p_m=p_n=0\) ，往左边走，不计入贡献。
3. \(p_m=1,p_n=0\) ， 将\(0\)的分支计入贡献，往右走。
4. \(p_m=0,p_x=1\) ，往右走，不计入贡献。

---

最长异或路径

由于是找两个节点进行异或，所以想到用01Trie。

寻找最长异或路径，可以利用异或的自反性，即：\(x\sim y=(1\sim x) \oplus(1\sim y)\)

所以预处理出1到所有节点的异或值，边 \(insert\) 边查询即可。

---

拆位

概述：对于一堆堆的异或，我们通常考虑每一位的贡献。

异或序列

先用前缀和将式子简化为：\(\sum_{1\le i\le j\le N}s_j\oplus s_{i-1}\)

即：\(\sum_{i=1}^{n}\sum_{j=0}^{i-1}s_i \oplus s_j\)

考虑每一位的贡献。

式子的实际含义就是求出一个区间内有多少对数异或值为1，显然：0的个数 \(\times\) 1的个数。

接着乘上这一位的贡献即可。

---

CF242E XOR on Segment

考虑每一位的贡献。

对一个区间求和，本质上是将每一位1的个数进行贡献。

所以我们记录 \(f(l,r,k)\) 表示区间 \([l,r]\) 第 \(k\) 位 \(1\) 的个数。

考虑如何实现异或操作。

如果当前位是1，那么一个区间内1变成0，0变成1，即：\(f(l,r,k)=(r-l+1)-f(l,r,k)\)

---

[TJOI2017] 异或和

题目要求所有和的异或值，先做一个前缀和（记作 \(s(i)\)）。

考虑每一位的贡献。

我们需要找出 \(s(i)-sm(j-1)\) 该位上 \(1\) 的个数是奇数还是偶数，那么如何在该位上减出1呢？分情况讨论：

1. \(s(i)=s(j)=0\) ，后面位：\(s(i)<s(j)\)
2. \(s(i)=1,s(j)=0\) ，后面位：\(s(j)\le s(i)\)
3. \(s(i)=0,s(j)=1\) ，后面位：\(s(i) \le s(j)\)

由于 \(\sum_{i=1}^{n} a_i \le 10^6\) ，所以可以用权值树状数组。

标签：le,01Trie,sum,个数,笔记,贡献,异或
From： https://www.cnblogs.com/zhangyuzhe/p/16718438.html