基础思想
异或哈希用到了异或的性质：相同数字异或为 0。
引入随机数的目的是做哈希运算的时候减小哈希碰撞，在使用 mt19937_64 的前提下，随机数强度足以避免哈希碰撞。并且，异或的上述性质可以保证当两侧的哈希相同的时候，运算结果恒定为 0。
异或哈希主要在面对 set 判断等价的时候使用。
还有前缀和哈希，主要是在面对 multiset（也可以说是 vector ） 判断相等的时候使用。
以 CF2014H 为例
思路
经过读题可以发现，警长作为后手压根没有必胜策略，只要罗宾每次打最大的气球，最后的得分一定会大于等于警长的得分。
那么考虑平局的情况，不难发现警长只有和罗宾先后手打同一得分的气球才能打成平手，也就是对于每种在区间 $[l,r]$ 的得分为 $x$ 的气球，必须存在偶数个。
这个问题乍一看很简单，异或前缀和以后求 $[l,r]$ 区间异或是否为 $0$ 就行了，但是实际操作的时候，不难发现由于给出数字比较小，很容易出现碰撞产生错误结果的情况，于是需要对每一个数字进行随机化映射。例如随机化数组为 $ [1930204585,12390125,485989234,1239049102349012]$，则源输入数据的 $[0,1,2,3]$ 分别对应了随机数组中的三个数，他们的 $xor$ 结果就不会为 $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
| using i64 = long long;
using u64 = unsigned long long;
mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
constexpr int MAXN = 1e6 + 10;
vector<int> rvec(MAXN);
void init()
{
for (auto &v : rvec)
v = rng();
}
void solve()
{
int n, q;
cin >> n >> q;
vector<i64> vec(n + 1);
vector<u64> pref(n + 1);
for (int i = 1; i <= n; i++)
cin >> vec[i], pref[i] = pref[i - 1] ^ rvec[vec[i]];
while (q--)
{
int l, r;
cin >> l >> r;
cout << (pref[l - 1] ^ pref[r] ? "NO" : "YES") << endl;
}
}
|
另一个例子：ABC367F
本题来自 @Sun_M ，非常感谢！
思路
这个题目的要求是分别选取数组 $a,b$ 的一段区间，问能否让这两个区间重排后等价。
重排后等价，则两者的数组和应该长度相等并且和相等，考虑用前缀和（注意，此处的数组可能存在多个重复元素，用 xor hash 不可行）。
用随机数将数字打乱避免碰撞即可。
代码
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
| mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
using i64 = long long;
constexpr int MAXN = 2e5 + 10;
vector<i64> rnd(MAXN);
void init()
{
for (auto &v : rnd)
v = rng();
}
void solve()
{
int n, q, l1, r1, l2, r2;
cin >> n >> q;
vector<int> a(n), b(n);
vector<i64> pa(n + 10), pb(n + 10);
for (auto &v : a)
cin >> v;
for (auto &v : b)
cin >> v;
for (int i = 1; i <= n; i++)
pa[i] = pa[i - 1] + rnd[a[i - 1]], pb[i] = pb[i - 1] + rnd[b[i - 1]];
while (q--)
{
cin >> l1 >> r1 >> l2 >> r2;
cout << (((pa[r1] - pa[l1 - 1]) == (pb[r2] - pb[l2 - 1]) && r1 - l1 == r2 - l2) ? "Yes" : "No") << endl;
}
}
|
其他题目
感谢 @Floating-Ocean 提供的练手题目！非常感谢！
CF1996G
tbd.
CF1977D
思路
题目要求反转行后特殊列的最大数量。
如果 $(i,j)$ 是第 $j$ 列唯一一个 $1$ ，则除了第 $i$ 行以外，其他所有行第 $j$ 列为 $1$ 的要变换为 $0$，原本就是 $0$ 的不能变换。
也就是，确定 $grid[i][j]=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
| vector<vector<i64>> randval(2, vector<i64>(3e5 + 5));
void init()
{
for (auto &vec : randval)
for (auto &v : vec)
v = rng();
}
void solve()
{
int n, m;
string s;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
for (int i = 0; i < n; i++)
{
cin >> s;
for (int j = 0; j < m; j++)
grid[i][j] = s[j] - '0';
}
map<pair<long long, i64>, int> ans;
int res = 0;
pair<int, int> ind_ans = {0, 0};
for (int j = 0; j < m; ++j)
{
i64 sum1 = 0, sum2 = 0;
for (int i = 0; i < n; ++i)
sum1 ^= grid[i][j] * randval[0][i], sum2 ^= grid[i][j] * randval[1][i];
for (int i = 0; i < n; ++i)
{
sum1 ^= randval[0][i], sum2 ^= randval[1][i];
ans[{sum1, sum2}]++;
if (res < ans[{sum1, sum2}])
res = ans[{sum1, sum2}], ind_ans = {j, i};
sum1 ^= randval[0][i], sum2 ^= randval[1][i];
}
}
cout << res << "\n";
string inds(n, '0');
for (int i = 0; i < n; ++i)
if (grid[i][ind_ans.first])
{
if (i != ind_ans.second)
inds[i] = '1';
}
else if (ind_ans.second == i)
inds[i] = '1';
cout << inds << "\n";
}
|