AtCoder Beginner Contest 226 F 問題 Score of Permutations

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

${1,2, \dots, N}$ の置換 $P$ に対して, $S(P)$ を以下で定義する.

$P^n=\rm{id}$ (恒等置換) を満たす最小の正の整数 $n$

${1,2, \dots, N}$ の置換 $P$ 全てにおける $S(P)^K$ の総和を求めよ.

制約

$1 \leq N \leq 50$
$1 \leq K \leq 10000$

解法

置換 $P$ に対して, $S(P)$ は $P$ の位数である. ここで, 置換において, 以下の性質がある.

任意の置換は互いに交わらない巡回置換の積に分解できる. しかも, この分解は順番の違いを除いて一意である.
置換 $P$ が互いに交わらないサイズ $k_1, \dots, k_l (k_1+\dots+k_l=N)$ の巡回置換に分解できたとき, 位数は $\operatorname{lcm}(k_1, \dots, k_l)$ である.

互いに交わらないサイズ $k_1, \dots, k_l~(k_1+\dots+k_l=N)$ の巡回置換に分解するような置換の数を求める. このとき, 以下のような手順で計算することになる.

$N$ 要素から, サイズ $k_1$ の巡回置換を生み出す方法は, $\frac{{}_N P_{k_1}}{k_1}=\frac{N!}{k_1 \cdot (N-k_1)!}$ 通りである.
残りの $N-k_1$ 要素から, サイズ $k_2$ の巡回置換を生み出す方法は, $\frac{{}_{N-k_1} P_{k_2}}{k_2}=\frac{(N-k_1)!}{k_2 \cdot (N-k_1-k_2)!}$ 通りである.
$\vdots$
残りの $N-k_1-\dots-k_{l-1}$ 要素から, サイズ $k_l$ の巡回置換を生み出す方法は, $\frac{{}_{N-k_1-\dots-k_{l-1}} P_{k_l}}{k_l}=\frac{N!}{k_l \cdot (N-k_1-k_2-\dots-k_l)!}=\frac{N!}{k_l}$ 通りである.

ここで, サイクルのサイズが同じ場合, 同じサイクルの巡回置換の生み出す順番による重複が存在する. これについては, $k_1, \dots, k_l$ の中に, $r$ が $t_r$ 個あるとき, 重複度は $t_r!$ である.

よって, サイズが互いに交わらないサイズ $k_1, \dots, k_l~(k_1+\dots+k_l=N)$ の巡回置換に分解するような置換の数 $\chi(k_1, \dots, k_l)$ は,

$\displaystyle \frac{N!}{k_1 \cdot (N-k_1)!} \cdot \frac{(N-k_1)!}{k_2 \cdot (N-k_1-k_2)!} \cdot \dots \cdot \frac{N!}{k_l} \cdot \prod_{r=1}^N \frac{1}{t_r!}=\frac{N!}{\left(\prod_{j=1}^l k_j\right) \left(\prod_{i=1}^N t_r! \right)}$