今回の問題はおおよそ三重対角行列の累乗がテーマである。すなわち、以下の問題である。

\(N \times N\) の三重対角行列

\[ T = \left( \begin{array}{ccccc} b_0 & u_0 \\ l_0 & b_1 & u_1 \\ & l_1 & b_2 & \ddots \\ & & \ddots & \ddots & u_{N-2} \\ & & & l_{N-2} & b_{N-1} \\ \end{array} \right) \]

および非負整数 \(k\) が与えられる。\(e_0 = (1,0,\dots,0)^{\mathrm{T}}\) とするとき、

\[w = T^k e_0\]

を満たすベクトル \(w\) を計算せよ。

この問題は \(\mathrm{O}(N \log^2 N + N \log N \log k)\) で解くことが出来る。解法を簡単に記す。

行列 \(I - z T\) を考える。求めたいものは \(i=0,1,\dots,N-1\) における

\[[z^k]\left( (I-zT)^{-1}\right)_{i,0}\]

である点に注意する。

\(I - zT\) の trailing principal minor (右下の正方形部分の行列式) を考える。より明確には、\(I-zT\) の右下 \(i \times i\) の小行列式を \(D_{N-i}(z)\) と定義する。これは漸化式を立てることが出来て、便宜上

\[D_N(z) = 1, D_{N+1}(z) = 0\]

と置くと

\[D_i(z) = (1 - b_i z) D_{i+1} (z) - l_i u_i z^2 D_{i+2} (z)\]

となる。(ここで \(l_{N-1} = u_{N-1} = 0\) と置いた。)

すると、実は \(D_i(z)\) を用いて \(\left( (I-zT)^{-1}\right)_{i,0}\) を表すことができる。すなわち、

\[\det(I - zT) = D_0(z)\]

であり、これと余因子行列の性質から

\[\left( (I-zT)^{-1}\right)_{i,0} = \frac{\left(\prod_{j=0}^{i-1} l_0 z\right) D_{i+1}(z)}{D_0(z)}\]

が得られるためである。

以上の式から、俗に「必要な所だけ持つ分割統治」、あるいは転置原理を用いた導出が可能なアルゴリズムであることから「転置」と呼ばれている特殊な分割統治により答えを計算できる。(詳しくは maspy さんの記事 などを参照されたし) 簡潔に記すと、

\[M_i = \left( \begin{array}{cc} 1-b_i z & -l_i u_i z^2 \\ 1 & 0 \end{array} \right) \]

と置くと

\[ \left( \begin{array}{cc} D_i \\ D_{i+1} \end{array} \right) = M_i M_{i+1} \dots M_{N-1} \left( \begin{array}{cc} 1 \\ 0 \end{array} \right) \]

となるので \(D_0(z)\) を計算できて、あとは Bostan-Mori の転置により \(\frac{1}{D_0(z)}\) の \(k-2N\) 次から \(k\) 次までの係数を求めて分割統治をすればよい。

なお、想定解はこのアルゴリズムの転置であると解釈できる。詳しく説明すると、想定解は

• input : ベクトル \(a\)
• output : 値 \(x = a^{\mathrm{T}} T^k e_0\)

を計算している。このアルゴリズムを転置すると

• input : 値 \(x\)
• output : ベクトル \(a = x T^k e_0\)

となり、\(x=1\) を代入すればこの記事で扱う問題と一致する。実際、登場する行列が似ており、想定解の行列積・Bostan-Mori がこの記事の特殊な分割統治・Bostan-Mori の転置とキレイに対応している。