きたまさ法

きたまさ法に関する記事です． よすぽさんの記事 を参照して書きました．

問題設定

整数 $d_0,\dots ,d_{k-1}$ と $a_0,\dots ,a_{k-1}$ が与えられている． 漸化式 $a_{n+k}=d_0{a}_n+\cdots +d_{k-1}{a}_{n+k-1}$ で定義される数列の $a_n$ を $O(k^2\log n)$ で求める．

行列

$$A=\left[\begin{array}{cccc}{d}_{k-1}& \cdots & \cdots & d_0\\ 1& & 0& 0\\ & \ddots & & 0\\ 0& & 1& 0\end{array}\right]$$

とすれば，

$$\left[\begin{array}{c}{a}_n\\ ⋮\\ a_{n-k+1}\end{array}\right]=A^{n-k+1}\left[\begin{array}{c}{a}_{k-1}\\ ⋮\\ a_0\end{array}\right]$$

なので，$A^n$ が計算できれば良い．あるいは，$A^n$ の最上行だけでも良い． 計算量が $O(k^2\log n)$ で押さえられて欲しいが， 普通の行列累乗だと$O(k^3\log n)$ になる．

計算

$$ $$ $$ $$ ${\mathit{y}}_i$ たちを行ベクトルとする．$\mathit{d}=[d_{k-1},\dots ,d_0]$ とする． また，$\text{sft}([z_0,\dots ,z_{k-1}])=[z_1,\dots ,z_{k-1},0]$ とする． 計算することによって以下がわかる:

$$\begin{array}{}\text{(1)}& A\left[\begin{array}{c}{\mathit{y}}_1\\ {\mathit{y}}_2\\ ⋮\\ {\mathit{y}}_k\end{array}\right]=\left[\begin{array}{c}\ast \\ {\mathit{y}}_1\\ ⋮\\ {\mathit{y}}_{k-1}\end{array}\right],\left[\begin{array}{c}{\mathit{y}}_1\\ ⋮\\ {\mathit{y}}_k\end{array}\right]A=\left[\begin{array}{c}{y}_{11}\mathit{d}+\text{sft}({\mathit{y}}_1)\\ ⋮\\ y_{k1}\mathit{d}+\text{sft}({\mathit{y}}_k)\end{array}\right]\end{array}$$

したがって，$A^n$ の最下行の行ベクトルを $\mathit{x}(n)$ と書くと，以下が成り立つ:

$$\begin{array}{}\text{(2)}& A^n=\left[\begin{array}{c}\mathit{x}(n+k-1)\\ ⋮\\ \mathit{x}(n)\end{array}\right]\end{array}$$

(1)の右の式より， $\mathit{x}(n)$ の第1成分を $x$ とすると， $$\begin{array}{}\text{(3)}& \mathit{x}(n+1)=x\mathit{d}+\text{sft}(\mathit{x}(n))\end{array}$$ であることが分かる． また，$A^n$ の列ベクトルを ${\mathit{w}}_1^T,\dots ,{\mathit{w}}_k^T$ とし，

$$\left[\begin{array}{c}\mathit{x}(2n+k-1)\\ ⋮\\ \mathit{x}(2n)\end{array}\right]=A^{2n}=(A^n{)}^2=\left[\begin{array}{c}\mathit{x}(n+k-1)\\ ⋮\\ \mathit{x}(n)\end{array}\right]\left[\begin{array}{c}\\ {\mathit{w}}_1^T& \cdots & {\mathit{w}}_k^T\\ \end{array}\right]$$

と書いて，最下行を比較すると，

$$\begin{array}{}\text{(4)}& \mathit{x}(2n)=[\mathit{x}(n)\cdot {\mathit{w}}_1,\dots ,\mathit{x}(n)\cdot {\mathit{w}}_k]\end{array}$$

である．

以上より，次の手順で $a_n$ を計算することができる．

• $a_n=\mathit{x}(n-k+1+k-1)\cdot [a_{k-1},\cdots ,a_0]$ なので，$\mathit{x}(n)$ が求められれば良い．
• $n$ を，「$+1$」 と 「$\times 2$」 で書く．たとえば，$n=18$ なら，$n=((1\times 2\times 2\times 2)+1)\times 2$． この内側から順に $\mathit{x}(n)$ を求めていく．
• $+1$ のときには，(3) を適用する．この計算量は，$O(k)$
• $\times 2$ のときには，まず (3) を $k-1$ 回適用して，$\mathit{x}(n),\dots ,\mathit{x}(n+k-1)$ を求める． すると(2) より $A^n$ が決まるので，(4) の右辺が計算できる．この計算量は，$O(k^2)$