けっこう，（といっても，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乗算使ってる？