https://smijake3.hatenablog.com/entry/2017/01/02/024712

2017年最初の記事。

Kitamasa法をとりあえず理解できた気がするのでメモ

Kitamasa法は、線形漸化式 ${a_{n+k} = c_0 * a_n + c_1 * a_{n+1} + \ldots + c_{k-1} * c_{n+k-1}}$ が与えられた時に、 ${a_{N}}$ を計算する方法である。
この問題で、 ${a_N}$ を求める場合の一つの方法として、 ${k*k}$ の行列に対して繰り返し二乗法を行い、 ${a_{N} = c'_0 * a_0 + c'_1 * a_1 + \ldots + c'_{k-1} * a_{k-1}}$ となる ${c'_0, c'_1, \ldots, c'_{k-1}}$ を求める方法がある。この場合の計算量は ${O(k^3 \log N)}$ である。
しかし、Kitamasa法だと ${O(k^2 \log N)}$ で計算できる。

Kitamasa法の概要っぽいもの

ここで、 ${a_N = C(N, 0)*a_0 + C(N, 1)*a_1 + \ldots + C(N, k-1)*a_{k-1} = \sum_{i=0}^{k-1} C(N, i)*a_i}$ と定義する。
Kitamasa法は、任意の ${X, Y \ge 0}$ について
${\underline{a_{X+Y} = C(X, 0)*a_Y + C(X, 1)*a_{Y+1} + \ldots + C(X, k-1)*a_{Y+k-1}}}$
が成り立つことを利用する。

${C(n, ) \rightarrow C(n+1, )}$ の計算

まず、 ${C(n, *)}$ と ${C(n+1, *)}$ の関係について計算してみる。

${ \begin{align} a_{n+1} & = & C(n+1, 0)*a_0 + C(n+1, 1)*a_1 + \ldots + C(n+1, k-1)*a_{k-1} \\ & = & C(n, 0)*a_1 + \ldots + C(n, k-2)*a_{k-1} + C(n, k-1) * \underline{a_k} \\ & = & C(n, 0)*a_1 + \ldots + C(n, k-2)*a_{k-1} + C(n, k-1) * \underline{\sum_{i=0}^{k-1} C(k, i) * a_i} \\ & = & \underline{C(n, k-1) * C(k, 0)} * a_0 + \sum_{i=1}^{k-1} \underline{(C(n, i-1) + C(n, k-1) * C(k, i))} * a_i \end{align} }$

このことから、
${ C(n+1, i) = \left\{ \begin{array}{ll} C(n, k-1) * C(k, 0) & (i=0) \\ C(n, i-1) + C(n, k-1) * C(k, i) & (0 < i \le k-1) \end{array} \right. }$
であることがわかる。これは ${O(k)}$ で計算できる。

${C(n, ) \rightarrow C(2n, )}$ の計算

次に、 ${C(n, *)}$ と ${C(2n, *)}$ の関係について計算してみる。

${ \begin{align} a_{2n} & = & C(2n, 0)*a_0 + C(2n, 1)*a_1 + \ldots + C(2n, k-1)*a_{k-1} \\ & = & C(n, 0)*a_n + C(n, 1)*a_{n+1} + \ldots + C(n, k-1)*a_{n+k-1} \\ & = & \sum_{j=0}^{k-1} C(n, j)*a_{n+j} \\ & = & \sum_{j=0}^{k-1} C(n, j) * \sum_{i=0}^{k-1} C(n+j, i)*a_i \\ & = & \sum_{i=0}^{k-1} \underline{\sum_{j=0}^{k-1} C(n, j) * C(n+j, i)} * a_i \\ \end{align} }$

ここから、
${ \begin{align} C(2n, i) = \sum_{j=0}^{k-1} C(n, j) * C(n+j, i) \end{align} }$
であることがわかる。
よって、 ${C(n, *)}$ から ${C(n+1, *), \ldots, C(n+k-1, *)}$ を計算することで ${C(2n, *)}$ が計算できる。これは ${O(k^2)}$ で計算できる。