I - Small Steps 解説
by 
ripity
以下のように場合分けをします．
- \(K = 1\) の場合
- \(K\ge 2, N = 1\) の場合
- \(K\ge 2, N = 2\) の場合
- \(K\ge 2, N\ge 3\) かつ \(T_0\) がスターである場合
- \(K\ge 2, N\ge 3\) かつ \(T_0\) がスターでない場合
\(K = 1\) の場合
\(f(T)\) の性質を調べ，\(f(T_0)\) を求めることにします．
ある頂点 \(v\) が存在し，\(T\) から \(v\) を削除して孤立点でない連結成分が \(3\) 個以上できたとします． このとき，\(f(T) = 0\) となることが示せます．
$T_0$ を，$v$ を根とする根付き木として考えます．
仮定より $v$ の子であって葉でない頂点が $3$ 個以上存在します．
これらを $c_1, c_2, c_3, \cdots$ とおきます．
一般性を失わず $p_1 = v$ と固定します．
また，$v$ の子であって葉でない頂点が $c_1, c_2, c_3, \cdots$ の順で現れるとします．
$p_2$ が $c_1$ のとき：
$p_3$ としてあり得るのは $c_1$ 以外の $v$ の子か $c_1$ の子孫であり，どちらの候補も少なくとも $1$ 通り存在します．
ところで，$c_1$ 以外の $v$ の子と $c_1$ の子孫の距離は $3$ 以上です．
よっていずれも不適です．
$p_2$ が $c_1$ の子のとき：
$c_1$ が現れる index を $k$ とおきます．
このとき，$c_1$ の部分木にない $v$ 以外の頂点が始めて現れる index は $k + 1$ であるとしてよいです (そうでない場合は先ほどのケースに帰着されます)．
特に $p_{k + 1}$ は $v$ の子です．
$p_{k + 1}$ が葉である場合は $p_{k + 2}$ も $v$ の子となるので，$c_1, c_2, \cdots$ の現れる順番から $p_{k + 1} = c_2$ と考えてよいです．
あとは $(c_2, c_3)\mapsto (c_1, c_2)$ と変換すると先ほどのケースに帰着されます．
どちらでもないとき：
$p_2$ は葉です．
同様に $p_3 = c_1$ として最初のケースに帰着されます．
証明
そうでない木を素晴らしい木と呼ぶことにします． 素晴らしい木 \(T\) はパスグラフにいくつかの葉を接続したような構造になっています． \(T\) から葉を削除して残った頂点を \(a_1, \cdots, a_D\) とおき，\(a_i\) と \(a_{i + 1}\) は隣接しているとします． また，頂点 \(v\) に隣接する葉の個数を \(L_v\) とおきます．
\(a_1, \cdots, a_i\) およびこれらに隣接する葉からなる部分誘導グラフを \(t_i\)，\(f(t_i)\) で数える順列のうち \(p_1 = a_i\) かつ \(p_1\) と \(p_n\) の距離が \(1\) であるものの個数を \(dp[i]\) とします． まず，明らかに \(dp[1] = L_{a_1}!\) です． さらに，\(dp[i]\ (i\ge 2)\) で数える順列は \((a_i), (dp[i - 1]\) で数えた順列の逆順\(), (a_i\) に隣接する葉の列\()\) をこの順に連結したもののみです (これは先ほどの証明と同様に示せます)． ここで葉の並べ方に自由度があり，\(dp[i] = L_{a_i}!\times dp[i - 1]\) と遷移することが分かります． したがって，\(dp[D] = \prod_{1\le i\le D}L_{a_i}!\) が得られます．
\(T\) がスターでないとき (つまり \(D\ge 2\) のとき)，\(p_1 = a_D\) と \(p_N\) の距離が \(2\) であるものも考慮する必要がありますが，同様の考察から，このような順列は \((a_D), (a_D\) に隣接する葉の列\(), (dp[D - 1]\) で数えた順列\()\) をこの順に連結したものに限ってよいです． よって，\(L_{a_D}! \times dp[D - 1] = \prod_{1\le i\le D}L_{a_i}!\) 個あります．
あとは \(p\) の対称性に注意して \(N\) をかけることで，以下が得られます．
- \(T\) が素晴らしい木でないとき，\(f(T) = 0\)
- \(T\) が素晴らしい木であり \(D = 1\) のとき，\(f(T) = N!\)
- \(T\) が素晴らしい木であり \(D\ge 2\) のとき，\(f(T) = 2N \prod_{1\le v\le N} L_v!\)
特に，\(f(T_0) = 0\) のとき，\(K\) の値に関わらず答えは \(0\) となります． 以下では \(f(T_0)\neq 0\) を仮定します．
\(K\ge 2, N = 1\) の場合
答えは \(K!\times K\times 2 ^ {K - 3}\) です． 積の和典型に帰着して適切に計算すると導くことができます．
$K = 2, 3$ は簡単です．
以下，$K\ge 4$ とします．
以下の問題 $(x, y)$ の答えを $g(x, y)$ とおきます．
ただし，$x\le 0$ または $y\lt 0$ のとき $g(x, y) = 0$ とします．
問題 \((x, y)\) 区別できる箱が \(x\) 個，区別できるボールが \(y\) 個あり，すべてのボールをどこかの箱に入れる．
このとき，箱 \(i\) に入ったボールの個数を \(z_i\) として，\(\prod_{1\le i\le x} z_i!\) をスコアとして得る．すべての入れ方に対するスコアの総和はいくつか？
積の和典型を適用します．
スコアを「『箱の中のボールを一列に並べる通り数』の総積」と言い換えます．
いま，箱ごとにボールを並べた後，箱 $1$ から順にボールの列を連結して $Y$ という列を得たとします．
$Y$ に $x - 1$ 個の仕切りを入れることを考えると，$Y$ を得るような入れ方は $\binom{x + y - 1}{x - 1}$ 通りあります．
$Y$ は $y!$ 通り存在するので $g(x, y) = y!\times \binom{x + y - 1}{x - 1}$ が分かります．
問題 $(x, y)$ において，箱 $1$ と箱 $x$ に $1$ 個以上のボールが必要な場合の答えを $g'(x, y)$ とします．
これは，$\{$箱 $1,$ 箱 $x\}$ の部分集合にボールを入れない，という制約に包徐原理を適用して $g'(x, y) = g(x, y) - 2g(x - 1, y) + g(x - 2, y)$ と求められます．
素晴らしい木のみを考えます．
$D = 1$ となる $T$ について，$f(T)$ の総和は $K\times K!$ です．
$2\le D\le K - 2$ となる $T$ について，$a_1, \cdots, a_D$ の決め方が ${}_K\mathrm{P}_{D} / 2$ 通り，$a_1, \cdots, a_D$ を固定したときの $f(T)$ の総和が $2K\times g'(D, K - D)$ であるので，$D$ を固定したときの $f(T)$ の総和は ${}_K\mathrm{P}_{D}\times K\times g'(D, K - D)$ です．
ここで，
\[\displaystyle
\begin{aligned}
\sum_{2\le D\le K - 2} {}_K\mathrm{P}_{D}\times K\times g'(D, K - D)
&= \sum_{2\le D\le K - 2} \frac{K!}{(K - D)!}\times K\times (K - D)!\times \left(\binom{K - 1}{D - 1} - 2\binom{K - 2}{D - 2} + \binom{K - 3}{D - 3}\right) \\
&= K!\times K\times \left(\sum_{2\le D\le K - 2}\binom{K - 1}{D - 1} - 2\sum_{2\le D\le K - 2}\binom{K - 2}{D - 2} + \sum_{2\le D\le K - 2}\binom{K - 3}{D - 3}\right) \\
&= K!\times K\times ([2 ^ {K - 1} - (K - 1) - 2] - 2\times[2 ^ {K - 2} - (K - 2) - 1] + [2 ^ {K - 3} - (K - 3) - 1]) \\
&= K!\times K\times (2 ^ {K - 3} - 1)
\end{aligned}\]
であるため，答えは $K!\times K\times 2 ^ {K - 3}$ です．
計算の詳細
\(K\ge 2, N = 2\) の場合
\(f(T)\) の性質より，素晴らしい木の寄与だけを考えてよいです． なので \(T_0\) のつなぎ方は一直線であるものだけを考えます． 反転して同じになるものを考慮して，\(T_0\) を一列に並べる方法は \(K!/2\) 通り，並べ方を固定したときのつなぎ方は \(4 ^ {K - 1}\) 通りあります．
また，このようなつなぎ方をした \(T\) に対し，\(0\le L_{a_i}\le 1\) より，\(f(T) = 4K\) です．したがって，答えは \(K!\times K\times 2 ^ {2K - 1}\) です．
\(K\ge 2, N\ge 3\) かつ \(T_0\) がスターである場合
同様に並べ方を固定し，左から順につないでいくことを考えます． 簡単のため，頂点番号の昇順に並べておきます．
隣り合う \(T_0\) をつなぐとき，どこかの葉で両隣の \(T_0\) をつなぐと \(T\) は素晴らしい木ではなくなります． 逆にそうでないときは素晴らしい木になります．
\(dp[i][j] =\) 左から \(i\) 番目の \(T_0\) を \(a_1\) でつないだ \((j = 0)\) / \(a_1\) に隣接する葉でつないだ \((j = 1)\) ときの \(\prod_{1\le v\le Ni}L_v!\) の総和，とします． 葉でつなぐか否かの \(4\) パターンを考えることで，\(i\ge 3\) に対し，以下のように遷移することが分かります．
\(\displaystyle \begin{aligned} dp[i][0] &= \left(dp[i - 1][0]\times \left(\left(1\times 1\times 1\times 1\right) + \left(\frac{1}{N - 1}\times 1\times (N - 1)\times 1\right)\right) + dp[i - 1][1]\times \left(\left(1\times 1\times 1\times 1\right) + \left(\frac{1}{N - 2}\times 1\times (N - 2)\times 1\right)\right)\right)\times (N - 1)! \\ &= (N - 1)!\times 2\times (dp[i - 1][0] + dp[i - 1][1]) \end{aligned}\)
\(\displaystyle \begin{aligned} dp[i][1] &= \left(dp[i - 1][0]\times \left(\left(1\times 1\times 1\times 1\right) + \left(\frac{1}{N - 1}\times 1\times (N - 1)\times 1\right)\right) + dp[i - 1][1]\times \left(\left(1\times 1\times 1\times 1\right) + \left(\frac{1}{N - 2}\times 1\times (N - 2)\times 1\right)\right)\right)\times (N - 2)! \times (N - 1) \\ &= (N - 1)!\times 2\times (dp[i - 1][0] + dp[i - 1][1]) \end{aligned}\)
また，同様に \(4\) パターンを考えると初期値は \(dp[2][0] = dp[2][1] = 2\times ((N - 1)!) ^ {2}\) なので，\(dp[K][0] = dp[K][1] = (N - 1)!\times 2\times ((N - 1)!) ^ {K - 1}\times 4 ^ {K - 2}\) です．
したがって，答えは \((K! / 2)\times 2NK\times (dp[K][0] + dp[K][1]) = K! \times NK\times ((N - 1)!) ^ {K}\times 4 ^ {K - 1}\) です．
\(K\ge 2, N\ge 3\) かつ \(T_0\) がスターでない場合
\(P = \prod_{1\le v\le N}L_v!\) とします． また，上と同じく頂点番号の昇順に並べておきます．
\(T\) を素晴らしい木にするにあたって，\(T_0\) をつなぐ際に使ってよい頂点は，\(a_1, a_D\) およびそれに隣接する葉のみです． \(T_0\) がスターである場合と異なり，どの頂点も \(T_0\) をつなげることに \(2\) 回以上使うことはできないことに注意します． さらに，\(T_0\) をつなぐ際に \(a_1\) とそれに隣接する葉を同時に使用することは，禁止してよいです． これは \(a_D\) についても同じです．
\(dp[i][j] =\) 左から \(i\) 番目の \(T_0\) を \(a_1\) または \(a_1\) に隣接する葉でつないだ \((j = 0)\) / \(a_D\) または \(a_D\) に隣接する葉でつないだ \((j = 1)\) 場合の \(\prod_{1\le v\le Ni}L_v!\) の総和，とします． 同様に場合分けを行うと，遷移は \(dp[i][0] = dp[i][1] = 4P\times dp[i - 1][0] + 4P\times dp[i - 1][1]\) となることが分かります．
詳細は省きますが，各項に \(\displaystyle \left(\left(1\times P\times 1\times 1\right) + \left(\frac{1}{L_{a_D}}\times P\times L_{a_D}\times 1\right)+ \left(1\times \frac{P}{L_{a_1}}\times 1\times L_{a_1}\right) + \left(\frac{1}{L_{a_D}}\times \frac{P}{L_{a_1}}\times L_{a_D}\times L_{a_1}\right)\right)\ (=4P)\) のような係数が付くことが分かれば上の遷移が導出できます．
初期値は \(dp[2][0] = dp[2][1] = 8\times P ^ {2}\) なので，答えは \((K! / 2)\times 2NK\times (dp[K][0] + dp[K][1]) = K!\times NK\times 2\times 8 ^ {K - 1}\times P ^ {K}\) です．
以上より，階乗を前計算しておけば 1 ケースあたり \(O(N + \log K)\) 時間で解けます． 実装例 (c++)
投稿日時:
最終更新: