yukicoder No.1348 Split Tile - かんプリンの学習記録

問題概要

ラベル付き ${N}$ 頂点のパスグラフから頂点を削除していく. 頂点を ${1}$ つ削除するたび連結成分の個数の点数を得る. ${N!}$ 通りの削除の仕方すべての点数の総和を求めよ.

${1\leq N\leq 10^6}$

連結成分の数というのは数えにくい.

パスグラフは木の一種であるのでABC173 F - Intervals on Treeと同様に考えると, 「頂点削除後の残りの頂点の数の総和」から「頂点削除後の残りの辺の数の総和」を引けばよい.

「頂点削除後の残りの頂点の数の総和」は削除の仕方によらず $\frac{N(N-1)}{2}$

「頂点削除後の残りの辺の数の総和」は ${2\leq N}$ のとき各辺の寄与分を考えると, ${1}$ つの辺につき $\sum_{k=0}^{N-2}k×{}_{N-2}{\rm{P}}_{k}×{}_{2}{\rm{C}}_{1}×(N-k-1)!=\frac{N!(N-2)}{3}$

よって答えは ${\displaystyle\frac{N!N(N-1)}{2}-\frac{N!(N-1)(N-2)}{3}=\frac{N!(N-1)(N+4)}{6}}$

これは ${N=1}$ のときも成り立つ.

おもしろかった.