Problem p03674 (python)

Fixed submission:
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n

# O(N)
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second

U = 10 ** 5 + 1
def power_mod(a, n):
    if n == 0:
        return 1
    x = power_mod(a//2)

def make_fact(fact, fact_inv):
    for i in range(1, U + 1):
        fact[i] = (fact[i - 1] * i) % MOD
    fact_inv[U] = pow(fact[U], MOD - 2, MOD)
    for i in range(U, 0, -1):
        fact_inv[i - 1] = (fact_inv[i] * i) % MOD

def comb(n, k):
    if k < 0 or n < k:
        return 0
    x = fact[n]
    x *= fact_inv[k]
    x %= MOD
    x *= fact_inv[n - k]
    x %= MOD
    return x

fact = [1] * (U + 1)
fact_inv = [1] * (U + 1)
make_fact(fact, fact_inv)

for i in range(1, n + 2):
    ans = comb(n + 1, i) - comb(left + right, i - 1)
    print (ans % MOD)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0




N = int(input())
A = list(map(int, input().split()))

lst = [-1] * (N + 1)
for i in range(N):
    a = A[i]
    if lst[a] == -1:
        lst[a] = i
    else:
        left = lst[a]
        right = i
        break
# print (left, right)
F = Factorial(N + 1, MOD).comb

for i in range(1, N + 2):
    if left + N - right >= i - 1:
        tmp = F(N + 1, i) - F(left + (N- right), i - 1)
    else:
        tmp = F(N + 1, i)
    print (tmp % MOD)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0




N = int(input())
A = list(map(int, input().split()))

lst = [-1] * (N + 1)
for i in range(N):
    a = A[i]
    if lst[a] == -1:
        lst[a] = i
    else:
        left = lst[a]
        right = i
        break
# print (left, right)
F = Factorial(N + 1, MOD).comb

for i in range(1, N + 2):
    tmp = F(N + 1, i) - F(left + (N- right), i - 1)
    
    print (tmp % MOD)

Buggy submission (verdict: Runtime Error):
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second
# print (left, right)

left_lst = [1] * (left + 1) 
for i in range(1, left + 1):
    left_lst[i] = (left_lst[i - 1] * (left + 1 - i)) // i
# print (left_lst)

right_lst = [1] * (right + 1)
for i in range(1, right + 1):
    right_lst[i] = (right_lst[i - 1] * (right + 1 - i)) // i
# print (right_lst)


def calc(i): #1を含めてトータルi個選ぶ
    if i == 1:
        return 1
    count = 0
    #左側からl個、右側からr個選ぶ
    start = max((i - 1) - right, 0) #左側から最低限選ばないといけない個数
    for l in range(start, i):
        count += left_lst[l] * right_lst[i - 1 - l]
    return count

N = n + 1
tmp = 1
for i in range(1, n + 2):
    tmp = (tmp * (N + 1 - i))//i
    if left + right < i - 1:
        print (tmp % MOD)
        continue
    print ((tmp - calc(i)) % MOD)

Buggy submission (verdict: Runtime Error):
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second
# print (left, right)

left_lst = [1] * (left + 1) 
for i in range(1, left + 1):
    left_lst[i] = (left_lst[i - 1] * (left + 1 - i)) // i
# print (left_lst)

right_lst = [1] * (right + 1)
for i in range(1, right + 1):
    right_lst[i] = (right_lst[i - 1] * (right + 1 - i)) // i
# print (right_lst)


def calc(i): #1を含めてトータルi個選ぶ
    if i == 1:
        return 1
    count = 0
    #左側からl個、右側からr個選ぶ
    start = max((i - 1) - right, 0) #左側から最低限選ばないといけない個数
    for l in range(start, left + 1):
        count += left_lst[l] * right_lst[i - 1 - l]
    return count



N = n + 1
tmp = 1
for i in range(1, n + 2):
    tmp = (tmp * (N + 1 - i))//i
    if left + right < i - 1:
        print (tmp % MOD)
        continue
    print ((tmp - calc(i)) % MOD)