AtCoder Regular Contest 162 D問題メモ

AtCoder Regular Contest 162

D - Smallest Vertices

問題

「根付き有向木」を以下で定義する
- 頂点 $1$ を根とし、親から子に向かって有向辺が張られている木
「良い頂点」を以下で定義する
- 頂点 $v$ の部分木に含まれる頂点のうち、最小の頂点番号が $v$ 自身である頂点
「良い木」を以下で定義する
- $N$ 頂点の根付き有向木であり、各頂点の出次数は $d_1,...,d_N$
全ての良い木に対する、良い頂点の個数の総和を $\mod{99824433}$ で求めよ
$1 \le N \le 500$
$d_1 \ge 1$
$\sum d_i=N-1$

解法

ケイリーの公式を活用する。

Cayley の定理と、頂点次数制約のついた全域木の数え上げ - けんちょんの競プロ精進記録

今回の場合、次数 $d_i$ には親に向かう辺がカウントされていないので、$i \neq 1$ の $d_i$ にそれぞれ1を足すと、無向木の次数に相当するものになる。（が、以下の説明ではとりあえず $d_i$ のままで説明する）

まず、良い木の個数は、ケイリーの公式を使って、以下のようになる。

$\displaystyle \frac{(N-2)!}{(d_1-1)!\prod_{i=2}^{N}d_i!}$

主客転倒して、各頂点に対して「自身が良い頂点となる良い木の個数」を求め、合計することを考える。

頂点 $1$ と葉は必ず良い頂点なので、良い木の個数だけ存在する。
それ以外の、$i \ge 2, d_i \ge 1$ の頂点について考える。

いま、$v$ の部分木に含まれる頂点集合が $S$ と決まっているとする。
$S$ が $v$ 以上の頂点でのみ構成されていれば、$v$ は良い頂点となれる。

木の頂点数と辺数の関係上、$\displaystyle \sum_{i \in S}d_i = |S|-1$ である必要がある。

$S$ を固定した良い木の個数は、($S$ からできる木の個数) × ($v$ と、$S$ に含まれない頂点からできる木の個数) で分割して求めることができる。
後者において、$v$ は葉の扱いとなる。

     ○                       ○
   ／  ＼                   ／  ＼
  ○    ○  =         ×   ○    ○
 /  \   ｜                /  \   ｜
○  ⓥ  ○     ⓥ        ○  ⓥ  ○
    /\         /\
   ○○       ○○

※図化のため具体的な木の形状を表現したが、
  実際は、それぞれの木での次数条件を満たす全ての個数を考える

両者をケイリーの公式で表すと、

$\displaystyle \frac{(|S|-2)!}{(d_v-1)!\prod_{i \in S, i \neq v}d_i!} \times \frac{(N-|S|+1-2)!}{(d_1-1)!\prod_{i \notin S,i \neq 1}d_i!}$

これを整理すると、分母が綺麗な形になる。

$\displaystyle \frac{(|S|-2)!(N-|S|-1)!d_1d_v}{\prod_i d_i}$

つまり、$S$ の具体的な構成要素に依らず、 $v$ が良い頂点になれる良い木の個数は $S$ のサイズが分かれば計算できることになる。

ただし、辺数の制約（$\displaystyle \sum_{i \in S}d_i = |S|-1$）は満たす必要があるため、この2つを状態に持ったDPでパターン数を数える。

$DP[i,j,k]=$ 大きい方から $i$ 個の頂点を見て、$S$ に $j$ 個採用し、その次数 $d$ の和が $k$ であるパターン数

遷移の過程で、以下のような $S$ について、先ほどの式で1パターン当たりの木の個数を求め、答えに加算していけばよい。

頂点 $i$ を使っている
$j=|S|$ としたとき、$k=j-1$ である

$O(N^3)$ で求められる。

Python3

import numpy as np


def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


n = int(input())
ddd = list(map(int, input().split()))
MOD = 998244353

zero_count = 0
facts, finvs = precompute_factorials(n, MOD)
all_prod = facts[ddd[0] - 1]
for i in range(1, n):
    if ddd[i] > 0:
        all_prod = all_prod * facts[ddd[i]] % MOD
    else:
        zero_count += 1
all_prod_inv = pow(all_prod, MOD - 2, MOD)

# 葉頂点＋根は必ず良い頂点
ans = facts[n - 2] * (zero_count + 1) % MOD

dp = np.zeros((n, n), dtype=np.int64)
dp[0, 0] = 1
for i in range(n - 1):
    d = ddd[-i - 1]

    if d > 0:
        for j in range(d, i + 1):
            if dp[j, j - d] > 0:
                tmp = dp[j, j - d] * d % MOD
                tmp *= facts[j - 1]
                tmp %= MOD
                tmp *= facts[n - j - 2]
                tmp %= MOD
                ans += tmp
                ans %= MOD

        dp[1:, d:] += dp[:-1, :-d]
    else:
        dp[1:, :] += dp[:-1, :]

    dp %= MOD

ans *= all_prod_inv
ans %= MOD
print(ans)

目次

AtCoder Regular Contest 162 D問題メモ

D - Smallest Vertices

問題

解法