golang 解法, 执行用时: 204 ms, 内存消耗: 40.5 MB, 提交时间: 2023-10-25 11:30:08

func waysToBuildRooms(prevRoom []int) int {
    var ans ,mod,div int64
    ans=1
    mod = 1000000007
    subtree := make([]int64,len(prevRoom))//统计子树size
    child := make([][]int, len(prevRoom))//树结构
    for i:=0;i<len(prevRoom);i++{
        ans= ans *int64(i+1)
        ans = ans % mod
        if i>0 {child [prevRoom[i]] = append(child [prevRoom[i]],i)}
    }
    countsub(0,subtree,child)   
    div = 1
    for i:=0;i<len(prevRoom);i++{
        div = div*subtree[i]
        div = div%mod
    }
    ans = ans* inver(div,mod)// 排除掉所有不符合限制的排列
    return int(((ans%mod)+mod)%mod)
}

func countsub(cur int, subtree []int64, child[][]int){
    var rt int64
    rt=1
    for i:=0;i<len(child[cur]);i++{
        countsub(child[cur][i],subtree,child)
        rt+=subtree[child[cur][i]]
    }
    subtree[cur]=rt   
}



func inver(a,m int64) int64{
    var rt ,ry int64;
    ExGcd(a,m,&rt,&ry)
    return rt
}

func ExGcd(a,b int64, x,y *int64) int64{
    if b==0{
        *x=1;
        *y=0;
        return a;
    }
    gcd:=ExGcd(b,a%b,x,y);
    var temp,k int64;
    k=a/b;
    temp=*x;
    *x=*y;
    *y=temp-k*(*y);
    return gcd;
}

golang 解法, 执行用时: 436 ms, 内存消耗: 45.1 MB, 提交时间: 2023-10-25 11:29:57

const mod int64 = 1000000007
func waysToBuildRooms(prevRoom []int) int {
    n := len(prevRoom)
    fac, inv, graph := make([]int64, n + 1), make([]int64, n + 1), map[int][]int{}
    var f int64 = 1
    for i := 1; i <= n; i++ {
        f = f * int64(i) % mod
        fac[i] = f
        inv[i] = quickPower(f, mod - 2)
        graph[prevRoom[i-1]] = append(graph[prevRoom[i-1]], i-1)
    }

    var dfs func(i int) []int64
    dfs = func(i int) []int64 {
        var size, res int64
        size, res = 0, 1
        for _, child := range graph[i] {
            cur := dfs(child)
            size += cur[0]
            if size > cur[0] {
                res = (((res * cur[1] % mod) * fac[size] % mod) * inv[cur[0]] % mod) * inv[size - cur[0]] % mod
            } else {
                res = res * cur[1] % mod
            }
        }
        return []int64{size + 1, res}
    }

    return int(dfs(0)[1])
}

func quickPower(x, y int64) int64 {
    var res int64 = 1
    for ; y > 0; y>>=1 {
        if (y & 1) == 1 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

java 解法, 执行用时: 186 ms, 内存消耗: 91.3 MB, 提交时间: 2023-10-25 11:29:33

class Solution {
    private static final int mod = (int)1e9 + 7;
    private static final int[] fac = new int[100005];
    private static final int[] inv = new int[100005];
    static{
        long f = 1;
        for(int i=1;i<=100000;i++){
            f = f * i % mod;
            fac[i] = (int)f;
            inv[i] = quickPower(fac[i], mod - 2);
        }
    }

    private Map<Integer, List<Integer>> graph;

    public int waysToBuildRooms(int[] prevRoom) {
        graph = new HashMap<>();
        for(int i=0;i<prevRoom.length;i++){
            List<Integer> list = graph.getOrDefault(prevRoom[i], new ArrayList<>());
            list.add(i);
            graph.put(prevRoom[i], list);
        }
        return dfs(0)[1];
    }

    private int[] dfs(int i){
        int size = 0;
        long res = 1;
        if(graph.containsKey(i)){
            for(Integer child: graph.get(i)){
                int[] cur = dfs(child);
                size += cur[0];
                if (size > cur[0]){
                    res = res * fac[size] % mod;
                    res = res * inv[size-cur[0]] % mod;
                    res = res * inv[cur[0]] % mod;
                }
                res = res * cur[1] % mod;
            }
        }
        return new int[]{++size, (int)res};
    }

    private static int quickPower(int x, int n) {
        long ans = 1, lx = (long)x;
        while(n > 0){
            if((n & 1) == 1)
                ans = ans * lx % mod;
            lx = lx * lx % mod;
            n >>= 1;
        }
        return (int)ans;
    }
}

python3 解法, 执行用时: 3400 ms, 内存消耗: 153.3 MB, 提交时间: 2023-10-25 11:29:14

class Solution:
    def waysToBuildRooms(self, prevRoom: List[int]) -> int:
        connect = defaultdict(list)
        for i,num in enumerate(prevRoom):
            connect[num].append(i)

        # 返回:元素个数,拓扑排序方案数
        def dfs(idx):
            nodes, ans = 0, 1
            for subnode in connect[idx]:
                nodes_, ans_ = dfs(subnode)
                nodes += nodes_
                # 因为当前的拓扑排序方案数不影响加入该子树后的拓扑排序方案数，所以是乘法叠加
                # 新的拓扑排序方案数为: 当前的拓扑排序方案数 * 从nodes个位置里选nodes_个位置分配给该子树 * 子树的拓扑排序方案数
                ans = (ans * comb(nodes, nodes_) * ans_) % (10 ** 9 + 7)
            # 加上根节点
            return nodes + 1, ans
        
        return dfs(0)[1]

cpp 解法, 执行用时: 180 ms, 内存消耗: 121.4 MB, 提交时间: 2023-10-25 11:28:52

class Solution {
public:
    static constexpr int mod = 1000000007;
    
    // 快速幂
    static constexpr long long power(long long x, size_t n) {
        long long ans = 1;
        for (auto i = n;i;i /= 2) {
            if (i % 2) ans = ans * x % mod;
            x = x * x % mod;
        }
        return ans;
    }
    
    int waysToBuildRooms(vector<int>& prevRoom) {
        const int n = prevRoom.size();
        // 用拓扑排序的方式进行动态规划
        vector<int> deg(n, 0);
        for (int i = 0;i < n;++i)
            if (0 <= prevRoom[i])
                ++deg[prevRoom[i]];
        queue<int> q;
        vector<int> dp(n, 1);
        vector<int> sizes(n, 1);
        for (int i = 0;i < n;++i)
            if (deg[i] == 0) q.push(i);
        // 计算阶乘及其乘法逆元
        vector<int> fac(n + 1, 1);
        vector<int> inv(n + 1, 1);
        for (int i = 2;i <= n;++i)
            fac[i] = 1ll * i * fac[i - 1] % mod;
        inv[n] = power(fac[n], mod - 2);
        for (int i = n;i > 2;--i)
            inv[i - 1] = 1ll * i * inv[i] % mod;
        // 动态规划
        for (;!q.empty();q.pop()) {
            const int u = q.front();
            dp[u] = 1ll * dp[u] * fac[sizes[u] - 1] % mod;
            const int v = prevRoom[u];
            if (v < 0) continue;
            sizes[v] += sizes[u];
            if (--deg[v] == 0) q.push(v);
            dp[v] = 1ll * dp[v] * inv[sizes[u]] % mod * dp[u] % mod;
        }
        return dp[0];
    }
};

python3 解法, 执行用时: 3908 ms, 内存消耗: 167.1 MB, 提交时间: 2023-10-25 11:28:22

class Solution:
    def waysToBuildRooms(self, prevRoom: List[int]) -> int:
        mod = 10**9 + 7
        
        n = len(prevRoom)
        # fac[i] 表示 i!
        # inv[i] 表示 i! 的乘法逆元
        fac, inv = [0] * n, [0] * n
        fac[0] = inv[0] = 1
        for i in range(1, n):
            fac[i] = fac[i - 1] * i % mod
            # 使用费马小定理计算乘法逆元
            inv[i] = pow(fac[i], mod - 2, mod)
        
        # 构造树
        edges = defaultdict(list)
        for i in range(1, n):
            edges[prevRoom[i]].append(i)
        
        f, cnt = [0] * n, [0] * n
        
        def dfs(u: int) -> None:
            f[u] = 1
            for v in edges[u]:
                dfs(v)
                # 乘以左侧的 f[ch] 以及右侧分母中 cnt[ch] 的乘法逆元
                f[u] = f[u] * f[v] * inv[cnt[v]] % mod
                cnt[u] += cnt[v]
            # 乘以右侧分子中的 (cnt[i] - 1)!
            f[u] = f[u] * fac[cnt[u]] % mod
            cnt[u] += 1
        
        dfs(0)
        return f[0]

cpp 解法, 执行用时: 532 ms, 内存消耗: 225.7 MB, 提交时间: 2023-10-25 11:28:07

class Solution {
private:
    static constexpr int mod = 1000000007;
    using LL = long long;

public:
    int waysToBuildRooms(vector<int>& prevRoom) {
        
        // 快速幂计算 x^y
        auto quickmul = [&](int x, int y) {
            int ret = 1, cur = x;
            while (y) {
                if (y & 1) {
                    ret = (LL)ret * cur % mod;
                }
                cur = (LL)cur * cur % mod;
                y >>= 1;
            }
            return ret;
        };
        
        int n = prevRoom.size();
        // fac[i] 表示 i!
        // inv[i] 表示 i! 的乘法逆元
        vector<int> fac(n), inv(n);
        fac[0] = inv[0] = 1;
        for (int i = 1; i < n; ++i) {
            fac[i] = (LL)fac[i - 1] * i % mod;
            // 使用费马小定理计算乘法逆元
            inv[i] = quickmul(fac[i], mod - 2);
        }
        
        // 构造树
        vector<vector<int>> edges(n);
        for (int i = 1; i < n; ++i) {
            edges[prevRoom[i]].push_back(i);
        }
        
        vector<int> f(n), cnt(n);
        function<void(int)> dfs = [&](int u) {
            f[u] = 1;
            for (int v: edges[u]) {
                dfs(v);
                // 乘以左侧的 f[ch] 以及右侧分母中 cnt[ch] 的乘法逆元
                f[u] = (LL)f[u] * f[v] % mod * inv[cnt[v]] % mod;
                cnt[u] += cnt[v];
            }
            // 乘以右侧分子中的 (cnt[i] - 1)!
            f[u] = (LL)f[u] * fac[cnt[u]] % mod;
            ++cnt[u];
        };
        
        dfs(0);
        return f[0];
    }
};