うーん、ちょっとわかりにくい書き方だったかな
実行時間のオーダーじゃなくて演算回数のオーダーって書いてあるのがミソね
何か多倍長整数のライブラリがあって、それを使ってよいとするわけ

自分の想定解は、
- O(N): DP、メモ付き再帰
- O(log N):
　　- 行列の掛け算に落として行列のN乗をlog(N)ステップで求める
　　- 一般項から直接計算（a+b√5 の形の数の計算が必要、一般項にN乗が入ってるので演算回数はO(log N)）

ちなみに、時間計算量は多倍長整数の演算のオーダーを考えにいれる必要があってめんどい
前者はNビットの数の足し算しか起こらないので O(N^2)-time,
後者は多倍長整数の乗算のオーダーに依存するが
O(N^1.585 * log N) ないし O(N^1.465 * log N) くらいにはなる