Kitamasa法
2017年最初の記事。
Kitamasa法をとりあえず理解できた気がするのでメモ
Kitamasa法は、線形漸化式 が与えられた時に、を計算する方法である。
この問題で、を求める場合の一つの方法として、の行列に対して繰り返し二乗法を行い、となるを求める方法がある。この場合の計算量はである。
しかし、Kitamasa法だとで計算できる。
Kitamasa法の概要っぽいもの
ここで、と定義する。
Kitamasa法は、任意のについて
が成り立つことを利用する。
の計算
まず、との関係について計算してみる。
このことから、
であることがわかる。これは で計算できる。
の計算
次に、との関係について計算してみる。
ここから、
であることがわかる。
よって、からを計算することでが計算できる。これは で計算できる。
これらの関係を利用し、からもしくはを計算していくと、までだいたい 回になり、 を で求めることができる。
Kitamasa法を利用できる問題
- Typical DP Contest - T問題: フィボナッチ
T: フィボナッチ - Typical DP Contest | AtCoder
- ABC009 - D問題: 漸化式
D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder
Pythonの行列計算が遅くてTLEするけど、Kitamasa法を使うと通せる。