AOJ 0168 Kannondou http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0168
漸化式が問題文に書いてあるのでそれをメモ化して取り出すだけ。