$F(M) =$長さ$N$の順列で、すべてのサイクルの長さが$M$の約数であるようなものの数 $f(m)=$長さ$N$の順列で、サイクルの長さのLCMが$m$であるようなものの数
とするとき、求める数は$N$の分割のLCMとして得られるようなすべての$m$について$f(m)m^K$の総和を取ったものに等しい。
$F(M) = \sum_{m | M} f(m)$であり、$f$は$F$のメビウス反転として計算できる。また、$N$の分割のLCMの最大値はランダウ関数$g(N)$として知られていて、OEISによると$g(50) = 180180$なので、個々の$F(M)$を高速に計算できればよさそう。
$F(M)$は単純なDPで求まる。$\operatorname{dp}[x] = 1, 2, ..., N$から$x$個使って任意個数の長さが$M$の約数であるようなサイクルを作る場合の数、とするとき、$M$の各約数$m ( \le N)$について
$$ \operatorname{dp}[x+m] \mathrm{{+}{=}} (m-1)! \binom{N-x-1}{m-1}\operatorname{dp}[x] $$と遷移すればよい。$(m-1)!$は長さ$m$のサイクルの総数であり、$\binom{N-x-1}{m-1}$はまだ使っていない$N-x$個の数から（完全な数え上げをするために）必ず最小の数は選ぶとして残りの$m-1$個を自由に選ぶことに対応している。計算量は${O}((N^2 +\log K)g(N))$。[1]
また、FPSで考えることもできる。$M$の約数だけに限って各長さのサイクルの総数を数えたEGFを$\mathcal D_M(x)$とするとき、$\mathcal D_M(x)=\sum_{m | M}(m-1)!x^m/m! = \sum_{m|M}x^m/m$である。このとき、$F(M) = [x^N/N!]\exp(\mathcal D_M(x))$である。[2] FFTを使うと計算量は${O}((N\log N + \log K) g(N))$。
解説を見ると、LCMごとにまとめなくてもすべての分割を試せるらしい。確かに。
