2022-02-24 アルゴリズムと数学 演習問題集 054 - Fibonacci Hard (mod 1000000000) を解いた
アルゴリズムと数学 演習問題集 054 - Fibonacci Hard (mod 1000000000) を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_at
書籍の例題と同じもの。 049 (2022-02-19) と同様にフィボナッチ数列の第 N 項を求める。ただし今度は N <= 10^18 なので前から数えると間に合わない。↓の行列の積を使う。
\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}
この行列の N - 1 乗したときの 2 行目の総和が答えになる。
あとは 050, 053 (2022-02-23) などと同様に繰り返し二乗法で掛け算の回数を減らすことで間に合う。
書籍の n 乗計算のところがよくわからなかったので単位元に置き換えたもので解いた。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29623918
今日のコミット。