Day 072-Q5 — 木上の積DP・EGF（根付き木の構造カウント + ラベル付け）

問題

$N$ 頂点のラベル付き根付き木の形状クラスを EGF（指数型母関数）を用いて数え上げる。

頂点 $1, 2, \ldots, N$ にラベルが付いており、根は頂点 $1$ とする。各頂点の子の順序は区別しない。

以下のパラメータを持つ木の数を $10^9 + 7$ で割った余りで求めよ：

• 各頂点の次数（子の数）が $[0, D]$ の範囲
• 根から最も深い葉までの深さが正確に $H$ に等しい

入出力例

5 3 2

60

3 1 2

2

例2: 3頂点パスグラフ（最大次数1、深さ2）。1→2→3 または 1→3→2 の2通り。

概念図: EGF と高さ制限木の漸化式

ヒント（段階的開示）

prev_egf = [0] * (N+1)
prev_egf[1] = 1  # G_0(x) = x (EGF係数: egf[1]=1)

for h in range(1, H+1):
    gpow = [[0]*(N+1) for _ in range(D+2)]
    gpow[0][0] = 1  # G^0 = 1

    for k in range(1, D+1):
        for m in range(N+1):
            if gpow[k-1][m] == 0: continue
            for j in range(1, N+1-m):
                gpow[k][m+j] += gpow[k-1][m] * prev_egf[j] % MOD

    for n in range(1, N+1):
        total = 0
        for k in range(1, min(D, n-1)+1):
            coeff = gpow[k][n-1] * inv_fact[k] % MOD
            total += fact[n-1] * coeff % MOD
        if n == 1: total = 1  # 葉
        curr_g[n] = total % MOD

模範解答 (Python)

コピーimport sys
input = sys.stdin.readline

def solve():
    MOD = 10**9 + 7
    N, D, H = map(int, input().split())

    fact = [1] * (N+1)
    for i in range(1, N+1): fact[i] = fact[i-1]*i%MOD
    inv_fact = [1] * (N+1)
    inv_fact[N] = pow(fact[N], MOD-2, MOD)
    for i in range(N-1, -1, -1): inv_fact[i] = inv_fact[i+1]*(i+1)%MOD

    def compute_g(max_h):
        prev_egf = [0]*(N+1)
        prev_g = [0]*(N+1)
        if N >= 1:
            prev_egf[1] = 1
            prev_g[1] = 1

        for h in range(1, max_h+1):
            gpow = [[0]*(N+1) for _ in range(D+2)]
            gpow[0][0] = 1

            for k in range(1, D+1):
                for m in range(N+1):
                    if gpow[k-1][m] == 0: continue
                    for j in range(1, N+1-m):
                        if prev_egf[j] == 0: continue
                        gpow[k][m+j] = (gpow[k][m+j] + gpow[k-1][m]*prev_egf[j]) % MOD

            curr_g = [0]*(N+1)
            if N >= 1: curr_g[1] = 1

            for n in range(2, N+1):
                total = 0
                for k in range(1, min(D, n-1)+1):
                    coeff = gpow[k][n-1]*inv_fact[k]%MOD
                    total = (total + fact[n-1]*coeff) % MOD
                curr_g[n] = total

            curr_egf = [0]*(N+1)
            for m in range(1, N+1):
                curr_egf[m] = curr_g[m]*inv_fact[m]%MOD

            prev_g = curr_g
            prev_egf = curr_egf

        return prev_g

    gH = compute_g(H)
    if H == 1:
        # h=0: 葉のみ g[0][1]=1, g[0][n]=0 for n>=2
        g0 = [0]*(N+1)
        g0[1] = 1
        gHm1 = g0
    else:
        gHm1 = compute_g(H-1)

    ans = (gH[N] - gHm1[N]) % MOD
    print(ans)

solve()

Step-by-Step 解説

Step 1: EGF による木の数え上げ

ラベル付き根付き木の EGF $T(x) = \sum_{n \ge 1} t_n x^n / n!$ は Cayley 公式から次の方程式を満たす: $T(x) = x \cdot e^{T(x)}$

次数制限がある場合: $T(x) = x \sum_{k=0}^{D} T(x)^k / k!$

Step 2: 高さ制限の導入

高さ $\le h$ の木の EGF $G_h(x)$ の漸化式:

$G_0(x) = x$（葉のみ）から始める。

Step 3: 係数の計算

$[x^n] G_h(x) = g[h][n] / n!$ なので、$g[h][n] = n! \cdot [x^n] G_h(x)$。

$G_{h-1}$ の $k$ 乗の係数を DP で求め、$k = 0, \ldots, D$ で合計。計算量: $O(H \cdot D \cdot N^2)$。

Step 4: 正確な高さ H の木の数

（高さ $\le H$ の木の数から高さ $\le H-1$ の木の数を引く）

よくあるミス

次のステップ

• 発展問題: 非ラベル付き根付き木の数え上げ（Burnside 補題 + EGF）
• 平衡木（balanced tree）の数え上げ
• Pólya の計数定理と木の同型クラス数

自己評価