算法笔记：异或哈希（xor-hashing）

异或哈希可以用来快速查询序列中的数是否出现了 $k$ 次。

异或哈希入门：区间集合判同#

问题：如何判断一个序列是否是另一个序列排列组合，也就是排序后是否相同，或者说元素的集合是否相同（不关心顺序）。

由异或的性质（交换律），可以知道，一个序列如果排序后和另一个序列相等，这两个序列的异或结果相同，相当于一个哈希了。但实际上还有一个问题：排序后相同的序列，异或结果一定相同；但是异或结果一定相同的序列，不一定排序后相同。

这个冲突的概率如何呢？假设序列长度为 $n$ ，每种元素都由 $1$ 到 $n$ 的一个数编码，异或的结果也是 $n$ 。序列长度为 $n$ ，排序后不同的类型序列数的规模最大项是 $n^2$ 的，映射到的哈希空间的最大项是 $n$ 的，肯定冲突。

如果想要用类似的方式的方式来快速判断，需要想办法扩大哈希空间。因此选用 $1$ 到 $2^{64}$ 的数编码，这样哈希空间的最大项就到了 $2^{64}$ ，可以很大程度上减少碰撞概率。例如， $n=1e6$ 的时候，碰撞概率是

p\approx\frac{(10^6)^2}{2^{64}}\approx 5.42\times 10^{-8}

碰撞的概率还是很小的，因此这种哈希方式是可行的。出于保险还可以选择双哈希。

代码（这题没有找到能交的oj测试过，本地测了一下应该对）：

1
typedef unsigned long long ull;
2

3
mt19937_64 rnd(time(0));
4
unordered_map<int, ull> XORHash_map[2];
5

6
struct XORHashing {
7
    int len;
8
    vector<int> s;
9
    vector<ull> hash[2]; // 哈希值
10

11
    void init(const vector<int>& str){
12
        s=str;
13
        len=s.size();
14
        ull xort;
15
        for (int p=0;p<2;p++) {
16
            hash[p].resize(len+1);
17
            hash[p][0]=0;
18
            for (int i=1;i<=len;i++) {
19
                if (XORHash_map[p].find(s[i-1])==XORHash_map[p].end())
20
                    XORHash_map[p].insert(make_pair(s[i-1],rnd()));
21
                xort=XORHash_map[p][s[i-1]];
22
                hash[p][i]=hash[p][i-1]^xort;
23
            }
24
        }
25
    }
26
    // 获取子字符串[s, e]的异或哈希值，序号从0开始
27
    pair<ull, ull> get_hash(int s, int t) {
28
        ull hash1=(hash[0][t+1]^hash[0][s]);
29
        ull hash2=(hash[1][t+1]^hash[1][s]);
30
        return {hash1, hash2};
31
    }
32
};

其中，mt19937_64是基于 Mersenne Twister 算法的伪随机数生成器，专门生成 64 位宽的随机数，具有较长周期（ $2^{19937}-1$ ）。

区间元素出现次数#

给定一个序列，判断指定区间每个元素出现次数是否都是偶数次（2的倍数），可以用异或前缀和实现，判断异或前缀和是否是0即可。那如果要判断每个元素出现次数是否都是3或3的倍数呢？或者出现次数都是 $k$ 或 $k$ 的倍数呢？

考虑实现 $k$ 进制异或，异或其实就是不带进位的加法，因此模拟一遍即可，只不过比起二进制要多一个 $\log$ 的常数。

更多问题中，要求的不是 $k$ 或 $k$ 的倍数，而是要求判断区间元素是否精准是 $k$ 次。精准是 $k$ 次，我们只需要解决一个问题：维护区间元素出现次数不多于 $k$ 的区间即可。可以从左到右以1的步长移动右端点，同时记录以当前右端点，区间元素出现次数不多于 $k$ 的区间左端点极限，同时用个map维护一下相同异或前缀和即可。

简而言之，也就是双指针加异或前缀和，利用 $k$ 进制异或的性质来维护双指针区间内有多少个满足条件的端点。

codeforces - 1418 - G（出现3次）#

给定一个由 $n$ 个正整数构造的数组 $a$ . 我们说子数组 $a[l..r]$ 也就是 $[a_l, a_{l + 1}, \dots, a_r]$ ( $1 \le l \le r \le n$ ) 是好的，当且仅当子数组中的每个元素都恰好出现3次。例如 $[1, 2, 2, 2, 1, 1, 2, 2, 2]$ 有3个好的子数组：

$a[1..6] = [1, 2, 2, 2, 1, 1]$ ;

$a[2..4] = [2, 2, 2]$ ;

$a[7..9] = [2, 2, 2]$ .

计算给定的数组 $a$ 的好的子数组的数目。

数据规模： $1\leq n\leq 5e5$

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
//#undef LOCAL_DEBUG
5
#ifdef LOCAL_DEBUG
6
#include "debug.h"
7
#else
8
#define debug(...) (void)0
9
#define debug_array(arr, len) (void)0
10
#endif
11

12
typedef unsigned long long ull;
13
typedef long long ll;
14
typedef pair<int,int> P;
15
const int maxn=5e5;
16

17
int n;
18
int a[maxn+5];
19

20
#define KNUM (3)    // K=3进制
21
#define KLEN (64)   // 用K进制64位数表示
22
typedef array<int, KLEN> Num;
23
Num operator ^(const Num &a, const Num &b){
24
    Num c;
25
    for (int i=0;i<KLEN;i++){
26
        c[i]=a[i]+b[i];
27
        if (c[i]>=KNUM)
28
            c[i]-=KNUM;
29
    }
30
    return c;
31
}
32
mt19937 rnd(time(0));
33
Num gen(void){  // 生成一个随机的K进制数
34
    Num ret;
35
    for (int i=0;i<KLEN;i++)
36
        ret[i]=rnd()%KNUM;
37
    return ret;
38
}
39

40
struct XORHashing {
41
    vector<Num> hash;
42
    // 初始化哈希[0,n]
43
    XORHashing(int n){
44
        hash.resize(n+1);
45
        for (int i=0;i<=n;i++)
46
            hash[i]=gen();
47
    }
48
    Num get_hash(int x){
49
        return hash[x];
50
    }
51
};
52

53
void solve(void){
54
  cin>>n;
55
    for (int i=1;i<=n;i++)
56
        cin>>a[i];
57
    XORHashing xh(n);
58

59
    vector<vector<int> > pos(n+1);  // 存储每个数字出现的位置
60
    vector<Num> pre(n+1); // 前缀和，初始只有0
61
    map<Num,int> cnt;   // 存储每个前缀和出现的次数
62
    int l=0;
63
    ll ans=0;
64
    cnt[pre[0]]=1;
65
    for (int i=1;i<=n;i++){
66
        pre[i]=pre[i-1]^xh.get_hash(a[i]);
67
        pos[a[i]].push_back(i);
68
        if (pos[a[i]].size()>=(KNUM+1)){
69
            int target=pos[a[i]][pos[a[i]].size()-(KNUM+1)];
70
            while (l<target)
71
                --cnt[pre[l++]];
72
        }
73
        ans+=cnt[pre[i]];
74
        ++cnt[pre[i]];
75
    }
76
    cout<<ans<<endl;
77
}
78

79
int main(){
80
  std::ios::sync_with_stdio(false);
81
  std::cin.tie(nullptr);
82
  std::cout.tie(nullptr);
83
  int t=1;
84
//  cin>>t;
85
  while (t--)
86
    solve();
87
  return 0;
88
}

2024牛客暑期多校7 - D（出现 $k$ 次）#

题目和前面类似，但是由 $3$ 次改成了任意 $k$ 次，同时数据规模 $a_i$ 也从 $[1,n]$ 变成了 $[0,1e9]$ 。

对于改成任意 $k$ 次，只需要将KNUM进制改成变量即可：

1
// #define KNUM (3)    // K=3进制
2
#define KLEN (64)   // 用K进制64位数表示
3
int KNUM=3;

对于 $a_i$ 的数据规模扩大，只需要离散化即可，这里可以预处理，把每个数都映射回 $[1,n]$ ，因为我们不关心具体的值，只关心是否相等。

1
/* 对x数组做离散化重映射 */
2
/**
3
例如，输入 1 1 4 5 1 4
4
修改为 1 1 2 3 1 2
5
*/
6
void prepare(int x[], int len){
7
    int b[len];
8
    memcpy(b,x,sizeof(b));
9
    sort(b,b+len);
10
    unordered_map<int,int> tag;
11
    int cnt=1;
12
    tag.insert(make_pair(b[0],1));
13
    for (int i=1;i<len;i++)
14
        if (b[i]!=b[i-1])
15
            tag.insert(make_pair(b[i],++cnt));
16
    for (int i=0;i<len;i++)
17
        x[i]=tag[x[i]];
18
}

完整代码：

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
//#undef LOCAL_DEBUG
5
#ifdef LOCAL_DEBUG
6
#include "debug.h"
7
#else
8
#define debug(...) (void)0
9
#define debug_array(arr, len) (void)0
10
#endif
11

12
typedef unsigned long long ull;
13
typedef long long ll;
14
typedef pair<int,int> P;
15
const int maxn=5e5;
16

17
int n;
18
int a[maxn+5];
19

20
// #define KNUM (3)    // K=3进制
21
#define KLEN (64)   // 用K进制64位数表示
22
int KNUM=3;
23
typedef array<int, KLEN> Num;
24
Num operator ^(const Num &a, const Num &b){
25
    Num c;
26
    for (int i=0;i<KLEN;i++){
27
        c[i]=a[i]+b[i];
28
        if (c[i]>=KNUM)
29
            c[i]-=KNUM;
30
    }
31
    return c;
32
}
33
mt19937 rnd(time(0));
34
Num gen(void){  // 生成一个随机的K进制数
35
    Num ret;
36
    for (int i=0;i<KLEN;i++)
37
        ret[i]=rnd()%KNUM;
38
    return ret;
39
}
40

41
struct XORHashing {
42
    vector<Num> hash;
43
    // 初始化哈希[0,n]
44
    XORHashing(int n){
45
        hash.resize(n+1);
46
        for (int i=0;i<=n;i++)
47
            hash[i]=gen();
48
    }
49
    Num get_hash(int x){
50
        return hash[x];
51
    }
52
};
53

54
void prepare(int x[], int len){
55
    int b[len];
56
    memcpy(b,x,sizeof(b));
57
    sort(b,b+len);
58
    unordered_map<int,int> tag;
59
    int cnt=1;
60
    tag.insert(make_pair(b[0],1));
61
    for (int i=1;i<len;i++)
62
        if (b[i]!=b[i-1])
63
            tag.insert(make_pair(b[i],++cnt));
64
    for (int i=0;i<len;i++)
65
        x[i]=tag[x[i]];
66
}
67

68
void solve(void){
69
  cin>>n>>KNUM;
70
    for (int i=1;i<=n;i++)
71
        cin>>a[i];
72
    prepare(a+1,n);
73
    XORHashing xh(n);
74

75
    vector<vector<int> > pos(n+1);  // 存储每个数字出现的位置
76
    vector<Num> pre(n+1); // 前缀和，初始只有0
77
    map<Num,int> cnt;   // 存储每个前缀和出现的次数
78
    int l=0;
79
    ll ans=0;
80
    cnt[pre[0]]=1;
81
    for (int i=1;i<=n;i++){
82
        pre[i]=pre[i-1]^xh.get_hash(a[i]);
83
        pos[a[i]].push_back(i);
84
        if (pos[a[i]].size()>=(KNUM+1)){
85
            int target=pos[a[i]][pos[a[i]].size()-(KNUM+1)];
86
            while (l<target)
87
                --cnt[pre[l++]];
88
        }
89
        ans+=cnt[pre[i]];
90
        ++cnt[pre[i]];
91
    }
92
    cout<<ans<<endl;
93
}
94

95
int main(){
96
  std::ios::sync_with_stdio(false);
97
  std::cin.tie(nullptr);
98
  std::cout.tie(nullptr);
99
  int t=1;
100
  cin>>t;
101
  while (t--)
102
    solve();
103
  return 0;
104
}

其他题（TODO）：

参考：

【算法笔记】杂项算法——异或哈希（xor-hashing）

Codeforces - XOR Hashing [TUTORIAL]

异或哈希入门：区间集合判同#

区间元素出现次数#

codeforces - 1418 - G（出现3次）#

2024牛客暑期多校7 - D（出现k kk次）#

2024牛客暑期多校7 - D（出现 $k$ 次）#