0%

异或哈希

又是只有我不会的科技。

随机函数的选择

std::mt19937std::mt19937_64 。又快又好,C++标准都说好,选它!

使用例:

1
2
3
4
5
#include <random>
using ull = unsigned long long;
std::mt19937_64 mrand(1145142007);

ull a = mrand();

何时用

关注区间内是否出现了某些数字。

例题:

  • 给定数列 \(A, B\)
  • 每次询问 \(A\) 的前 \(x\) 项出现的数字是否与 \(B\) 的前 \(y\) 项出现的数字相同。1

我们可以为出现的每一个数字分配一个随机值,然后做一个前缀异或和。对于去重,考虑异或的恒等律2,可以为数列中再次出现的位置分配 \(0\)。我们可以使用 std::map 来做值的映射。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <random>

using ull = unsigned long long;

constexpr int MAX_N = 200050;

std::mt19937_64 mrand(1145142007);

int a[MAX_N], b[MAX_N];
ull sa[MAX_N], sb[MAX_N];
std::map<int, bool> va, vb;
std::map<int, ull> mp;

int main() {
std::ios::sync_with_stdio(false);

int n;
read(n);
for (int i = 1; i <= n; i++) {
read(a[i]);
}
for (int i = 1; i <= n; i++) {
read(b[i]);
}
for (int i = 1; i <= n; i++) {
if (va[a[i]]) {
a[i] = 0;
} else {
va[a[i]] = true;
}
}
for (int i = 1; i <= n; i++) {
if (vb[b[i]]) {
b[i] = 0;
} else {
vb[b[i]] = true;
}
}

for (int i = 1; i <= n; i++) {
if (a[i] and (mp.find(a[i]) == mp.end())) {
mp[a[i]] = mrand();
}
}
for (int i = 1; i <= n; i++) {
if (b[i] and (mp.find(b[i]) == mp.end())) {
mp[b[i]] = mrand();
}
}
for (int i = 1; i <= n; i++) {
sa[i] = sa[i - 1];
if (a[i]) {
sa[i] ^= mp[a[i]];
}
}
for (int i = 1; i <= n; i++) {
sb[i] = sb[i - 1];
if (b[i]) {
sb[i] ^= mp[b[i]];
}
}

int q;
read(q);
while (q--) {
int x, y;
read(x, y);
std::cout << (sa[x] == sb[y] ? "Yes" : "No") << '\n';
}

return 0;
}

碰撞?

对于随机的 \(p, q \in [0,1]\)\(p \oplus q\) 有一半的情况为 \(0\),一半的情况为 \(1\)

即对于 \(1 \mathrm{bit}\) 的随机数,碰撞的概率为 \(2^{-1}\)

又因为异或是按位操作,因此一个 \(64 \mathrm{bit}\) 的随机数碰撞的概率即为 \(2^{-64}\)。可以认为在 OI 出现的数据范围内忽略不计。

例1

  • 给定数组 \(a_1, a_2, \dots, a_n \ (1 \le a_i \le n)\)
  • \(a_l, a_{l+1}, \dots, a_r\)\(1, 2, \dots, r-l+1\) 恰好各出现一次,称其为一个子排列;
  • \(a\) 中有几个子排列。3

首先将 \([1,n]\) 的哈希及其异或前缀和预处理出来。

\(a\) 中枚举 \(1\) 的位置,向左右枚举长度。为了方便处理我们可以改成向右枚举长度后反转序列再枚举一次。

求出 \(a, a'\) 的哈希异或前缀和,即可快速判断是否出现了 \([1,r-l+1]\)。最后记得算上一次 \(1\) 的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <random>

using ull = unsigned long long;

constexpr int MAX_N = 300050;

std::mt19937_64 mrand(1145142007);

int a[MAX_N];
ull r[MAX_N], s[MAX_N], p[MAX_N];

int main() {
std::ios::sync_with_stdio(false);

int n;
read(n);
for (int i = 1; i <= n; i++) {
r[i] = mrand();
s[i] = s[i - 1] ^ r[i];
}
for (int i = 1; i <= n; i++) {
read(a[i]);
}
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] ^ r[a[i]];
}

int ans{};
for (int i = 1, j = 1; i <= n; i++) {
if (a[i] == 1) {
j = 1;
ans++;
} else {
j = std::max(j, a[i]);
if (i < j) {
continue;
}
if ((p[i] ^ p[i - j]) == s[j]) {
ans++;
}
}
}

std::reverse(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] ^ r[a[i]];
}
for (int i = 1, j = 1; i <= n; i++) {
if (a[i] == 1) {
j = 1;
} else {
j = std::max(j, a[i]);
if (i < j) {
continue;
}
if ((p[i] ^ p[i - j]) == s[j]) {
ans++;
}
}
}
std::cout << ans << '\n';

return 0;
}

例2

题面太长了,自己看

不妨令所有颜色相同的位置哈希异或和为 \(0\),在做前缀异或和时,若发现当前前缀异或和出现过即说明满足条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <iostream>
#include <map>
#include <memory>
#include <random>
#include <vector>

using ull = unsigned long long;

constexpr int MAX_N = 300050;

std::mt19937_64 mrand(1145141999);

std::map<ull, int> mp;
std::vector<int> c[MAX_N];
ull v[MAX_N];

void solve() {
int n;
read(n);
for (int i = 1; i <= n; i++) {
int x;
read(x);
c[x].push_back(i);
}
for (int i = 1; i <= n; i++) {
if (c[i].empty()) {
continue;
}
ull s{};
for (int j = 1; j < c[i].size(); j++) {
s ^= (v[c[i][j]] = mrand());
}
v[c[i][0]] = s;
}

mp[0] = 1;
ull s{}, a{};
for (int i = 1; i <= n; i++) {
s ^= v[i];
a += mp[s];
mp[s]++;
}
std::cout << a << '\n';

  1. [ABC250E] Prefix Equality↩︎

  2. \(x \oplus 0 = x\)↩︎

  3. [CF1175F] The Number of Subpermutations↩︎