blog.bouzuya.net

2022-02-25 アルゴリズムと数学 演習問題集 055 - Recurrence Formula 1 を解いた

アルゴリズムと数学 演習問題集 055 - Recurrence Formula 1 を解いた。

問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_au

書籍の例題からの流れがあるので解ける。フィボナッチ数列の第 N 項を行列の累乗で解いた流れで出てきているので同様の解法で良いのだろうとあたりをつける。

フィボナッチ数列との違いは a_{n-1}2 という係数がついている。ひとつ前の数字に 2 がかけられるようにすれば良さそうなので↓のようにする。

\begin{pmatrix}
2 & 1 \\
1 & 0 \\
\end{pmatrix}

あとは 054 (2022-02-24) と同様。ただし mod の値が違う点に注意する。

提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29630307


育児。下の子はお風呂で洗面器を湯船に沈めたあと裏返してのぼる気泡で爆笑していた。


今日のコミット。