Problem p03674 (python)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

class ModInv:
    def __init__(self, size, MOD):
        self.inv = [0] * (size + 1)
        self.inv[1] = 1
        for i in range(2, size + 1):
            self.inv[i] = (-(MOD // i) * self.inv[MOD%i]) % MOD

if n == 1:
    print(1)
    print(1)
    exit()

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        break

first = a.index(b[i])
for i in range(first + 1, n + 1):
    if a[i] == a[first]:
        second = i

w = n + first - second

inv = ModInv(n + 1, MOD)
c = [1] * (n + 2)
d = [1] * (n + 2)

for i in range(n + 1):
    d[i + 1] = (d[i] * inv.inv[i + 1]) % MOD
for i in range(n + 1):
    c[i + 1] = (c[i] * (i + 1)) % MOD

print(n)
for k in range(2, n + 2):
    ans = (((c[n+1] * d[n+1-k]) % MOD) * d[k]) % MOD
    if w >= k - 1:
        ans -= (((c[w] * d[w-k+1]) % MOD) * d[k-1]) % MOD
    print( ans % MOD )

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(input().split())

if n == 1:
    print(1)
    print(1)
    exit()

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        d = b[i]
        break

p = []
for i in range(n):
    if a[i] == d:
        p.append(i)

w = p[0] + n - p[1]

c = [0 for _ in range(n + 2)]
d = [0 for _ in range(n + 2)]

L = 1
H = 1
for i in range(1, n + 2):
    L *= i
    H *= n + 2 - i
    c[i] = L
    d[i] = H

e = [0 for _ in range(w + 1)]
temp = 1
for i in range(1, w + 1):
    temp *= w + 1 - i
    e[i] = temp


def ncmb(k):
    return d[k] // c[k]

def wcmb(k):
    if k > w or k <= 0:
        return 0
    elif k == w:
        return 1
    else:
        return e[k] // c[k]

print(n)
for k in range(2, n + 2):
    ans = ncmb(k) - wcmb(k-1)
    print(ans % MOD)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(input().split())

if n == 1:
    print(1)
    print(1)
    exit()

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        d = b[i]
        break

p = []
for i in range(n):
    if a[i] == d:
        p.append(i)

w = p[0] + n - p[1]

c = [0 for _ in range(n + 2)]

temp = 1
for i in range(1, n + 2):
    temp *= i
    c[i] = temp

def cmb(x, y):
    if y < 0 or y > x:
        return 0
    elif x == y:
        return 1
    else:
        return c[x] // c[y] // c[x - y] % MOD


print(n)
for k in range(2, n + 2):
    ans = cmb(n + 1, k) - cmb(w, k - 1)
    print(ans % MOD)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(input().split())

if n == 1:
    print(1)
    print(1)
    exit()

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        d = b[i]
        break

p = []
for i in range(n):
    if a[i] == d:
        p.append(i)

w = p[0] + n - p[1]

c = [0 for _ in range(n + 2)]

temp = 1
for i in range(1, n + 2):
    temp *= i
    c[i] = temp

def cmb(x, y):
    if x == y:
        return 1
    else:
        return c[x] // c[y] // c[x - y]


print(n)
for k in range(2, n + 2):
    if w >= k - 1:
        ans = cmb(n + 1, k) - cmb(w, k - 1)
    else:
        ans = cmb(n + 1, k)
    print(ans % MOD)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(input().split())

if n == 1:
    print(1)
    print(1)
    exit()

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        d = b[i]
        break

p = []
for i in range(n):
    if a[i] == d:
        p.append(i)

x = p[0]
y = p[1] - p[0] - 1
z = n - p[1]
w = x + z

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

print(n)
for k in range(2, n + 2):
    if w >= k - 1:
        ans = cmb(n + 1, k) - cmb(w, k - 1)
    else:
        ans = cmb(n + 1, k)
    print(ans % MOD)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(input().split())

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        d = b[i]
        break

p = []
for i in range(n):
    if a[i] == d:
        p.append(i)

x = p[0]
y = p[1] - p[0] - 1
z = n - p[1]
w = x + z

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

print(n)
for k in range(2, n + 2):
    if w >= k - 1:
        ans = cmb(n + 1, k) - cmb(w, k - 1)
    else:
        ans = cmb(n + 1, k)
    print(ans % MOD)