bzoj 1005

[HNOI2008]明明的烦恼

Description

自从明明学了树的结构,就对奇怪的树产生了兴趣...... 给出标号为 $1$ 到 $N$ 的点,以及某些点最终的度数, 允许在任意两点间连线,可产生多少棵度数满足要求的树?

Input

第一行为 $N(0 < N \le 1000)$ , 接下来 $N$ 行, 第 $i+1$ 行给出第 $i$ 个节点的度数 $d_i$ , 如果对度数不要求,则输入 $-1$ .

Output

一个整数, 表示不同的满足要求的树的个数, 无解输出 $0$

Sample Input

3
1
-1
-1

Sample Output

题解

首先特判掉 $n = 1$ 和 $n = 2$ 的情况.

当 $n \ge 3$ 时，每个树有一个唯一的长度为 $n - 2$ 的 Prüfer 序列与之对应.

设度数有限制的点的数量为 $c$ ，以及

$s = \sum_{i=1}^{c}{(d_i - 1)}$

由 Prüfer 序列的性质可知一个点的度数减一表示它在这个序列中出现了多少次，所以这个序列要拿出 $s$ 个位置放置有限制的点，剩下的 $n-2-s$ 个位置可以随意放置剩下的 $n - c$ 个点. 总的方案数为

$\begin{aligned} &\binom{n-2}{s} \cdot \begin{pmatrix} s \\ d_1 - 1, d_2 - 1, \dots, d_c - 1 \end{pmatrix} \cdot (n-c)^{n-2-s}\\ =& \frac{(n - 2)!}{(n-2-s)!\prod_{i=1}^c(d_i-1)!} \cdot (n-c)^{n-2-s} \end{aligned}$

显然当 $n - 2 < s$ 或者存在一个节点有 $d_i = 0$ 或 $d_i > n - 1$ 时无解.

代码

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
    static BigInteger[] f = new BigInteger[1024];
    public static void init() {
        f[0] = BigInteger.valueOf(1);
        for (int i = 1; i < 1024; i++)
            f[i] = f[i-1].multiply(BigInteger.valueOf(i));
    }

    static int n = 0;
    static int[] d = new int[1024];
    static int s = 0, c = 0;

    public static void solve() {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        if (1 == n)
        {
            d[0] = cin.nextInt();
            System.out.println( (1 == d[0] * d[0]) ? 1 : 0 );
            return;
        }
        if (2 == n)
        {
            d[0] = cin.nextInt(); d[1] = cin.nextInt();
            if ( (1 == d[0] * d[0]) && (1 == d[1] * d[1]) )
                System.out.println(1);
            else
                System.out.println(0);
            return;
        }
        for (int i = 0; i < n; i++)
        {
            d[i] = cin.nextInt();
            if (0 == d[i] || d[i] > n - 1)
            {
                System.out.println(0);
                return;
            }
            if (-1 == d[i]) continue;
            s += d[i] - 1;
            c++;
        }
        if (n - 2 < s)
        {
            System.out.println(0);
            return;
        }
        BigInteger ans = f[n - 2].divide(f[n - 2 - s]);
        for (int i = 0; i < n; i++)
            if (-1 != d[i])
                ans = ans.divide(f[d[i] - 1]);
        for (int i = 0; i < n - 2 - s; i++)
            ans = ans.multiply(BigInteger.valueOf(n - c));
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        init();
        solve();
    }
}

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
56
57
58
59
60
61
62
63
64
65

# bzoj 1005

# [HNOI2008]明明的烦恼

# Description

# Input

# Output

# Sample Input

# Sample Output

# 题解

# 代码