mydcwfy's Blog

BZOJ1488 [HNOI2009]图的同构

Posted on
Symbols count in article: 1.6k Reading time ≈ 3 mins.

题意：问点数为 $n$ 的本质不同无向图个数。$n\leq 60$，对 997 取模。

本质不同，显然是群论知识了。

有没有可以使用 2 种颜色来表示，现在就相当于是无向完全图个数计数。

容易发现一共有 $n!$ 种不同的点置换。现在考虑对于每种不同的置换求不动点的个数。

对于一个置换长度为 $k$ 内部的循环，有 $\lfloor\dfrac k2\rfloor$ 种不同的等价类，画画图就知道了。

对于两个长度为 $k_1, k_2$ 的点置换之间的边，我们可以一直转的话，可以得到下面这种情况：

容易发现这样中间的 6 条边都是一个等价类。该图比较特殊，如果画一些 $k_1 = 4, k_2 = 6$ 之类的情况的话会发现有 $\gcd(k_1, k_2)$ 个等价类。

这样算下来一共等价类的个数为：

注意上面的 $k_1, k_2$ 不能来自同一个置换。

这样直接计算是 $O(n!)$ 的，无法接受。

注意到我们只需要找到每一个循环的长度即可，然后考虑如果我们只枚举所有循环的长度如何计算。这样其实是整数划分的个数，大概为 $O(\dfrac{10 ^ {\sqrt n}}{n})$，可以接受。

如果我们已经定义了每一个长度为 $b_i$，每一个长度的循环个数为 $c_i$，那么首先每一个置换是一个圆排列，所以需要除以 $b_i$，然后不同长度的可以任意变换，需要除以 $c_i!$，那么整个的答案就是：

$n!$ 可以消去，直接计算即可。时间复杂度 $O(\dfrac{10 ^ {\sqrt n}}{n}\mathrm{poly} n)$，可以通过。

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

void solve()
{
	// puts("One Division");
	// for (int i = 1; i <= tot; ++ i) printf("%d cnt = %d\n", p[i], cnt[i]);
	int k = 0, ans;
	for (int i = 1; i <= tot; ++ i)
		k += p[i] / 2 * cnt[i] + p[i] * cnt[i] * (cnt[i] - 1) / 2;
	for (int i = 1; i <= tot; ++ i)
		for (int j = i + 1; j <= tot; ++ j)
			k += g[p[i]][p[j]] * cnt[i] * cnt[j];
	ans = qpow(2, k);
	for (int i = 1; i <= tot; ++ i)
		ans = (LL) ans * qpow(p[i], Mod - 1 - cnt[i]) % Mod * infact[cnt[i]] % Mod;
	// std::cout << ans << '\n';
	adj(res += ans - Mod);
}

void dfs(int ls, int rem)
{
	if (rem == 0) return solve();
	++ tot;
	for (int i = ls + 1; i <= rem; ++ i)
		for (p[tot] = i, cnt[tot] = 1; cnt[tot] * i <= rem; ++ cnt[tot])
			dfs(i, rem - i * cnt[tot]);
	-- tot;
}

int main()
{
	init();
	std::cin >> n;
	for (int i = 0; i <= n; ++ i)
		for (int j = 0; j <= n; ++ j)
			g[i][j] = Gcd(i, j);
	dfs(0, n);
	std::cout << res << '\n';
	return 0;
}