UVA 11174 Stand in a Line - 樹形 DP 計數排列數

問題描述

給定有向森林（每個節點最多一個父節點），求合法排列數：父節點必須出現在子節點之前。模 1e9+7。

樹形 DP + 多重集排列

對每棵樹根，計算以該根為根的子樹的合法排列數。狀態：

• size[u]：子樹節點數。
• dp[u]：子樹內合法排列數。

轉移：對節點 u，合併子樹 v。合併兩個序列的方法數為多項式係數：C(size[u]-1+size[v], size[v])。即插空法。

dp[u] = dp[u] * dp[v] % MOD * C(size[u]-1+size[v], size[v]) % MOD。 size[u] += size[v]。

虛根 0 連接所有樹根，最終答案 dp[0]。

代碼實現（Java）

import java.util.*;

public class Main {
    static final int MOD = 1000000007, N = 40010;
    static List[] G = new ArrayList[N];
    static long[] dp = new long[N], fac = new long[N], invFac = new long[N];
    static int[] sz = new int[N];
    static int n, m;

    static long modPow(long a, long e) {
        long r = 1;
        while (e > 0) { if ((e & 1) == 1) r = r * a % MOD; a = a * a % MOD; e >>= 1; }
        return r;
    }

    static long C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fac[n] * invFac[k] % MOD * invFac[n - k] % MOD;
    }

    static void dfs(int u) {
        sz[u] = 1; dp[u] = 1;
        for (int v : G[u]) {
            dfs(v);
            dp[u] = dp[u] * dp[v] % MOD * C(sz[u] - 1 + sz[v], sz[v]) % MOD;
            sz[u] += sz[v];
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        fac[0] = 1;
        for (int i = 1; i < N; i++) fac[i] = fac[i-1] * i % MOD;
        invFac[N-1] = modPow(fac[N-1], MOD-2);
        for (int i = N-2; i >= 0; i--) invFac[i] = invFac[i+1] * (i+1) % MOD;

        int T = in.nextInt();
        while (T-- > 0) {
            n = in.nextInt(); m = in.nextInt();
            for (int i = 0; i <= n; i++) { G[i] = new ArrayList<>(); }
            int[] deg = new int[n+1];
            for (int i = 0; i < m; i++) {
                int u = in.nextInt(), v = in.nextInt();
                G[v].add(u); deg[u]++;
            }
            for (int i = 1; i <= n; i++) if (deg[i] == 0) G[0].add(i);
            dfs(0);
            System.out.println(dp[0]);
        }
    }
}

關鍵點

• 預計算階乘與逆元，O(1) 計算組合數。
• 虛根技巧統一處理森林。
• 插空合併子序列：原序列長 a，新序列長 b，合併方法數 C(a+b, b)。