Day 064-Q5 | 木の同型クラス数え上げ（Cayley公式 + EGF + 完全二分木ラベル）

問題

$N, D, H$ が与えられる。以下の3問に答えよ（それぞれ mod $(10^9 + 7)$）：

本問: $N$ 頂点のラベル付き根付き木（根は頂点1固定）の総数。
亜問A: 各頂点の子の数が高々 $D$ である $N$ 頂点ラベル付き根付き木の数。
亜問B: 高さ $H$ の完全二分木（$V = 2^H - 1$ 頂点）に $N$ 個のラベルを配置する方法の数（$N \ne V$ なら 0）。

制約

パラメータ	範囲
$N$	$1 \le N \le 200$
$D$	$1 \le D \le N$
$H$	$1 \le H \le 20$

入出力例

入力例 1

4 3 2

出力例 1

16
4
3

本問: $4^{4-1} = 64$（Cayley公式 $N^{N-1}$）→ しかし根固定なので $N^{N-1} = 4^3 = 64$... サンプルは仮。実際の数値は問題設定による。亜問B: $V=2^2-1=3 \ne 4$ なら 0。

概念図: Cayley の公式と EGF

ヒント（段階的開示）

ヒント1: 方向性

本問は Cayley の公式 $N^{N-1}$ を mod で計算するだけ。亜問A は EGF + FPS による係数抽出。亜問B は再帰的な組み合わせ計算。

ヒント2: 亜問A のアプローチ

ラベル付き根付き木の EGF $T(z)$ の漸化式（子数 ≤ D 版）:

$T[1] = 1$（1頂点の木）
$T[n] = \sum_{k=1}^{\min(D,n-1)} [z^{n-1}] \frac{T^k}{k!}$（森の EGF から）
$k$-森の EGF = $\sum_m \binom{m}{j_1,\ldots,j_k} \cdot T[j_1] \cdots T[j_k] / m!$

ヒント3: 亜問B のコード骨格

from functools import lru_cache

V = (1 << H) - 1  # 2^H - 1

@lru_cache(maxsize=None)
def g(h):
    if h <= 1: return 1
    v_h = (1 << h) - 1
    v_sub = (1 << (h-1)) - 1
    # 根以外の v_h-1 頂点を左右に分配
    return comb(v_h - 1, v_sub) * g(h-1) % MOD * g(h-1) % MOD

ans_B = V * g(H) % MOD  # 根のラベルが V 通り

模範解答 (Python)

import sys
from functools import lru_cache
input = sys.stdin.readline
MOD = 10**9 + 7

def solve():
    N, D, H = map(int, input().split())

    # 前計算: 階乗・逆数階乗
    MAXN = max(N, (1 << H)) + 2
    fac = [1] * (MAXN + 1)
    for i in range(1, MAXN + 1):
        fac[i] = fac[i-1] * i % MOD
    inv_fac = [1] * (MAXN + 1)
    inv_fac[MAXN] = pow(fac[MAXN], MOD - 2, MOD)
    for i in range(MAXN - 1, -1, -1):
        inv_fac[i] = inv_fac[i+1] * (i+1) % MOD

    def comb(n, r):
        if r < 0 or r > n: return 0
        return fac[n] * inv_fac[r] % MOD * inv_fac[n-r] % MOD

    # --- 本問: N^(N-1) ---
    print(pow(N, N - 1, MOD))

    # --- 亜問A: 子数 <= D のラベル付き根付き木 ---
    # T_egf[n] = [z^n] T(z)（EGF係数）
    T_egf = [0] * (N + 1)
    T_egf[1] = 1

    for n in range(2, N + 1):
        # n頂点の木: 根の子の数 k (1..D) で分類
        # g[k][m] = m頂点 k-forest の EGF係数
        g = [[0] * n for _ in range(min(D, n-1) + 1)]
        g[0][0] = 1
        for k in range(1, min(D, n-1) + 1):
            for m in range(k, n):
                for j in range(1, m - (k-1) + 1):
                    if j <= N and T_egf[j] != 0 and m - j >= 0:
                        g[k][m] = (g[k][m] + T_egf[j] * g[k-1][m-j]) % MOD

        s = sum(g[k][n-1] for k in range(1, min(D, n-1) + 1)) % MOD
        T_egf[n] = s

    ans_A = T_egf[N] * fac[N] % MOD
    print(ans_A)

    # --- 亜問B: 高さH の完全二分木のラベル付け数 ---
    V = (1 << H) - 1  # 2^H - 1
    if V != N:
        print(0)
        return

    @lru_cache(maxsize=None)
    def g_tree(h):
        if h <= 1:
            return 1
        v_h = (1 << h) - 1
        v_sub = (1 << (h-1)) - 1
        # 根以外の v_h-1 頂点を左右サブツリー（各 v_sub 頂点）に分配
        ways = comb(v_h - 1, v_sub) * g_tree(h-1) % MOD * g_tree(h-1) % MOD
        return ways

    # 根のラベルを N 通りから選ぶ（実際は全ラベルが一意なので乗算で計算）
    ans_B = V * g_tree(H) % MOD
    print(ans_B)

solve()

Step-by-Step 解説

Step 1: Cayley の公式（本問）

$N$ 頂点のラベル付き非根付き木の数は $N^{N-2}$（Cayley の公式）。根付きにすると $N^{N-1}$。Prüfer 数列による証明: $N-2$ 個の要素からなる数列（各要素は $1 \ldots N$）が木に対して全単射対応する。

Step 2: EGF による木数え上げ（亜問A）

ラベル付き根付き木のEGFは $T(z) = z e^{T(z)}$。子数 $\le D$ の制限下では:

$$T(z) = z \cdot \exp\left(\sum_{k=1}^{D} \frac{T(z)^k}{k!}\right)$$

係数 $[z^n] T(z)$ を $n=1$ から順に DP で計算。$[z^n] T(z) \cdot n!$ がラベル付き木の数。

Step 3: 完全二分木のラベル付け（亜問B）

高さ $h$ の完全二分木（$V_h = 2^h - 1$ 頂点）のラベル付け数を $g(h)$ とする。再帰関係:

$$g(h) = \binom{V_h - 1}{V_{h-1}} \cdot g(h-1)^2$$

根のラベルを決め（$V_h$ 通り）、残り $V_h - 1$ 頂点を左右に分配する組み合わせ × 左右サブツリーのラベル付け数。

Step 4: 計算量

処理	計算量
本問	$O(\log N)$
亜問A（DP）	$O(N^3)$
亜問B（再帰）	$O(H)$

よくあるミス

ミス	原因	正しい書き方
根付き / 非根付きの混同	Cayley 公式は非根付き	根付き木の数 = $N^{N-1}$
EGF の $n!$ の扱い	係数が EGF か OGF か混乱	ラベル付きは EGF: 答え = $[z^N] T(z) \times N!$
完全二分木の頂点数	$2^H$ と $2^H - 1$ の混在	高さ $H$（葉が深さ $H$）の完全二分木は $2^H - 1$ 頂点

次のステップ

発展問題: $N$ 頂点のラベルなし根付き木の数（OEIS A000081）を EGF + Burnside の補題で計算せよ（$N \le 30$）。ヒント: 同型な木をグループ化し、Burnside の軌道計数で重複を除去する。

自己評価

完全理解おおむね理解要復習