Problem p03676 (python)

Fixed submission:
def ncr(n, r):
    return fact[n] * inv_fact[r] * inv_fact[n - r] % div


def find_duplicated(aa):
    appeared = [-1] * (n + 1)
    for i, a in enumerate(aa):
        if appeared[a] >= 0:
            return appeared[a], i
        appeared[a] = i


div = int(1e9 + 7)
n = int(input())
aa = list(map(int, input().split()))

fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, n + 2):
    fact_tmp *= i
    fact_tmp %= div
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, div - 2, div))

i1, i2 = find_duplicated(aa)
outside_n = n + 1 - (i2 - i1 + 1)

for part_n in range(1, n + 2):
    sub = ncr(outside_n, part_n - 1) if outside_n >= part_n - 1 else 0
    print((ncr(n + 1, part_n) - sub) % div)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(100001)


def get_ncr(div):
    cache = {}

    def f(*args):
        if args in cache:
            return cache[args]
        n, r = args
        if r == 0 or n == r:
            cache[args] = 1
            return 1
        cache[args] = (f(n - 1, r) + f(n - 1, r - 1)) % div
        return cache[args]

    return f


def find_duplicated(aa):
    appeared = [-1] * (n + 1)
    for i, a in enumerate(aa):
        if appeared[a] >= 0:
            return appeared[a], i
        appeared[a] = i


n = int(input())
aa = list(map(int, input().split()))
i1, i2 = find_duplicated(aa)
between_n = i2 - i1 + 1
outside_n = n + 1 - between_n
div = int(1e9 + 7)
ncr = get_ncr(div)

for part_n in range(1, n + 2):
    sub = ncr(outside_n, part_n - 1) if outside_n >= part_n - 1 else 0
    print((ncr(n + 1, part_n) - sub) % div)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(100000)


def get_ncr(div):
    cache = {}

    def f(*args):
        if args in cache:
            return cache[args]
        n, r = args
        if r == 0 or n == r:
            cache[args] = 1
            return 1
        cache[args] = (f(n - 1, r) + f(n - 1, r - 1)) % div
        return cache[args]

    return f


def find_duplicated(aa):
    appeared = [-1] * (n + 1)
    for i, a in enumerate(aa):
        if appeared[a] >= 0:
            return appeared[a], i
        appeared[a] = i


n = int(input())
aa = list(map(int, input().split()))
i1, i2 = find_duplicated(aa)
between_n = i2 - i1 + 1
outside_n = n + 1 - between_n
div = int(1e9 + 7)
ncr = get_ncr(div)

for part_n in range(1, n + 2):
    sub = ncr(outside_n, part_n - 1) if outside_n >= part_n - 1 else 0
    print((ncr(n + 1, part_n) - sub) % div)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(100000)


def get_ncr():
    cache = {}

    def f(*args):
        if args in cache:
            return cache[args]
        n, r = args
        if r == 0 or n == r:
            cache[args] = 1
            return 1
        cache[args] = f(n - 1, r) + f(n - 1, r - 1)
        return cache[args]

    return f


def find_duplicated(aa):
    appeared = [-1] * (n + 1)
    for i, a in enumerate(aa):
        if appeared[a] >= 0:
            return appeared[a], i
        appeared[a] = i


n = int(input())
aa = list(map(int, input().split()))
i1, i2 = find_duplicated(aa)
pre_n = i1
mid_n = i2 - i1 + 1
post_n = n + 1 - i2 - 1
ncr = get_ncr()
div = int(1e9 + 7)

for total in range(1, n + 2):
    ans = 0
    for i in range(max(total - pre_n - post_n, 0), min(total, mid_n) + 1):
        if i == 1:
            ic = mid_n - 1
        else:
            ic = ncr(mid_n, i)
        for j in range(max(total - i - post_n, 0), min(total - i, pre_n) + 1):
            k = total - i - j
            ans = (ans + ic * ncr(pre_n, j) * ncr(post_n, k)) % div
    print(ans)

Buggy submission (verdict: Runtime Error):
def get_ncr():
    cache = {}

    def f(*args):
        if args in cache:
            return cache[args]
        n, r = args
        if r == 0 or n == r:
            cache[args] = 1
            return 1
        cache[args] = f(n - 1, r) + f(n - 1, r - 1)
        return cache[args]

    return f


def find_duplicated(aa):
    appeared = [-1] * (n + 1)
    for i, a in enumerate(aa):
        if appeared[a] >= 0:
            return appeared[a], i
        appeared[a] = i


n = int(input())
aa = list(map(int, input().split()))
i1, i2 = find_duplicated(aa)
pre_n = i1
mid_n = i2 - i1 + 1
post_n = n + 1 - i2 - 1
ncr = get_ncr()
div = int(1e9 + 7)

for total in range(1, n + 2):
    ans = 0
    for i in range(max(total - pre_n - post_n, 0), min(total, mid_n) + 1):
        if i == 1:
            ic = mid_n - 1
        else:
            ic = ncr(mid_n, i)
        for j in range(max(total - i - post_n, 0), min(total - i, pre_n) + 1):
            k = total - i - j
            ans = (ans + ic * ncr(pre_n, j) * ncr(post_n, k)) % div
    print(ans)