书接上回

为什么随机 hash 用乘法不行，用加法可以啊？

加法代码：

#include<bits/stdc++.h>
using namespace std;
#define W while
#define gc getchar
void Read(int &x) {
	x = 0; char ch = gc();
	W(ch < '0' || ch > '9') ch = gc();
	W(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
}
#define ull unsigned long long
const int N = 100010; int n, q, ans; unordered_map<int, ull> lsh; ull h[N];
ull R(int l, int r) {return rand() % (r - l + 1) + l;}
ull L(int x) {
	if(lsh[x]) return lsh[x];
	return lsh[x] = 1ull * R(2, N) * R(2, N) * R(2, N);
}
int main() {
	srand(time(0)); Read(n); Read(q);
	for(int i = 1; i <= n; i++) {
		int k; Read(k); h[i] = 0;
		W(k--) {int x; Read(x); h[i] += L(x);}
	}
	for(int i = 1; i <= q; i++) {
		int op, x, y; Read(op); Read(x), Read(y);
		if(op == 1) h[y] += h[x], h[x] = 0;
		else {if(h[x] == h[y]) ans ^= i;}
	}
	cout << ans;
	return 0;
}

乘法代码：

#include<bits/stdc++.h>
using namespace std;
#define W while
#define gc getchar
void Read(int &x) {
	x = 0; char ch = gc();
	W(ch < '0' || ch > '9') ch = gc();
	W(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
}
#define ull unsigned long long
const int N = 100010; int n, q, ans; unordered_map<int, ull> lsh; ull h[N];
ull R(int l, int r) {return rand() % (r - l + 1) + l;}
ull L(int x) {
	if(lsh[x]) return lsh[x];
	return lsh[x] = 1ull * R(2, N) * R(2, N) * R(2, N);
}
int main() {
	srand(time(0)); Read(n); Read(q);
	for(int i = 1; i <= n; i++) {
		int k; Read(k); h[i] = 1;
		W(k--) {int x; Read(x); h[i] *= L(x);}
	}
	for(int i = 1; i <= q; i++) {
		int op, x, y; Read(op); Read(x), Read(y);
		if(op == 1) h[y] *= h[x];
		else {if(h[x] == h[y]) ans ^= i;}
	}
	cout << ans;
	return 0;
}

如果是我太菜了就赶紧嘲讽我。