読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

Typical DP Contest T:フィボナッチ

AtCoder

解くのに1年かかった問題です。
Typical DP Contest、通称TDPCと呼ばれるDP限定のAtCoderで開催された過去のコンテストの問題。
TDPCはDPの練習にもってこいだと思います。


- 問題概要

N,Kが与えられ、Kボナッチ数列のN項目を出力せよという問題です。

- 解法

Nの最大が10^9であるためO(N)の一般的なDPはTLE。
Kの最大が10^3であるためO(K^3 \log N)のコンパニオン行列を用いた演算子法もTLE。
O(K^2 \log N)でK項間漸化式のN項目を出力することのできるきたまさ法を使うとACです。
きたまさ法そのまま使うだけなのでアルゴリズムの解説はこちら。

m項間漸化式の高速なアルゴリズム - 競技プログラミングをするんだよ

- ソースコード

http://tdpc.contest.atcoder.jp/submissions/342773
きたまさ法を実装したソースコードはABC#009のD問題のもののほうが綺麗です。