2021年11月16日火曜日

ABC 226 F - Score of Permutations

F(M)=F(M) =長さNNの順列で、すべてのサイクルの長さがMMの約数であるようなものの数 f(m)=f(m)=長さNNの順列で、サイクルの長さのLCMがmmであるようなものの数

とするとき、求める数はNNの分割のLCMとして得られるようなすべてのmmについてf(m)mKf(m)m^Kの総和を取ったものに等しい。

F(M)=∑m∣Mf(m)F(M) = \sum_{m | M} f(m)であり、ffはFFのメビウス反転として計算できる。また、NNの分割のLCMの最大値はランダウ関数g(N)g(N)として知られていて、OEISによるとg(50)=180180g(50) = 180180なので、個々のF(M)F(M)を高速に計算できればよさそう。

F(M)F(M)は単純なDPで求まる。dp⁡[x]=1,2,...,N\operatorname{dp}[x] = 1, 2, ..., Nからxx個使って任意個数の長さがMMの約数であるようなサイクルを作る場合の数、とするとき、MMの各約数m(≤N)m ( \le N)について

dp⁡[x+m]+=(m−1)!(N−x−1m−1)dp⁡[x] \operatorname{dp}[x+m] \mathrm{{+}{=}} (m-1)! \binom{N-x-1}{m-1}\operatorname{dp}[x]

と遷移すればよい。(m−1)!(m-1)!は長さmmのサイクルの総数であり、(N−x−1m−1)\binom{N-x-1}{m-1}はまだ使っていないN−xN-x個の数から（完全な数え上げをするために）必ず最小の数は選ぶとして残りのm−1m-1個を自由に選ぶことに対応している。計算量はO((N2+log⁡K)g(N)){O}((N^2 +\log K)g(N))。[1]

また、FPSで考えることもできる。MMの約数だけに限って各長さのサイクルの総数を数えたEGFをDM(x)\mathcal D_M(x)とするとき、DM(x)=∑m∣M(m−1)!xm/m!=∑m∣Mxm/m\mathcal D_M(x)=\sum_{m | M}(m-1)!x^m/m! = \sum_{m|M}x^m/mである。このとき、F(M)=[xN/N!]exp⁡(DM(x))F(M) = [x^N/N!]\exp(\mathcal D_M(x))である。[2] FFTを使うと計算量はO((Nlog⁡N+log⁡K)g(N)){O}((N\log N + \log K) g(N))。

解説を見ると、LCMごとにまとめなくてもすべての分割を試せるらしい。確かに。

  1. 実際には1,2,...,g(N)1, 2, ..., g(N)の約数でNN以下であるものの総数が問題になる。これがo(N2){o}(N^2)であればもっとよい評価ができることになるけれど、よくわからなかった。 ↩︎

  2. 仮に「箱」が区別できる設定だったら単にEGFの掛け算をすればいいので[xn/n!]∑n≥1DM(x)n[x^n/n!]\sum_{n \ge 1}\mathcal D_M(x)^nでよくて、箱の区別を無くすために各項をn!n!で割ると∑n≥1DM(x)n/n!=exp⁡(DM(x))\sum_{n \ge 1}\mathcal D_M(x)^n/n! = \exp(\mathcal D_M(x))になる。 ↩︎

投稿者