母関数解法

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

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})$ で解くことができる。