質問する

インプット

正解

import sys

n = int(input())
arr = [0 for j in range(1000001)]
arr[0] = 1
arr[1] = 1
arr[2] = 2
for i in range(3, 1000001):
    arr[i] = arr[i - 1] % 1000000009 + arr[i - 2] % 1000000009 + arr[i - 3] % 1000000009
for i in range(n):
    a = int(input())
    print(arr[a] % 1000000009)

説明:

点火式はarr[i-1]+arr[i-2]+arr[i-3]
問題は全部終わりましたが、メモリが超過したので検索してみました.
arr[i-1]を追加すると、%1億0009となり、メモリオーバーフローは発生しません.

ポスト

前の解の1,2,3プラスと差が少ないので、すぐに解けました.
メモリがオーバーしたので10分くらい食べましたが….
職場をよくチェックしましょう.