山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.718 行列のできるフィボナッチ数列道場 (1)

問題

No.718 行列のできるフィボナッチ数列道場 (1) - yukicoder

yukicoder contest 196 の問題Cとして出題されたものです。フィボナッチ数列の性質を知っていないと厳しいかもしれません。

フィボナッチ数列

今後のためにフィボナッチ数列の性質をいくつか取り上げます。また、解答につかったもの載せます。

定義

 F_0 = 0

 F_1 = 1

 F_n = F_{n - 1} + F_{n - 2}

性質 ① フィボナッチ数列の総和

 S_n = F_1 + F_2 + \cdots + F_n

 = F_{n + 2} - 1

導出

 F_1 = F_1

 F_2 = F_1 + F_0

 \vdots

 F_n = F_{n - 1} + F_{n - 2}

上記を縦に足していくと、

 S_n = 1 + S_{n - 1} + S_{n - 2}

 S_n = 1 + S_n - F_n + S_{n - 2}

 S_{n - 2} = F_n - 1

 S_{n} = F_{n + 2 } - 1

性質 ② フィボナッチ数列の加法

 F_n = F_m F_{n - m + 1} + F_m F_{n - m}  1 \lt m \lt n

導出

 F_n = F_{n - 1} + F_{n - 2}

 F_n = F_3 F_{n - 2} + F_2 F_{n - 3}

 F_n = F_4 F_{n - 3} + F_3 F_{n - 4}

と表現できるので、

 F_n = F_m F_a + F_{m - 1} F_b

として、 a, b の値を求めると、

 m + a = n + 1

 m - 1 + b = n - 1

より、 a = n - m + 1,  b = n - m

なので、

 F_n = F_m F_{n - m + 1} + F_m F_{n - m}  1 \lt m \lt n

あとは、数学的帰納法を使って証明するだけですが、省略します。参考サイトにその証明が載っていました。

性質③ 隣接するフィボナッチ数の2乗の和

 F_n^2 + F_{n + 1} ^2 = F_{2n + 1}

導出

性質②を用いて、 n
= 2m - 1 とすると、

 F_{2m - 1} = F_{m - 1}^2 + F_m ^ 2

が得られるので、 m = m + 1 とすると、

 F_{2m + 1} = F_m^2 + F_{m + 1}^2

問題の考え方

 T_n = F_1^2 + F_2^2 + \cdots + F_n^2

を求めるにはどうすれば良いのかを考えます。

 T_n = F_{n}F_{n + 1}

となるのを利用しないで解くことを目指します。

ここで、性質②を適用することを考えます。なので、 n が奇数か偶数かで場合分けをする必要があります。項数が偶数個ないと余ってしまいます。

 n = 2m - 1 のとき

 T_{2m - 1} = (F_0^2 + F_1^2) + (F_2^2 + F_3^2) + \cdots (F_{2m - 2}^2 + F_{2m - 1} ^2)

 = F_1 + F_5 + \cdots +F_{4m - 3}

 n = 2m のとき

 T_{2m} = (F_1^2 + F_2^2) + (F_3^2 + F_4^2) + \cdots (F_{2m - 1}^2 + F_{2m } ^2)

 = F_3 + F_7 + \cdots +F_{4m - 1}

上記をどうやって求めるかですか、フィボナッチ数列の偶数項の総和を求めるときに使うような計算を行います。

フィボナッチ数の4つ飛ばしの総和

タイトルの表記が適切かどうかは別にして、次の数列の和を考えます。

 A_n = F_1 + F_5 + \cdots + F_{4m - 3}

 B_n = F_2 + F_6 + \cdots + F_{4m - 2}

 C_n = F_3 + F_7 + \cdots + F_{4m - 1}

 D_n = F_4 + F_8 + \cdots + F_{4m}

ここで、 A_n = T_{2m - 1},  C_n =  T_{2m} となっていることに注意します。

また、ここでは使いませんが性質①から、

 A_n + B_n + C_n + D_n = S_{4m} となっています。

*  A_n について

 F_1 = F_1

 F_5 = F_4 + F_3

 \vdots

 F_{4m - 3} = F_{4m - 4} + F_{4m - 5}

縦に足すと、

 A_n = 1 + (D_n - F_{4m}) + (C_n - F_{4m - 1})

 A_n - C_n - D_n = 1 - F_{4m - 1} - F_{4m}   \cdots (a)

*  B_n について

 F_2 = F_1 + F_0

 F_4 = F_3 + F_2

 \vdots

 F_{4m - 2} = F_{4m - 3} + F_{4m - 4}

縦に足すと

 B_n = A_n + D_n - F_{4m}

 -A_n + B_n - D_n = -F_{4m}   \cdots (b)

*  C_n について

 F_3 = F_2 + F_1

 F_7 = F_6 + F_5

 \vdots

 F_{4m - 1} = F_{4m - 2} + F_{4m - 3}

縦に足すと、

 C_n = B_n + A_n

 -A_n - B_n + C_n = 0   \cdots (c)

*  D_n について

 F_4 = F_3 + F_2

 F_8 = F_7 + F_6

 \vdots

 F_{4m} = F_{4m - 1} + F_{4m - 2}

縦に足すと、

 D_n = C_n + B_n

 -B_n - C_n + D_n = 0   \cdots (d)

連立方程式を解く

方程式 a, b, c, d を行列で表現すると、

 {
\left[
    \begin{array}{rrr}
     1 & 0 & -1 & -1\\
-1 & 1 & 0  & -1\\
-1 & -1 & 1 & 0\\
0 & -1 & -1 & 1
    \end{array}
  \right]
\begin{bmatrix}
A_n\\\ 
B_n\\\
C_n\\\
D_n 
\end{bmatrix}
 = 

\begin{bmatrix}
1 - F_{4m - 1} - F_{4m}\\\ 
- F_{4m}\\\
0\\\
0 
\end{bmatrix}

}

となります。ここで行列 P

{
  P= \left[
    \begin{array}{rrr}
     1 & 0 & -1 & -1\\
-1 & 1 & 0  & -1\\
-1 & -1 & 1 & 0\\
0 & -1 & -1 & 1
    \end{array}
  \right]
}

とすると、 P逆行列は、

{
  P^{-1} = \left[
    \begin{array}{rrr}
      0.2 & -0.6 & -0.2 & -0.4\\ 
-0.4 & 0.2 & -0.6  & -0.2\\
-0.2 & -0.4 & 0.2 & -0.6\\
-0.6 & -0.2 & -0.4 & 0.2
    \end{array}
  \right]
}

となります。

したがって、 A_{n} は、

 A_n = 0.2 - 0.2F_{4m - 1} + 0.4F_{4m}

 = \dfrac{1 - F_{4m - 1} + 2F_{4m}}{5}

となり、 C_{n} は、

 C_n = -0.2 + 0.2F_{4m - 1} + 0.6F_{4m}

 = \dfrac{-1 + F_{4m - 1} + 3F_{4m}}{5}

フィボナッチ数を求める

 F_{4m} {F_{4m - 1}} が知りたいので、どのようにして求めるかですか、普通にfor文を回していたら間に合いません。したがって、二分累乗法を用いてフィボナッチ数を求めます。

フィボナッチ数の漸化式は、

フィボナッチ数 - Wikipedia

から、

{
   \left[
    \begin{array}{cc}
          F_{n+ 1} & F_{n} \\
          F_{n} & F_{n - 1} \\
    \end{array}
  \right]
= 
  \left[
    \begin{array}{rr}
          1 &1 \\
         1 & 0 \\
    \end{array}
  \right] ^n
}

上記より、

{
G
= 
  \left[
    \begin{array}{rr}
          1 &1 \\
         1 & 0 \\
    \end{array}
  \right]
}

とします。したがって、 G^{4m - 1} を二分累乗法で求めることになります。

二分累乗法の考え方

行列を格納するための配列を G_{i} とします。

 G_0 = G

 G_1 = G_0 G_0

 G_2 = G_1 G_1

 \vdots

 G_i = G_{i - 1}G_{i - 1}

のように計算していきます。

例えば、 G^7 を求めたいときは、 7 を2進数で表現すると「111」なので、

 G^7 = G_2 G_1 G_0

となります。したがて、二進数で表現したとき、1が立っている要素を掛けることで、累乗を計算します。詳しくは二分累乗法とか高速二乗法で検索すると良いと思います。

モジュラ逆数

この問題では  \rm{mod} を取る必要があります。ここで、

 d = 1000000007 とします。

二分累乗法で行列の累乗を求めるときは、常に d \rm{mod} を取る必要があります。フィボナッチ数は意外と発散するスピードが速いので、注意が必要です。 N が奇数のとき、先程の議論から  A_n \mod d が答えになります。

 A_n= \dfrac{1 - F_{4m - 1} + 2F_{4m}}{5}

ここで注意が必要なのが、

 F_{4m - 1} F_{4m} が求まっているのではなく、

 F_{4m - 1} \mod d F_{4m - 1} \mod d の値が得られています。

なので、 A_{n} において、

 v =1 - F_{4m - 1} + 2F_{4m} の値は分かりませんが、

 r = v \mod d

の値は分かっています。

ここで、次の計算を考えます。

 \dfrac{a}{b} \mod c

ただし、 a b の倍数です。これがモジュラ逆数に繋がるんですが、調べたばかりなので、あまり理解していません。なので、具体的な数値で考えてみます。

 \dfrac{45}{5} \mod 7

 \dfrac{45}{5} = 13 なので、

 \dfrac{45}{5} \mod 7 = 6

となります。また、

 45 \mod 7 = 2

です。ここで、

 \dfrac{1}{5} \mod 7 は、

 5x - 1 = 7q

を満たす 整数 x, q を求めることで計算できます。

 x = \dfrac{7q + 1}{5}

となるので、 q = 2 q = 7 が候補となります。

 q = 2 のとき、  x = 3であり、

 3 \mod 7 = 3 なので、

 \dfrac{1}{5} \mod 7 = 3 となります。

また、

 q = 7 のとき、  x = 10であり、

 10 \mod 7 = 3

となることに注意します。

よって、

 \dfrac{45}{5} \mod 7

 = 45 \mod 7 \times \dfrac{1}{5} \mod 7

 = 2 \times 3 = 6

 \dfrac{a}{b} \mod c

ここで、 a \mod c b, c は既知であるとします。このとき、

 \dfrac{a}{b} \mod c を求めます。

 bx - 1 = cq を満たす整数 x, q が得られたとすると、

 \dfrac{1}{b} \mod c = x \mod c となります。

どのようにして求めるかですが、 b c が互いに素でなければ  x は存在しません。この問題に関しては x が存在すると仮定して大丈夫だと思います。

 r = c \mod b

とします。

 bx - 1 = cq

 x = \dfrac{cq + 1}{b}

 x = \dfrac{(bk + r)q + 1}{b}  ( c = bk + r)

 x = \dfrac{bkq + rq + 1}{b}

と計算できるので、

 rq + 1 = b

 q = \dfrac{b - 1}{r}

とします。

となります。

 \dfrac{1}{5} \mod d

この問題で知りたい値は、

 \dfrac{1}{5} \mod 1000000007

です。

 d \mod 5 = 2

なので、

 2q + 1 = 5 より  q = 2

となります。

したがって、

 x = \dfrac{2d + 1}{5}

となります。

解答

 N が奇数のとき

 v = (1 - F_{4m - 1} + 2F_{4m}) \mod d

 x = \dfrac{2d + 1}{5}

として、

 vx \mod d

が答えになります。

 N が偶数のとき

 v = (-1 + F_{4m - 1} + 3F_{4m}) \mod d

 x = \dfrac{2d + 1}{5}

として、

 vx \mod d

が答えになります。

感想

 \rm{mod} を使うとき、モジュラ逆数というものを知れて良かったです。なんで自分の方法でWAとなった原因を探すのに非常に苦労しました。原因はモジュラ逆数を無視していたことにあります。

 \dfrac{15}{5} \mod 7 = 3

となりますが、

 \dfrac{15 \mod 7} { 5} = \dfrac{1}{5}

となるのに気が付くまでが大変でした。モジュラ逆数以外の部分はなんとなく計算しているうちに導出できたんですが、そのあとが大変でした。

参考サイト

d.hatena.ne.jp