Problem p03674 (python)

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(10**5 + 5)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    pre_idx = 0
    idx = 0
    appeared = [-1] * (N + 1)
    for i, a in enumerate(A):
        if appeared[a] == -1:
            appeared[a] = i
        else:
            pre_idx, idx = appeared[a], i
            break

    """
    dpする前に計算量を見積もる癖はつけた方が良さそう。
    TLEした後に引き返せる時間が残っていない。。。

    問題が「同じ表現を含まない」のネガティブなので、全体から
    表現が被るケースを除くべきでした。
    同じ表現になるのは、２回出てくる数をaとして、aが２回出てくるまでの範囲を見た時に
    aを一回選びかつ2つのaの間の数を全く選ばない時。
    """

    for k in range(1, N + 2):
        if k == 1:
            print(N)
            continue
        rem = (N + 1) - (idx - pre_idx + 1)
        if rem < k - 1:
            print(comb(N + 1, k))
        else:
            print((comb(N + 1, k) - comb(rem, k - 1)) % mod)





if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    pre_idx = 0
    idx = 0
    appeared = [-1] * (N + 1)
    for i, a in enumerate(A):
        if appeared[a] == -1:
            appeared[a] = i
        else:
            pre_idx, idx = appeared[a], i
            break

    # dp[i][j] = (A[:i]まで見た時にj個数字を選んでできる部分列の種類)
    dp = [[0] * (N + 2) for _ in range(N + 2)]
    for i in range(N + 2): dp[i][i] = 1
    for i in range(N + 2): dp[i][0] = 1
    for i in range(1, N + 2):
        if i - 1 != idx:
            for j in range(1, i):
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod
        else:
            for j in range(1, pre_idx + 2):
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] - dp[pre_idx][j - 1]) % mod
            for j in range(pre_idx + 2, i):
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod
    #for i in range(1, N + 2): print("A[:{}] => dp[{}]={}".format(i, i, dp[i]))
    for k in range(1, N + 2):
        print(dp[N + 1][k])

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    pre_idx = 0
    idx = 0
    appeared = [-1] * (N + 1)
    for i, a in enumerate(A):
        if appeared[a] == -1:
            appeared[a] = i
        else:
            pre_idx, idx = appeared[a], i
            break
    print("pre_idx={}, idx={}".format(pre_idx, idx))

    # dp[i][j] = (A[:i]まで見た時にj個数字を選んでできる部分列の種類)
    dp = [[0] * (N + 2) for _ in range(N + 2)]
    for i in range(N + 2): dp[i][i] = 1
    for i in range(N + 2): dp[i][0] = 1
    for i in range(1, N + 2):
        if i - 1 != idx:
            for j in range(1, i):
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod
        else:
            for j in range(1, pre_idx + 2):
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] - dp[pre_idx][j - 1]) % mod
            for j in range(pre_idx + 2, i):
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod
    #for i in range(1, N + 2): print("A[:{}] => dp[{}]={}".format(i, i, dp[i]))
    for k in range(1, N + 2):
        print(dp[N + 1][k])

if __name__ == "__main__":
    main()