No.329

$A_{i_1} \rightarrow A_{i_2} \rightarrow \cdots \rightarrow A_{i_n}$ が全射を持つためには, $\min(w_{i_1}, w_{i_2}, \dots, w_{i_n}) = w_{i_n}$ である必要がある.

ワーシャル・フロイド法を改造して $A_i \rightarrow A_j$ の経路のうち途中の $w$ の最小値が最も大きくなるものを求めておく. その上でそれぞれの全射の数を合計する. なお, $A_i \rightarrow A_j$ の全射の数は, これが合成関数かどうかにかかわらず $A_i$ と $A_j$ だけ見ればいい. (入力と出力が一致する関数は同一とみなすため)

$A_i \rightarrow A_j$ ($w_i \geq w_j$) の全射の数は, $A_j$ の要素の並びの組み合わせ数が $w_j!$ 通りであり, $A_i$ の要素を $w_j$ 個のグループに分ける組み合わせの数が第二種スターリング数を使って $S(w_i, w_j)$ 個であるので, この積となる.

$n!$, $S(n, r)$ はあらかじめ計算しておく.