CF1323E Instant Noodles（哈希）

题意

$T$T 组数据，每组数据给出一个 $2N$2N 个点的二分图，给出右边 $n$n 个点的权值，设 $f\left(S\right)$f(S) 表示所有与左边集合 $S$S 有连边的右边点的点权和。求 $f\left(S\right)$f(S) 的 $\gcd$gcd。

分析

对于右边的点：

• 如果没有连边，则可以删去
• 如果有连边情况相同的点，则合并在一起，权值相加

这样，最终得到的是若干个点，每个点对应左边不同的集合，那么答案就是这些点的 $\gcd$gcd，原因是 $\gcd (a,b)=\gcd (a+b,b)$gcd(a,b)=gcd(a+b,b) 的高维形式。

那么应该怎么判断两个点连边情况是否相同呢？
可以使用哈希。下面将介绍几种不同的哈希方法。

法一：双模数哈希

这个大家都会了。

代码如下

#include <bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define base 131
#define N 500005
using namespace std;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
LL z = 1, c[N], g[N], ans;
int hx1, hx2;
vector<int> vec[N];
int main(){
	int i, j, n, m, T, a, b;
	pair<int, int> p;
	scanf("%d", &T);
	while(T--){
		map<pair<int, int>, int> f;
		ans = 0;
		scanf("%d%d", &n, &m);
		for(i = 1; i <= n; i++) g[i] = 0, vec[i].clear(), scanf("%lld", &c[i]);
		for(i = 1; i <= m; i++){
			scanf("%d%d", &a, &b);
			vec[b].push_back(a);
		}
		for(i = 1; i <= n; i++) if(vec[i].size()) sort(vec[i].begin(), vec[i].end());
		for(i = 1; i <= n; i++){
			if(!vec[i].size()) continue;
			hx1 = hx2 = 0;
			for(j = 0; j < vec[i].size(); j++){
				hx1 = (z * hx1 * base % mod1 + vec[i][j]) % mod1;
				hx2 = (z * hx2 * base % mod2 + vec[i][j]) % mod2;
			}
			p = make_pair(hx1, hx2);
			if(!f[p]) f[p] = i;
			g[f[p]] += c[i];
		}
		for(i = 1; i <= n; i++) ans = __gcd(ans, g[i]);
		printf("%lld\n", ans);
	}
	return 0;
}

法二：直接用map对应向量

这个也是很神奇，我之前都不知道 $map$map 可以这样用，即是 map<vector<int>, int>，将向量映射到一个整数。

代码如下

#include <bits/stdc++.h>
#define N 500005
#define LL long long
using namespace std;
LL c[N], ans;
vector<int> vec[N];
int main(){
	int i, j, n, m, T, a, b;
	scanf("%d", &T);
	while(T--){
		ans = 0;
		scanf("%d%d", &n, &m);
		for(i = 1; i <= n; i++) vec[i].clear(), scanf("%lld", &c[i]);
		for(i = 1; i <= m; i++){
			scanf("%d%d", &a, &b);
			vec[b].push_back(a);
		}
		for(i = 1; i <= n; i++) if(vec[i].size()) sort(vec[i].begin(), vec[i].end());
		map<vector<int>, LL> f;
		for(i = 1; i <= n; i++) if(vec[i].size()) f[vec[i]] += c[i];
		for(auto &u: f) ans = __gcd(ans, u.second);
		printf("%lld\n", ans);
	}
	return 0;
}

法三：权值异或

就是给每个位置生成大随机数，然后将一个集合的异或起来，作为哈希值。
然后再用个哈希表把相同哈希值对应的 $c_i$ci​ 加起来。
可以用 mt19937_64 生成大随机数（太神啦）
这个复杂度是最小的，接近 $O\left(n\right)$O(n)

代码如下

#include <bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define N 500005
using namespace std;
uLL ans, v[N], rd[N], c[N];
int id[N];
mt19937_64 rdn(time(0));
int main(){
	int i, j, n, m, T, a, b;
	scanf("%d", &T);
	while(T--){
		unordered_map<uLL, uLL> f;
		ans = 0;
		scanf("%d%d", &n, &m);
		for(i = 1; i <= n; i++) rd[i] = rdn(), scanf("%llu", &c[i]), v[i] = 0;
		for(i = 1; i <= m; i++){
			scanf("%d%d", &a, &b);
			v[b] ^= rd[a];
		}
		for(i = 1; i <= n; i++){
			if(!v[i]) continue;
			f[v[i]] += c[i];
		}
		for(auto u: f) ans = __gcd(ans, u.second);
		printf("%llu\n", ans);
	}
	return 0;
}