PT07D - Let us count 1 2 3

发表于
https://www.spoj.com/problems/PT07D/en/

题目链接

PT07D - Let us count 1 2 3」PATH

做法

$ k = 1 $ ： 树的 $ Prufer $ 序列个数为 $ n^{n - 2} $ 。
$ k = 2 $ ： 树的 $ Prufer $ 序列选一个为根， $ n^{n - 1} $ 。
$ k = 3 $ ：
令 $ f_i $ 为节点数为 $ i $ 时无标号有根树的方案数，生成函数为 $ F(x) = \sum f_i x^i $ 。
考虑到一棵无标号有根树可以看做一个无标号有根森林加一个根组成，而一种大小为 $ k $ 的子树贡献用生成函数表示为 $ \sum x^{ki} = (1 - x^k)^{-1} $ ，一共有 $ f_k $ 种，即 $ (1 - x^k)^{-f_k} $ ，则：
$$
F(x) = x \prod_{k > 0} (1 - x^k)^{-f_k}
$$
两边取 $ \ln $ 并求导得：
$$
\frac{F’(x)}{F(x)} = \frac{1}{x} + \sum_{k > 0} k f_k \frac{x^{k - 1}}{1 - x^k}\\
x F’(x) = F(x) + (\sum_{k > 0} k f_k \frac{x^{k - 1}}{1 - x^k})F(x)\\
n f_n = f_n + \sum_{i > 0} f_i \sum_{k | n - i} k f_k
$$
可以 $ O(n^2) $ 算出 $ f_n $ 。
$ k = 4 $ ：
考虑怎么唯一表示一棵树，我们可以用重心表示，所以把根不是重心的都减去。 一个根不为重心，那么有且仅有一个子树大小大于 $ \frac{n}{2} $ ：
$$
ans = f_n - \sum_{i = 1}^{\frac{n}{2}} f_i f_{n - i}\\
ans += f_{\frac{n}{2}} f_{\frac{n}{2}} - f_{\frac{n}{2}}(f_{\frac{n}{2}} - 1) / 2
$$

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int k, n, p;
int f[10010], g[10010], h[10010];

int ksm(int x, int y = p - 2) {
	int w = 1;
	for(; y; y >>= 1, x = x * x % p) if(y & 1) w = w * x % p;
	return w;
}
void solve1() {
	f[1] = 1; for(int i = 1; i <= n; i++) g[i] = 1;
	for(int i = 2; i <= n; i++) {
		f[i] = 0;
		for(int j = 1; j < i; j++) f[i] = (f[i] + f[j] * g[i - j]) % p;
		f[i] = f[i] * ksm(i - 1, p - 2) % p;
		for(int j = i, t = i * f[i] % p; j <= n; j += i) g[j] = (g[j] + t) % p;
	}
}
void solve2() {
	solve1(); int inv2 = (p + 1) / 2;
	for(int i = 1; i <= n; i++) {
		int cnt = 0;
		for(int j = (i - 1) / 2; j; j--) cnt = (cnt + f[j] * f[i - j]) % p;
		if(!(i & 1)) cnt = (cnt + (ll)f[i / 2] * (f[i / 2] - 1) * inv2 % p) % p;
		h[i] = (f[i] - cnt + p) % p;
	}
	printf("%d\n", h[n]);
}
int main() {
	for(; scanf("%d%d%d", &k, &n, &p) != EOF;) {
		if(k == 1) printf("%d\n", n == 1 ? 1 : ksm(n % p, n - 2));
		else if(k == 2) printf("%d\n", ksm(n % p, n - 1));
		else if(k == 3) solve1(), printf("%d\n", f[n]);
		else solve2();
	}
	return 0;
}