http://codeforces.com/contest/1395
E. Boboniu Walks on Graph
题意：给定一张有向图，有边权，每点出度最多为k，k≤9，每一个出度为 i 的点取第 ci 小的出边，这些 c1,c2,⋯,ck 组成一个tuple，问有多少种tuple，使得每个点都至少在某个环里。
集合哈希
由于每点取一条出边，所以要每点在一个环里，等价于每点被一条边指着。
k 很小，可以直接暴力枚举tuple中每个数，需要 O(1) 判断这个tuple是否满足条件。
先预处理出出度为 i 的点，所有第 j 小的边，并对这个集合进行哈希。对于一个tuple，可以把这 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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e6 + 10;
const ll mod = 1e9 + 7;
int n, m, k;
typedef pair<int, int>pii;
vector<pii>G[N];
vector<int>vc[10][10];
ll all;
ll p[N], a[10][10], t[10];
ll ans;
void dfs(int dep) {
if (dep == k + 1) {
ll tmp = 0ll;
for (int i = 1; i <= k; i++) {
tmp = (tmp + a[i][t[i]]) % mod;
}
if (tmp == all)ans++;
return;
}
for (int i = 1; i <= dep; i++) {
t[dep] = i;
dfs(dep + 1);
}
}
int main() {
scanf("%d%d%d", &n, &m, &k);
p[0] = 1ll;
for (int i = 1; i <= n; i++)p[i] = p[i - 1] * 10 % mod;
for (int i = 1; i <= n; i++) {
all = (all + i * p[i] % mod) % mod;
}
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(pii(w, v));
}
for (int i = 1; i <= n; i++) {
sort(G[i].begin(), G[i].end());
for (int j = 1; j <= (int)G[i].size(); j++)vc[(int)G[i].size()][j].push_back(G[i][j - 1].second);
}
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= i; j++) {
for (int u : vc[i][j]) {
a[i][j] = (a[i][j] + u * p[u] % mod) % mod;
}
}
}
dfs(1);
printf("%lld\n", ans);
return 0;
}
|
