Problem258 メモ

けっこう,(といっても,4,5日前だが)に解いた.

問題文は簡単.

g(k) = 1 if 0 <= k <= 1999

g(k) = g(k-2000) + g(k-1999) if 2000 < k

find g(10^18) (mod 20092010)

普通のFibonacciだったら,簡単ですが.

そう簡単にはいかない.まぁ,それが今回の問題ですか.

Haskellで実装したら,3分位.

C++で実装したら,3秒位.

NTLをつかったら,0.2秒位.

NTLスゲー.

おそらく乗算に,FFT乗算を使っているからだろう.

しかし,最近C++の速さが魅力になってきた.

# Haskellも内部ではFFT乗算使ってる?

More Reading
Newer// Level E
Older// powering