CodeIQ 「ルート・パワー」問題

CodeIQ の @riverplus さん出題の問題。
$\Large (1+\sqrt{2}+\sqrt{3}+\sqrt{5})^n$
の有理数の項を求めよというもの。
他の方のコードが http://togetter.com/li/911507 にある。

$\Large \lambda_1 = 1+\sqrt{2}+\sqrt{3}+\sqrt{5}\\ \lambda_2 = 1+\sqrt{2}+\sqrt{3}-\sqrt{5}\\ \lambda_3 = 1+\sqrt{2}-\sqrt{3}+\sqrt{5}\\ \lambda_4 = 1+\sqrt{2}-\sqrt{3}-\sqrt{5}\\ \lambda_5 = 1-\sqrt{2}+\sqrt{3}+\sqrt{5}\\ \lambda_6 = 1-\sqrt{2}+\sqrt{3}-\sqrt{5}\\ \lambda_7 = 1-\sqrt{2}-\sqrt{3}+\sqrt{5}\\ \lambda_8 = 1-\sqrt{2}-\sqrt{3}-\sqrt{5}$
とすると、求める数 F(n) は
$F(n) = \frac{1}{8} ({\lambda_1}^n + {\lambda_2}^n + {\lambda_3}^n + {\lambda_4}^n + {\lambda_5}^n + {\lambda_6}^n + {\lambda_7}^n + {\lambda_8}^n)$
$\lambda_1 \sim \lambda_8$ を解に持つ方程式
$\Large (x-\lambda_1)(x-\lambda_2)(x-\lambda_3)(x-\lambda_4)(x-\lambda_5)(x-\lambda_6)(x-\lambda_7)(x-\lambda_8)=0$
を頑張って展開すると
$\Large x^8 - 8x^7 - 12x^6 + 184x^5 - 178x^4 - 664x^3 + 580x^2 + 744 x - 71 = 0$
になるから、F(n) は差分方程式
$\Large F(n+8) - 8F(n+7) - 12F(n+6) + 184F(n+5)\\ - 178F(n+4) - 664F(n+3) + 580F(n+2) + 744F(n+1) - 71F(n) = 0$
を満たす。
なので、
$\Large v_n = \begin {pmatrix}F(n)\\F(n+1)\\F(n+2)\\F(n+3)\\F(n+4)\\F(n+5)\\F(n+6)\\F(n+7)\end{pmatrix}$

$\Large A = \begin{pmatrix} & 1 & & & & & & \\ & & 1 & & & & & \\ & & & 1 & & & & \\ & & & & 1 & & & \\ & & & & & 1 & & \\ & & & & & & \;1 & \\ & & & & & & & \;\;1 \\ 71 & -744 & -580 & 664 & 178 & -184 & \;12 & \;\;8 \end{pmatrix}$
とすれば
$\Large v_{n+1} = A v_n$
だから
$\Large v_n = A^n v_0$
$v_0$ は直接計算して
$\Large v_0 = \begin {pmatrix}1\\1\\11\\31\\285\\1221\\9671\\51171\end{pmatrix}$
になる。

下は提出したコードを修正したもの。言語は Ruby。

require 'matrix'

def mod_pow(a, n)
  x = Matrix.I(8)
  loop do
    x = (x * a).map {|y| y % Mod} if n.odd?
    return x if (n >>= 1) == 0
    a = (a ** 2).map {|y| y % Mod}
  end
end

def init_mat
  8.times.map do |i|
    if i < 7 then
      8.times.map {|j| j == i + 1 ? 1 : 0}
    else
      [71, -744, -580, 664, 178, -184, 12, 8]
    end
  end
end

Mod = 10 ** 7
a = Matrix[*init_mat]
v = Vector[1, 1, 11, 31, 285, 1221, 9671, 51171]
p (mod_pow(a, gets.to_i) * v)[0] % Mod