母関数解法

母関数を用いて,機械的に解ける問題.

1. Ad Infinitum - Math Programming Contest June'14: Bridges and Harbors

概要

根から高々 $K$ 本しか枝が出ていないようなラベル付き根付き木 $M $ 個により,$N$ 頂点の森を構成する場合の数を求めよ.($1 \le K, M \le 100,\, 1\le N \le 10^9$)

余談

昔 Adinf で解けなかったツラい数え上げ問題.

公式の解説もかなり複雑で無理問にみえるのだけれど,
指数型母関数と Lagrange inversion theorem (Lagrange–Bürmann formula) を知っていると(任意 mod を無視すれば)直接的に解ける.

解法

ラベル付き根付き木の個数の指数型母関数 $T(x)$ は,
$$
T(x) = x e^{T(x)},\, T(x) = \sum_{n=0}\frac{n^{n-1}}{n!}x^n,
$$
を満たす.特に,根から高々 $K$ 本しか枝が出ていないものに限った指数型母関数は,
$$
T_K(x) = x \sum_{n=0}^{K} \frac{T(x)^n}{n!}
$$
と書ける.すると,求める場合の数は,
$$
\left[\frac{x^N}{N!}\right] \frac{T_K(x)^M}{M!}
= \frac{N!}{M!} \left[x^{N-M}\right] \left(\sum_{n=0}^{K} \frac{T(x)^n}{n!}\right)^M
$$
である.ここで,Lagrange–Bürmann formula を用いて $T(x)$ を消去すると,
$$
\begin{align*}
\frac{N!}{M!} \left[x^{N-M}\right] \left(\sum_{n=0}^{K} \frac{T(x)^n}{n!}\right)^M
&= \frac{N!}{M!(N-M)} \left[u^{N-M- 1}\right]
\frac{d}{du}\left(\sum_{n=0}^{K} \frac{u^n}{n!}\right)^M \cdot e^{u(N-M)} \\
&= \frac{N!}{M!(N-M)} \left[u^{N-M- 1}\right]
\frac{d}{du}\left(\sum_{n=0}^{K} \frac{u^n}{n!}\right)^M \cdot \sum_{n=0}^{\infty}\frac{(N-M)^n}{n!}u^n
\end{align*}
$$
となる.$\left[u^{N-M- 1}\right]$ に関係するのは合計 $MK$ 項だけなので,計算量は,$\frac{d}{du}\left(\sum_{n=0}^{K} \frac{u^n}{n!}\right)^M $
の $O(KM^2)$ 依存となる (*).厄介な $N!$, $M!$ は $\sum_{n=0}^{\infty}\frac{(N-M)^n}{n!}u^n$ の部分にまとめると,二項係数に近い形になって消えてくれる.

(*)
$$
f_m(x) := \left(\sum _{n=0}^{k} \frac{x^n}{n!} \right)^m
$$
とおくと,
$$
\begin{align*}
\frac{df_m}{dx} (x) &= m \cdot f_{m -1}(x) \cdot \sum _{n=0}^{k -1} \frac{x^n}{n!} \\
&= m \cdot \left(f_m(x) - \frac{x^k}{k!}f_{m -1}(x)\right)
\end{align*}
$$
が成り立つ.特に,$[x^n]$ に着目すると $n \ge k$ において,
$$
\begin{align*}
(n+1)\frac{f_{m,n+1}}{(n+1)!}&= m \cdot \left(\frac{f_{m,n}}{n!} - \frac{1}{k!} \cdot \frac{f_{m -1, n-k}}{(n-k)!}\right) \\
\frac{f_{m,n+1}}{(n+1)!} &= \frac{m}{n+1} \cdot \left(\frac{f_{m,n}}{n!} - \frac{1}{k!} \cdot \frac{f_{m -1, n-k}}{(n-k)!}\right)
\end{align*}
$$
なる漸化式を得られる.$n \le k$ については,
$$
f_{m,n} = \left[\frac{x^n}{n!}\right]f_m(x) = \left[\frac{x^n}{n!}\right]e^{mx} = m^n
$$
とすればよい.以上により,$f_1(x)$, $\cdots$, $f_{m}(x)$ が $O(km^2)$ で得られる.

2. Ad Infinitum - Math Programming Contest June'14: Permutation Problem

概要

$0$~$9$ の各数字の出現回数が $k$ 回以下であるような,ちょうど $n$ 桁の数の個数を求めよ.
$(1 \le n \le 1000, 1 \le k \le 10^9)$

解説

当時は気が付かなかったけど,実は Bridges and Harbors に出現する関数と全く同じ関数を求めている.

先頭の $0$ を許し,$m $ 個の数字を高々 $k$ 回以下ずつ使って作れる $n$ 桁の数の個数を $c_{m,n}$ とする($k$ は省略).このとき,$c_{m,n}$ の指数型母関数 $C_m(x)$ は,
$$
C_m(x) = \left(\sum _{n=0}^k \frac{x^n}{n!}\right)^m
$$
である.後は前述のように,$C_m(x)$ を求めて,$\frac{9}{10}c_{m,n}$ を出力すればよい.

この問題では,mod ${x^{(n+1)}}$ で計算してよいので,計算量が落ちる.

3. CyclesNumber

概要

$c(N, i)$ を符号なし第 1 種スターリング数とするとき
$$
\sum_{i=1}^N c(N, i)i^M
$$
を求めよ.

解法

$c(N, i)$の母関数 $C_N(x)$ は,
$$
C_N(x) = \prod_{i=0}^{N-1}(x+i) = \sum_{i=1}^N c(N,i) x^i
$$
である.$\left(x\frac{d}{dx}\right)x^n = n x^n$ に注意すると,求めたい値は,
$$
\left.\left(x\frac{d}{dx}\right)^M C_N(x) \right|_{x=1}
$$
となるが,$S(N, M)$ を第 2 種スターリング数とするとき,
$$
\left(x\frac{d}{dx}\right)^M = \sum_{i=0}^{M} S(M, i) x^i \left(\frac{d}{dx}\right)^i
$$
が成立するので.
$$
\left.\left(x\frac{d}{dx}\right)^M C_N(x) \right|_{x=1}
= \sum_{i=0}^{M} S(M, i) C_N^{(i)}(1)
$$
となる.ここで,$f^{(i)}(x)$ は $f(x)$ の $i$ 回微分とする.明らかに,
$$
C_{N}(x+1) = \frac{C_{N+1}(x)}{x} = \sum_{i=0}^N{c(N+1,i+1)x^i}
$$
であるから,
$$
\sum_{i=1}^N c(N, i)i^M = \sum_{i=0}^{M} S(M, i) C_N^{(i)}(1) = \sum_{i=0}^M S(M, i) c(N + 1, i + 1) i!
$$
となる.

4. SPOJ. INS14H - Virus Revisited

概要

$N$ 次元空間の原点から $T$ 回ランダムウォークした際,原点に戻ってこれる場合の数を答えよ.
ランダムウォークは $x_i$ 軸に対して $\pm1$ 進むというもので,合計 $2N$ 通りある.

($Q \le 10000, N \le 100, T \le 200$, mod $10^9+7$)

解法

想定解はおそらく $O(NT^2 + Q)$ で設定されているが,1 テストケースに限れば $O(T\log(T) + \log{N})$ で解ける.

1 次元のランダムウォークで,$n$ 回の移動後に原点にいる場合の数の指数型母関数は,
$$
C(x) = \sum_{n=0} \frac{\binom{2n}{n}}{2n!}x^{2n}
= \sum_{n=0} \frac{1}{(n!)^2}x^{2n}
$$
で与えられる.よって,$N$ 次元のランダムウォークでの指数型母関数は,$C(x)^N$ であり,
もとめる場合の数は
$$
\left[ \frac{x^T}{T!}\right] C(x)^N
$$
である.ここで,$C(0) = 1$ なので,$C(x)^N = e^{(N \log{C(x)})}$ として計算でき,$O(T \log{T})$ で解くことができる.