HDU 5378：樹上標號概率 DP + 模逆元計算方案數

問題重述

n 節點樹，標號 1~n 排列。若節點標號是其子樹中最大值，稱該節點為「好」。求恰有 k 個好節點的排列數。答案 = n! × 概率 p。

DP 狀態定義

dp[i][j]：前 i 個節點（按某拓撲序）中有 j 個好節點的概率。
轉移：第 i 節點子樹大小為 c[i]。它是好節點的概率 = 1/c[i]（在子樹中最大）；不是好節點概率 = (c[i]-1)/c[i]。
dp[i][j] = dp[i-1][j] * (c[i]-1)/c[i] + dp[i-1][j-1] * 1/c[i]

模逆元優化

直接用 double 精度不足；用分數結構體分子分母分別取模會爆 long long。
模逆元：Inv(x) = x^(MOD-2) mod MOD（MOD=1e9+7 為質數）。
轉移變為整數運算：
dp[i][j] = dp[i-1][j] * (c[i]-1) % MOD * Inv(c[i]) % MOD + dp[i-1][j-1] * Inv(c[i]) % MOD

子樹大小計算

DFS 遞歸計算每節點子樹節點數 c[u]，順便預處理 Inv[1..n] 和 n! mod MOD。

完整代碼框架

const long long MOD = 1e9+7;
long long dp[1005][1005], c[1005], Inv[1005];

long long power(long long a, long long p) {
    long long r=1;
    while(p){ if(p&1) r=r*a%MOD; a=a*a%MOD; p>>=1; }
    return r;
}

void dfs(int u, int fa) {
    c[u]=1;
    for(int v:tree[u]) if(v!=fa) {
        dfs(v,u);
        c[u] += c[v];
    }
}

int main() {
    Inv[1]=1;
    for(int i=2;i<=n;++i) Inv[i] = power(i, MOD-2);
    dfs(1,0);
    dp[0][0]=1;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=i;++j) {
            dp[i][j] = dp[i-1][j] * (c[i]-1) % MOD * Inv[c[i]] % MOD;
            if(j) dp[i][j] = (dp[i][j] + dp[i-1][j-1] * Inv[c[i]]) % MOD;
        }
    cout << dp[n][k] * fact[n] % MOD << endl;
}

關鍵點總結

• 概率 DP + 模逆元避免浮點誤差與分數溢出
• 子樹大小決定「好節點」概率
• 最終乘 n! 還原方案數