概要

数列 ${a}$ について、隣接 $k$ 項間の漸化式および初期条件（第 $k$ 項までの数列の値）が与えられた時に $a_{n}$ を高速に求める方法。言い換えると、 $a_{n}$ を $a_{0}, a_{2}, \dots a_{k-1}$ で表現する方法。

内容

前提の確認

任意の $m$ について、隣接 $k$ 項間の漸化式が

$\begin{eqnarray} a_{m+k} = \sum_{i=0}^{k-1}c_{i}a_{m+i} \end{eqnarray}$

で与えられているとする。このとき、

$\begin{eqnarray} a_{n} = \sum_{i=0}^{k-1} C(n, i)a_{i} \end{eqnarray}$

となる係数 $C(n, i)$ を、 $C(k, i) (i=0, 1, \dots k-1)$ で表すことが最終的なゴールである。ここで、任意の0以上の整数 $m$ について

$\begin{eqnarray} a_{n+m} = \sum_{i=0}^{k-1} C(n, i)a_{i+m} \ \ \ \ \ (1) \end{eqnarray}$

となることを言及しておく。

(A) $n \rightarrow n+1$ の関係

さて、 $a_{n+1}$ について考えていくと

$\begin{eqnarray} a_{n+1} &=& \sum_{i=0}^{k-1}C(n+1, i)a_{i} \\ &=& \sum_{i=0}^{k-1}C(n, i)a_{i+1} \ \ \ \ \ (1)より \\ &=& \sum_{i=0}^{k-2}C(n, i)a_{i+1} + C(n, k-1)a_{k} \\ &=& \sum_{i=1}^{k-1}C(n, i-1)a_{i} + C(n, k-1)\sum_{i=0}^{k-1}C(k, i)a_{i} \\ &=& C(n, k-1)C(k, 0)a_{0} + \sum_{i=0}^{k-1}\left[ C(N, i-1)+ C(N, k-1)C(k, i) \right]a_{i} \\ \end{eqnarray}$

となるから、

$\begin{eqnarray} C(n+1, 0) &=& C(n, k-1)C(k, 0) \\ C(n+1, i) &=& C(n, k-1)C(k, i) \ \ \ (i>0) \end{eqnarray}$

という関係式を導くことができた。

(B) $n \rightarrow 2n$ の関係

次に $a_{2n}$ について考えてみると

$\begin{eqnarray} a_{2n} &=& \sum_{j=0}^{k-1} C(2n, j)a_{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} \left[ \sum_{j=0}^{k-1} C(n, j) C(n+j, i) \right] a_{i} \\ \end{eqnarray}$

となるから

$\begin{eqnarray} C(2n, i) = \sum_{j=0}^{k-1}C(n, j)C(n+j, i) \end{eqnarray}$

という関係式を導くことができた。

解法

(A)と(B)の漸化式を使い、 $C(2n, i) (i=0. 1, k-1)$ を $C(k, j) (j=0, 1, k-1)$ で表すために、以下のようなステップで $\mathcal{O})(\log n)$ の計算量で求めることができる。ここで、基本的には現在の値が奇数の時は(A)、偶数の場合は(B)を使って遷移させることになるが、値が $2k$ を下回った場合は常に(A)を使って遷移させることに注意。

f:id:salpik:20220414225242p:plain — $k=100$ 、 $n=819$ の場合の遷移の例

計算量

(A)の1回あたりの計算量は $\mathcal{O}(k)$ であり、(B)の1回あたりの計算量は $\mathcal{O}(k^{2})$ である。 $n$ から $k$ まで減らしていくステップで、(A)は $\mathcal{O}(k + \log n)$ 回、(B)は $\mathcal{O}(\log n)$ 回なので、合わせて $\mathcal{O}(k(k+\log n) + k^{2}\log n) = \mathcal{O}(k^{2}\log n)$ である。