ABC 226 F - Score of Permutations

• 問題

$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ごとにまとめなくてもすべての分割を試せるらしい。確かに。

---

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

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

ACL Beginner Contest F - Heights and Pairs

• 問題
• AC

$h_i$が互いに異なる場合は$(2N-1)!! = (2N)! / 2^N N!$通りという有名事実がある（後述）。以下、$p_i = (2i-1)!!$とする。

身長$h$の人が$a_h$人いるとする。$i$人の同じ身長を持つ人から$j$ペアを作る場合の数は$\binom{i}{2j}p_j$である。$F(x) = \prod_h \sum_j \binom{a_h}{2j}p_j x^{j}$とすると、$F(x)$の$x^k$の係数$[x^k]F(x)$は$2N$人から身長が同じであるような$k$ペアを作る場合の数に等しい。このとき、残った人、つまり$2(N-k)$人でペアを作る場合の数は$p_{N-k}$通りであり、あとは包除で$\sum_k(-1)^kp_{N-k}([x^k]F(x))$通りと求まる。

$(2N-1)!!$について

$2N$人に$1, 2, ..., 2N$という番号を振ってこの順に並べ、二人ずつ取り除いていくとする。この際、ペアのうちの一人目は必ずその時点で番号が最小の人を選ぶ、としておくと完全な数え上げができる。一人目には$2N-1$通りの人がマッチできて、二人目には$2N-3$通りの人がマッチできて、……となるので二重階乗の記号を使うと$(2N-1)!!$と表せる。

別の考え方もできる。$2N$人を自由な順番で一列に並べて、隣り合う二人をくっつけて$N$ペアを作ることにする。並べ方は$(2N)!$通りあるが、二人組の内の順番は考慮しないので$2^N$で割る必要がある。さらに、$N$ペアの順番も考慮しないので$N!$で割って$(2N)!/(2^N N!)$と求まる。これらは二重階乗の公式も与えている:

$$ (2N-1)!! = \frac{(2N)!}{2^N N!} $$

エイシング プログラミングコンテスト 2020 F - Two Snuke

• 問題

$2(s_1+n_1+u_1+k_1+e_1)+\Delta s + \Delta n + \Delta u + \Delta k + \Delta e \le N$で各変数は非負という条件下で$\Delta s\Delta n\Delta u\Delta k\Delta e$の総和を取る問題。

$d = N - (\Delta s + \Delta n + \Delta u + \Delta k + \Delta e )$とするとき、$\Delta s\Delta n\Delta u\Delta k\Delta e$は$s_1+n_1+u_1+k_1+e_1 \le d/2$の非負整数解の数だけ足される。これは$\binom{\lfloor d/2 \rfloor)+5}{5}$通りだから、求める数は

$$ \sum_{d_1+d_2+d_3+d_4+d_5 + d = N}\binom{\lfloor d/2 \rfloor+5}{5}d_1d_2d_3d_4d_5 $$

に等しい。FPSで考えるなら、$\sum_n nx^n = x/(1-x)^2$を5乗して$\sum_{i} \binom{\lfloor i/2 \rfloor +5}{5}x^{i}$という謎の級数を掛けると、$x^N$の係数が求める数である。後者にBerlekamp-Massey法を適用してみると21次の多項式を分母とする有理式が出てくるので、$x^N$の係数はBostan-Mori法で求まる。

---

そもそも一般に$\lfloor i/2 \rfloor$の多項式を係数にするFPSが有理べき級数になるのかどうかとか、基本的なことがよくわかっていなかった。

与えられたFPS$f(x)$の偶数項、奇数項がそれぞれ有理べき級数$g(x), h(x)$の偶数項、奇数項と一致しているなら、$g$の(0-basedで)偶数項だけ抜き出したもの$(g(x)+g(-x))/2$と$h$の奇数項だけ抜き出したもの$(h(x)-h(-x))/2$を足せば$f(x)$になるので、確かに有理べき級数になる。一般に$\lfloor i/k \rfloor$の多項式を係数とするFPSについても、$1$の$k$乗根を考えれば同じことが言える。

一般化すると、次の性質を満たす$f(x) = \sum_n a_n x^n$は有理べき級数と言える:

$M$個の有理べき級数$f_k(x) = \sum_n b_{k, n}x^n \ (k=0, 1, ..., M-1)$と$N \in \mathbb N$が存在して、$n \ge N$ならば$a_n = b_{n \bmod M, n}$。