【算法讲解】杂项算法

异或哈希是个很神奇的算法，利用了异或操作的特殊性和哈希降低冲突的原理，可以用于快速找到一个组合是否出现、序列中的数是否出现了k次

异或是计算机语言中的一个运算符，代码中用^表示，数学符号用 ⊕ \oplus ⊕表示，含义是对数字的二进制表示按位相加并对2取余，举个例子 3 ⊕ 5 = ( 011 ) 2 ⊕ ( 101 ) 2 = ( 110 ) 2 = 7 3\oplus5=(011)_2\oplus (101)_2=(110)_2=7 3⊕5=(011)2​⊕(101)2​=(110)2​=7 异或运算符合交换律（类似加法交换律、乘法交换律），既 A ⊕ B = B ⊕ A A\oplus B = B \oplus A A⊕B=B⊕A 异或运算相比其他运算，有一个很重要的独有特性： A ⊕ 0 = A A ⊕ A = 0 A\oplus 0=A\\ A\oplus A=0 A⊕0=AA⊕A=0 根据上述这个特性，我们可以推演得到重要特性：当一个数进行偶数次异或运算后，其值为0，当一个数进行奇数次操作后，其结果为自身

我们可以根据这个特性快速解决这个题目 leetcode: 一个数组中除了一个元素外其他元素都出现了两次(偶数次)，找出这个元素

自此，将算法的复杂度从 O ( n 3 ) O(n^3) O(n3) 优化成了 O ( n 2 ) O(n^2) O(n2)，至于如何优化到 O ( n ) O(n) O(n)，不是本篇介绍的主要内容，大家可以自行思考

上面代码大家会看到一个很神奇的内容 mt19937_64 rnd(time(0))，这是 c++ 自带的梅森旋转（Mersenne Twister）伪随机数，可以随机生成 64 位整数，随机的内容直到 2 19937 2^{19937} 219937 次调用后才会出现重复，具体的原理这里不过多介绍。把他当成一个工具使用就行。

在用异或求解章节我们利用了异或的交换律特性，那是否用也符合交换律的加法运算也能达到相同的效果呢？ 答案是：yes

异或的本质是对 2 进制每位进行不进位的加法 加法的本质是对 2 进制每位进行进位的加法

而c++的语言特性中，无符号整数对于溢出的部分会自动截断，所以效果是相同的 只是在求区间结果的时候需要将xor[r] ^ xor[l - 1]换成xor[r] - xor[l - 1]

那么乘法呢？ 乘法其实也是类似的道理，但是转化为对 2 64 2^{64} 264去模除法，这个很麻烦，不利于模拟。而且虽然没有证明，但我觉得乘法的冲突概率要比异或高。所以不会建议使用乘法

而计算机对位运算的处理效率要比其他运算高很多，并且不用像加法一样额外考虑减法，所以这类题目我们都用异或来进行计算。

判断一个序列内的元素是否出现偶数( k k k的倍数)次

在开篇我们提到一个用异或来解决的经典题目：快速找到一个数组中只出现1次（其他数都出现偶数次）的数 利用的就是 A ⊕ A = 0 A\oplus A=0 A⊕A=0的特性，我们可以快速判断一个数组(区间)的元素是否都出现了偶数次 直接异或结果为0就行了 不对！！ 因为 4 ⊕ 8 ⊕ 12 4\oplus 8 \oplus 12 4⊕8⊕12 也等于0，所以我们需要将数字进行hash处理，降低冲突概率，再用异或操作

现在我们将问题升级一下：

给一个长度为 n n n 的数组 a a a，找到所有的连续子序列 [ l , r ] [l,r] [l,r] 满足：所有 a i , i ∈ [ l , r ] a_i, i\in[l,r] ai​,i∈[l,r] 出现的次数都是 3 次倍数

之前提到，二进制的异或的本质是对每一位进行不进位的加法，也就是每一位相加对2取模，既： 0 ⊕ 0 = ( 0 + 0 ) % 2 = 0 1 ⊕ 0 = ( 1 + 0 ) % 2 = 1 0 ⊕ 1 = ( 0 + 1 ) % 2 = 1 1 ⊕ 1 = ( 1 + 1 ) % 2 = 0 \begin{aligned} 0\oplus0&=(0+0)\%2&=0\\ 1\oplus0&=(1+0)\%2&=1\\ 0\oplus1&=(0+1)\%2&=1\\ 1\oplus1&=(1+1)\%2&=0\\ \end{aligned} 0⊕01⊕00⊕11⊕1​=(0+0)%2=(1+0)%2=(0+1)%2=(1+1)%2​=0=1=1=0​ 假设有这么一个运算符 3 ◯ \textcircled{3} 3◯，可以让 A 3 ◯ A 3 ◯ A = 0 A\textcircled{3}A\textcircled{3}A=0 A3◯A3◯A=0，那么问题就解决了，既： 0 3 ◯ 0 = ( 0 + 0 ) % 3 = 0 0 3 ◯ 1 = ( 0 + 1 ) % 3 = 1 0 3 ◯ 2 = ( 0 + 2 ) % 3 = 2 1 3 ◯ 2 = ( 1 + 2 ) % 3 = 0 \begin{aligned} 0\textcircled{3}0&=(0+0)\%3&=0\\ 0\textcircled{3}1&=(0+1)\%3&=1\\ 0\textcircled{3}2&=(0+2)\%3&=2\\ 1\textcircled{3}2&=(1+2)\%3&=0\\ \end{aligned} 03◯003◯103◯213◯2​=(0+0)%3=(0+1)%3=(0+2)%3=(1+2)%3​=0=1=2=0​ 这就是 3 3 3 进制，也可以推演至 k k k 进制。

但很不幸， k k k 进制虽然能解决问题，但是会额外增加 log ⁡ 3 C \log_3C log3​C的常数 ≈ 40 \approx 40 ≈40。 上文有提到，加法配合减法可以达到异或类似的效果，所以我们对于这类问题可以取个巧，将第 k k k 的倍数次出现的数字设置为 k − 1 k-1 k−1倍的负数 − ( k − 1 ) ⋅ a i -(k-1)\cdot a_i −(k−1)⋅ai​，那么只要一个区间内出现的次数是 k k k 的倍数，那么他们的和一定是0 对于 k = 2 k=2 k=2，设置为 − a i -a_i −ai​，对于 k = 3 k=3 k=3，设置为 − 2 ⋅ a i -2\cdot a_i −2⋅ai​ 所以我们只需要判断区间和为0，那么这个区间的数字出现的次数一定是 k k k的倍数 注意：为了降低冲突的概率，我们需要将元素映射为64位无符号整数

思考 这个做法我们只将复杂度从 O ( n 3 ) O(n^3) O(n3)降低为 O ( n 2 ) O(n^2) O(n2)，如何降低为 O ( n ) O(n) O(n)大家可以自行思考 如果要求区间出现的次数一定是 k k k次，而不是 k k k的倍数，又应该如何解呢？ 对于这两个思考，可以在 CF 1418 G Three Occurrences 这道题中进行验证

判断一个序列的乘积是否是 x 2 x^2 x2( x x x为某个整数)

通常题目不会直观让你判断次数是否偶数次，会进行一些伪装，而 x 2 x^2 x2 就是一个非常常见的伪装 我们将一个 a i a_i ai​进行质因数分解可得 p 1 k i 1 p 2 k i 2 ⋯ p m k i m p_1^{k_{i_1}}p_2^{k_{i_2}}\cdots p_m^{k_{i_m}} p1ki1​​​p2ki2​​​⋯pmkim​​​，其中 p i p_i pi​都是质数， k i k_i ki​是对应的指数。 那么所有 a i a_i ai​的乘积就为 ∏ i = 1 n a i = p 1 ∑ i = 1 n k i 1 p 2 ∑ i = 1 n k i 2 ⋯ p m ∑ i = 1 n k i m \prod_{i=1}^{n} a_i=p_1^{\sum_{i=1}^n k_{i_1}}p_2^{\sum_{i=1}^n k_{i_2}}\cdots p_m^{\sum_{i=1}^n k_{i_m}} ∏i=1n​ai​=p1∑i=1n​ki1​​​p2∑i=1n​ki2​​​⋯pm∑i=1n​kim​​​ (为了简化表达，我们将 ∑ i = 1 n k i m \sum_{i=1}^n k_{i_m} ∑i=1n​kim​​ 记为 K m K_m Km​) 如果： p 1 K 1 p 2 K 2 ⋯ p n K n = x 2 p_1^{K_1}p_2^{K_2}\cdots p_n^{K_n}=x^2 p1K1​​p2K2​​⋯pnKn​​=x2 那么： ( p 1 K 1 2 p 2 K 2 2 ⋯ p n K n 2 ) 2 = x 2 (p_1^{\frac{K_1}{2}}p_2^{\frac{K_2}{2}}\cdots p_n^{\frac{K_n}{2}})^2=x^2 (p12K1​​​p22K2​​​⋯pn2Kn​​​)2=x2 可以推得：所有的 K i K_i Ki​都是偶数， ∏ i = 1 n a i \prod_{i=1}^{n} a_i ∏i=1n​ai​才可能是某个整数的平方 x 2 x^2 x2 所以问题就转化成了质因数的个数是否是偶数次 这就是上述已经解决的问题

1. XOR Hashing [TUTORIAL] 2. 哈希算法学习笔记