日々drdrする人のメモ

今日も明日もdrdr

Kitamasa法

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)} で計算できる。



これらの関係を利用し、 {C(n, *)}から {C(n+1, *)}もしくは {C(2n, *)}を計算していくと、 {C(N, *)}までだいたい  {(\log N)} 回になり、  {a_N} {O(k^2 \log N)} で求めることができる。

Kitamasa法を利用できる問題

  • Typical DP Contest - T問題: フィボナッチ

T: フィボナッチ - Typical DP Contest | AtCoder

  • ABC009 - D問題: 漸化式

D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder
Pythonの行列計算が遅くてTLEするけど、Kitamasa法を使うと通せる。