競技プログラミングにおけるフィボナッチ数列問題まとめ

フィボナッチ数列にまつわるテク

フィボナッチ数列に関する全般的な話題

• 【テク1】行列累乗でフィボナッチ数列の任意の項を高速に求めるテク
  • 参考1 参考2
  • フィボナッチ数列の行列部分の逆元を使いたい(Baby-Step Giant-Step)ときは、こっちの更新式を使おう (全部こっちの方がいい？)
• 【テク2】フィボナッチ数列 mod nの時の周期性を使う
  • 「ｐ＝±１（ｍｏｄ５）のとき，ｆ（ｐ）＝ｐ－１」「ｐ＝±２（ｍｏｄ５）のとき，ｆ（ｐ）＝２ｐ＋２」（pは奇素数、f(p)はmod pとする時の周期）出典
  • Pisano periodというのもある
  • 周期は6*n以下に抑えられるらしい
• 【テク3】初項が異なるフィボナッチ数列
  • 「初項、第2項がa,bのフィボナッチ数列の第n項は基本のフィボナッチ数列をfib[n]としてa*fib[n-1]+b*fib[n-2]とO(1)で求められる」出典
• 【テク4】任意の自然数はフィボナッチ数列の和として表現できる
  • ゼッケンドルフの定理
  • 取れる最大のフィボナッチ数を取ってくる貪欲法で構築可能
  • https://docs.google.com/document/d/17PNPPleixm-uZLyP-Sh0H45L3mrB6XyoEGMThun07JQ/edit

問題

• yukicoder No.526 フィボナッチ数列の第N項をMで割った余りを求める
• yukicoder No.534 フィボナッチフィボナッチ数 解説
• HR Recurrent on a Tree 行列のまま分配法則などを使う面白い問題
• CSA Fibonacci Mod
• yukicoder No.658 テトラナッチ数列 Hard 解説【テク2】
• yukicoder No.718 行列のできるフィボナッチ数列道場 (1) 解説