読者です 読者をやめる 読者になる 読者になる

Ad Infinitum 15

母関数成分を補足.

1. K-element Sequences

概要

$N = x_1 + x_2 + ... + x_K$ と分解する場合の数を答えよ.$x_i$ は正の整数.

解説

求める値は,
$$
[x^N]\left(\frac{x}{1-x}\right)^K = [x^{N-K}]\frac{1}{(1-x)^K} = \binom{K - 1 + N - K}{K - 1} = \binom{N - 1}{K - 1}
$$
となる.

7. Box Hopping

概要

$\mathfrak{S}_n$ の要素のうち,最大のサイクルが $k$ 以下となるようなものの個数を $c_{k,n}$ とする.$p_{K,N} := \frac{c_{K,N}}{N!}$ を求めよ.

解説

$p_{k,n}$ の $n$ に関する母関数 (ogf) を $P_k(x)$ とすると
$$
P_k(x) = \exp{
\left(\sum_{i=1}^{k}\frac{x^i}{i}\right)
}
$$
が成り立ち,求める確率は $[x^N]P_K(x)$ で得られる.

両辺の $\log$ をとって,微分すると,
$$
\begin{align*}
P_k'(x) &= \frac{1-x^k}{1-x} P_k(x)\\
(1-x)P_k'(x) &= (1-x^k) P_k(x)
\end{align*}
$$
となる.ここで $[x^n]$ に着目すると,$n \ge k$ について,
$$
\begin{align*}
(n+1)p_{k,n+1} - n p_{k,n} &= p_{k,n} - p_{k,n-k} \\
p_{k,n+1} &= p_{k,n} - \frac{p_{k,n-k}}{n+1}
\end{align*}
$$
なる関係式が得られる.$n \le k$ に関しては $p_{k,n} = 1$ である.

補足

一般に $g(x) = \exp{(f(x))}$ が成り立っているとき,$f'(x)$ が項数の少ない有理関数でかけるならば,$g_n$ は簡単な漸化式で書くことができる.

8. Multipoint Evaluation

概要

$n-1$ 次元の関数 $f(x)$ が与えられる.特殊な $x_i$ ($0 \le i < n$) について,$f(x_0)$, $f(x_1)$, ..., $f(x_{n-1})$ を求めよ.$n \le 60000$.

解説

$n = 60000$, mod $10^6 + 3$ の条件では,多項式乗算は 64 bit NTT 1 回で処理できるので,multipoint evaluation をそのまま実装して通した.最悪実行時間は 1.5 秒程度.