1916. 统计为蚁群构筑房间的不同顺序Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

你是一只蚂蚁，负责为蚁群构筑 n 间编号从 0 到 n-1 的新房间。给你一个下标从 0 开始且长度为 n 的整数数组 prevRoom 作为扩建计划。其中，prevRoom[i] 表示在构筑房间 i 之前，你必须先构筑房间 prevRoom[i] ，并且这两个房间必须直接相连。房间 0 已经构筑完成，所以 prevRoom[0] = -1 。扩建计划中还有一条硬性要求，在完成所有房间的构筑之后，从房间 0 可以访问到每个房间。

你一次只能构筑一个房间。你可以在已经构筑好的房间之间自由穿行，只要这些房间是相连的。如果房间 prevRoom[i] 已经构筑完成，那么你就可以构筑房间 i。

返回你构筑所有房间的不同顺序的数目。由于答案可能很大，请返回对 109 + 7 取余的结果。

示例 1：

输入：prevRoom = [-1,0,1]
输出：1
解释：仅有一种方案可以完成所有房间的构筑：0 → 1 → 2

示例 2：

输入：prevRoom = [-1,0,0,1,2]
输出：6
解释：
有 6 种不同顺序：
0 → 1 → 3 → 2 → 4
0 → 2 → 4 → 1 → 3
0 → 1 → 2 → 3 → 4
0 → 1 → 2 → 4 → 3
0 → 2 → 1 → 3 → 4
0 → 2 → 1 → 4 → 3

提示：

n == prevRoom.length
2 <= n <= 105
prevRoom[0] == -1
对于所有的 1 <= i < n ，都有 0 <= prevRoom[i] < n
题目保证所有房间都构筑完成后，从房间 0 可以访问到每个房间

# 思路

树形dp + 组合数

# 解法

class Solution {

    private final int MAXN = (int) 1e5 + 50, MOD = (int) 1e9 + 7;

    private long[] fac = new long[MAXN], inv = new long[MAXN];

    private List<Integer>[] edges = new ArrayList[MAXN];

    private long[] dp = new long[MAXN], size = new long[MAXN];

    public int waysToBuildRooms(int[] prevRoom) {
        int n = prevRoom.length;
        for (int i = 0; i < n; i++) edges[i] = new ArrayList<>();
        for (int i = 1; i < n; i++) edges[prevRoom[i]].add(i);

        // 预处理组合数
        fac[0] = inv[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i - 1] * i % MOD;
            inv[i] = qpow(fac[i], MOD - 2);
        }

        return (int) dfs(0);
    }

    private long dfs(int x) {
        dp[x] = 1;
        size[x] = 0;
        for (Integer v : edges[x]) {
            dfs(v);
            dp[x] = dp[x] * dp[v] % MOD;
            dp[x] = dp[x] * get((int) size[x] + (int) size[v], (int) size[v]) % MOD;
            size[x] += size[v];
        }
        size[x] += 1;
        return dp[x];
    }

    private long qpow(long a, long k) {
        long ans = 1;
        while (k > 0) {
            if ((k & 1) == 1) ans = ans * a % MOD;
            k >>= 1;
            a = a * a % MOD;
        }
        return ans;
    }

    private long get(int n, int m) {
        return fac[n] % MOD * inv[m] % MOD * inv[n - m] % MOD;
    }
}

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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java