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

ACM
6.8k words

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

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

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

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

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

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

p≈(106)2264≈5.42×10−8p\approx\frac{(10^6)^2}{2^{64}}\approx 5.42\times 10^{-8}

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

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

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
typedef unsigned long long ull;

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

struct XORHashing {
    int len;
    vector<int> s;
    vector<ull> hash[2]; // 哈希值

    void init(const vector<int>& str){
        s=str;
        len=s.size();
        ull xort;
        for (int p=0;p<2;p++) {
            hash[p].resize(len+1);
            hash[p][0]=0;
            for (int i=1;i<=len;i++) {
                if (XORHash_map[p].find(s[i-1])==XORHash_map[p].end())
                    XORHash_map[p].insert(make_pair(s[i-1],rnd()));
                xort=XORHash_map[p][s[i-1]];
                hash[p][i]=hash[p][i-1]^xort; 
            }
        }
    }
    // 获取子字符串[s, e]的异或哈希值，序号从0开始
    pair<ull, ull> get_hash(int s, int t) {
        ull hash1=(hash[0][t+1]^hash[0][s]);
        ull hash2=(hash[1][t+1]^hash[1][s]);
        return {hash1, hash2};
    }
};

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

区间元素出现次数

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

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

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

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

codeforces - 1418 - G（出现3次）

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

  • a[1..6]=[1,2,2,2,1,1]a[1..6] = [1, 2, 2, 2, 1, 1];
  • a[2..4]=[2,2,2]a[2..4] = [2, 2, 2];
  • a[7..9]=[2,2,2]a[7..9] = [2, 2, 2].

计算给定的数组 aa 的好的子数组的数目。

数据规模：1≤n≤5e51\leq n\leq 5e5

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
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;

//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#endif

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=5e5;

int n;
int a[maxn+5];

#define KNUM (3)    // K=3进制
#define KLEN (64)   // 用K进制64位数表示
typedef array<int, KLEN> Num;
Num operator ^(const Num &a, const Num &b){
    Num c;
    for (int i=0;i<KLEN;i++){
        c[i]=a[i]+b[i];
        if (c[i]>=KNUM)
            c[i]-=KNUM;
    }
    return c;
}
mt19937 rnd(time(0)); 
Num gen(void){  // 生成一个随机的K进制数
    Num ret;
    for (int i=0;i<KLEN;i++)
        ret[i]=rnd()%KNUM;
    return ret;
}

struct XORHashing {
    vector<Num> hash;
    // 初始化哈希[0,n]
    XORHashing(int n){
        hash.resize(n+1);
        for (int i=0;i<=n;i++)
            hash[i]=gen();
    }
    Num get_hash(int x){
        return hash[x];
    }
};

void solve(void){
	cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    XORHashing xh(n);

    vector<vector<int> > pos(n+1);  // 存储每个数字出现的位置
    vector<Num> pre(n+1); // 前缀和，初始只有0
    map<Num,int> cnt;   // 存储每个前缀和出现的次数
    int l=0;
    ll ans=0;
    cnt[pre[0]]=1;
    for (int i=1;i<=n;i++){
        pre[i]=pre[i-1]^xh.get_hash(a[i]);
        pos[a[i]].push_back(i);
        if (pos[a[i]].size()>=(KNUM+1)){
            int target=pos[a[i]][pos[a[i]].size()-(KNUM+1)];
            while (l<target)
                --cnt[pre[l++]];
        }
        ans+=cnt[pre[i]];
        ++cnt[pre[i]];
    }
    cout<<ans<<endl;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t=1;
//	cin>>t;
	while (t--)
		solve();
	return 0;
}

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

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

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

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

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

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

完整代码：

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;

//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#endif

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=5e5;

int n;
int a[maxn+5];

// #define KNUM (3)    // K=3进制
#define KLEN (64)   // 用K进制64位数表示
int KNUM=3;
typedef array<int, KLEN> Num;
Num operator ^(const Num &a, const Num &b){
    Num c;
    for (int i=0;i<KLEN;i++){
        c[i]=a[i]+b[i];
        if (c[i]>=KNUM)
            c[i]-=KNUM;
    }
    return c;
}
mt19937 rnd(time(0)); 
Num gen(void){  // 生成一个随机的K进制数
    Num ret;
    for (int i=0;i<KLEN;i++)
        ret[i]=rnd()%KNUM;
    return ret;
}

struct XORHashing {
    vector<Num> hash;
    // 初始化哈希[0,n]
    XORHashing(int n){
        hash.resize(n+1);
        for (int i=0;i<=n;i++)
            hash[i]=gen();
    }
    Num get_hash(int x){
        return hash[x];
    }
};

void prepare(int x[], int len){
    int b[len];
    memcpy(b,x,sizeof(b));
    sort(b,b+len);
    unordered_map<int,int> tag;
    int cnt=1;
    tag.insert(make_pair(b[0],1));
    for (int i=1;i<len;i++)
        if (b[i]!=b[i-1])
            tag.insert(make_pair(b[i],++cnt));
    for (int i=0;i<len;i++)
        x[i]=tag[x[i]];
}

void solve(void){
	cin>>n>>KNUM;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    prepare(a+1,n);
    XORHashing xh(n);

    vector<vector<int> > pos(n+1);  // 存储每个数字出现的位置
    vector<Num> pre(n+1); // 前缀和，初始只有0
    map<Num,int> cnt;   // 存储每个前缀和出现的次数
    int l=0;
    ll ans=0;
    cnt[pre[0]]=1;
    for (int i=1;i<=n;i++){
        pre[i]=pre[i-1]^xh.get_hash(a[i]);
        pos[a[i]].push_back(i);
        if (pos[a[i]].size()>=(KNUM+1)){
            int target=pos[a[i]][pos[a[i]].size()-(KNUM+1)];
            while (l<target)
                --cnt[pre[l++]];
        }
        ans+=cnt[pre[i]];
        ++cnt[pre[i]];
    }
    cout<<ans<<endl;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t=1;
	cin>>t;
	while (t--)
		solve();
	return 0;
}

其他题（TODO）：

参考：

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

Codeforces - XOR Hashing [TUTORIAL]