Day 079-Q5 — 多項式べき乗 + 多変数 EGF（連結グラフの EGF exp/log 変換）

問題

整数 $N$ ($1 \le N \le 500$) が与えられる。$N$ 頂点のラベル付き連結グラフの個数 $f(N)$ を $10^9+7$ で割った余りを求めよ。

ここで「ラベル付きグラフ」とは、頂点に $1, 2, \ldots, N$ のラベルが振られており、 頂点集合が同じでも辺集合が異なれば別のグラフとみなす。また、頂点が2つ以上の場合、 孤立した頂点や非連結な成分があれば連結グラフとはみなさない。 $N = 1$ の場合、1頂点のグラフ（辺なし）は連結とみなす。

ヒント（背景）: $N$ 頂点のラベル付き全グラフ数は $g(N) = 2^{N(N-1)/2}$ 個（各辺を独立に有無選択）。 これと連結グラフ数 $f(N)$ の間には指数型母関数（EGF）を介した関係 $$G(x) = \exp(F(x)), \quad G(x) = \sum_{n \ge 0} g(n) \frac{x^n}{n!}, \quad F(x) = \sum_{n \ge 0} f(n) \frac{x^n}{n!}$$ が成り立ち、したがって $F(x) = \log(G(x))$ を計算すれば $f(N)$ が得られる。

入出力例

1

1

3

4

5

728

概念図: EGF の exp/log 変換と連結グラフ

左側の非連結グラフの EGF $G(x)$ に形式的 $\log$ を適用すると、連結グラフの EGF $F(x)$ が得られる。 係数比較により $O(N^2)$ の漸化式として実装できる。

ヒント

MOD = 10**9 + 7
N = int(input())

# g[n] = 2^(n*(n-1)//2)
g = [pow(2, n*(n-1)//2, MOD) for n in range(N+1)]
g[0] = 1

# 階乗と逆階乗
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

# EGF係数
G = [g[n]*inv_fact[n]%MOD for n in range(N+1)]

# 逆数テーブル（線形前処理）
inv = [0]*(N+1); inv[1] = 1
for i in range(2, N+1): inv[i] = -(MOD//i)*inv[MOD%i]%MOD

# poly_log の漸化式
F = [0]*(N+1)
for n in range(1, N+1):
    s = n*G[n]%MOD
    for k in range(1, n):
        s = (s - k*F[k]%MOD*G[n-k])%MOD
    F[n] = s*inv[n]%MOD

# f(N) = F[N] * N!
print(F[N]*fact[N]%MOD)

模範解答

import sys
input = sys.stdin.readline

MOD = 10**9 + 7

def solve():
    N = int(input())

    # 1. g[n] = 2^(n*(n-1)/2): N頂点ラベル付き全グラフ数
    #    g[0] = 1 (空グラフ = 空集合の唯一のグラフ)
    g = [0] * (N + 1)
    g[0] = 1
    for n in range(1, N + 1):
        g[n] = pow(2, n * (n - 1) // 2, MOD)

    # 2. 階乗テーブル（前処理 O(N)）
    fact = [1] * (N + 1)
    for i in range(1, N + 1):
        fact[i] = fact[i - 1] * i % MOD

    # 逆階乗テーブル（前処理 O(N)）
    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

    # 3. EGF係数: G[n] = g[n] / n!  (mod MOD)
    G = [g[n] * inv_fact[n] % MOD for n in range(N + 1)]

    # 4. 逆数テーブル inv[i] = i^{-1} mod MOD  (線形前処理 O(N))
    inv = [0] * (N + 1)
    inv[1] = 1
    for i in range(2, N + 1):
        # i = (MOD // i) * (MOD % i) + (MOD % i) を使った線形前処理
        inv[i] = -(MOD // i) * inv[MOD % i] % MOD

    # 5. poly_log の漸化式: F = log(G) の EGF係数を求める
    #    G = exp(F) を微分: G' = F' * G
    #    => x^{n-1}の係数比較: n*G[n] = Σ_{k=1}^{n} k*F[k]*G[n-k]
    #    => n*F[n] = n*G[n] - Σ_{k=1}^{n-1} k*F[k]*G[n-k]
    #    初期値: F[0] = log(G[0]) = log(1) = 0
    F = [0] * (N + 1)
    F[0] = 0  # log(1) = 0
    for n in range(1, N + 1):
        s = n * G[n] % MOD
        for k in range(1, n):
            s = (s - k * F[k] % MOD * G[n - k]) % MOD
        F[n] = s * inv[n] % MOD

    # 6. f(N) = F[N] * N!  (EGF係数 F[N] = f(N)/N! を元に戻す)
    ans = F[N] * fact[N] % MOD
    print(ans)

solve()

Step-by-Step 解説

Step 1: EGF と連結グラフの関係の導出

$N$ 頂点ラベル付きグラフを「ラベル付き連結成分の集合」と解釈する。 $N$ 頂点のグラフは、頂点 $\{1,\ldots,N\}$ を何らかの部分集合に分割して、 各部分集合上に連結グラフを1つ乗せた構造に対応する。 EGF の「積の公式」（集合の分割を表す）により：

$$G(x) = \sum_{n \ge 0} g(n) \frac{x^n}{n!}, \quad F(x) = \sum_{n \ge 0} f(n) \frac{x^n}{n!}$$

として $G(x) = \exp(F(x))$ が成り立つ。$\exp$ が「ラベル付き集合の分割の EGF 変換」になるのは、 $\exp$ の冪展開が組み合わせ的に集合分割の個数を数えるからである。 逆に $F(x) = \log(G(x))$ を形式的べき級数として計算すれば $f(N) = F[N] \cdot N!$ が得られる。

Step 2: 形式的べき級数の log の漸化式

$G = \exp(F)$ の両辺を形式的微分すると $G'(x) = F'(x) \cdot G(x)$。 $x^{n-1}$ の係数を比較する（$n \ge 1$）：

$$n \cdot G[n] = \sum_{k=0}^{n-1} (k+1) F[k+1] \cdot G[n-1-k] = \sum_{k=1}^{n} k \cdot F[k] \cdot G[n-k]$$

$k = n$ の項（$= n \cdot F[n] \cdot G[0] = n \cdot F[n]$）を左辺に移項すると：

$$n \cdot F[n] = n \cdot G[n] - \sum_{k=1}^{n-1} k \cdot F[k] \cdot G[n-k]$$

$F[0] = \log(G[0]) = \log(1) = 0$ を初期値として、$F[1], F[2], \ldots$ を順に $O(n)$ で求められる。 全体 $O(N^2)$。

Step 3: 境界条件と検算

（実際の実装はすべて mod $10^9+7$ の整数演算で行う）

Step 4: 実装上の注意点まとめ

よくあるミス

次のステップ

• $N \le 10^5$ への拡張: $O(N^2)$ では遅い。多項式逆元（poly_inv）を Newton 法 + NTT で $O(N \log N)$ に実装し、 $\text{poly\_log}(F) = \int (F' / F)$ を同様に $O(N \log N)$ で計算する。
• 有向連結グラフ（強連結）: 弱連結・強連結の EGF は DAG との組み合わせで変換式が変わる。 強連結成分数え上げは多変数 EGF と log/exp の組み合わせで解ける。
• $k$-連結グラフのカウント: 包除原理と EGF を組み合わせて、辺連結度 $\ge k$ のラベル付きグラフ数を求める問題。
• EGF と Set Partition: Bell 数 $B(n) = \sum_{k} S(n,k)$（スターリング数の和）の EGF $= \exp(e^x - 1)$ も 同じ exp/log 変換の枠組みで理解できる。

自己評価