ヤマカサのプログラミング勉強日記

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

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

yukicoder 数学

問題

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$ を行列で表現すると、

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

とすると、 $P$ の逆行列は、

となります。

したがって、 $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

から、

上記より、

とします。したがって、 $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}$

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

参考サイト