Problem p03013 (python)

Fixed submission:
#!/usr/bin/env python3

import math
from functools import lru_cache


def ncr(n, r):
    r = min(r, n - r)
    # 桁が小さいときは直接 math.factorial を使ったほうが早い
    if n + r < 4000:
        return math.factorial(n) // math.factorial(n-r) // math.factorial(r)
    if r == 0:
        return 1
    if r == 1:
        return n
    numerator = list(range(n - r + 1, n + 1))
    denominator = list(range(1, r+1))
    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):
        result *= numerator[k]
    return result


# 穴なしで n step 離れている場合の組み合わせ
def no_hole(n):
    count = 0
    m = n // 2
    for i in range(0, m+1):
        count += ncr(n-i, i)
    return count


# 穴なしで n step 離れている場合の組み合わせ(高速化版)
@lru_cache(maxsize=8192)
def no_hole2(n):
    if n <= 5:
        return (1, 1, 2, 3, 5, 8)[n]
    if n % 2:
        h = (n-1) // 2
        m1 = no_hole2(h-1)
        m0 = no_hole2(h)
        return 2 * m1 * m0 + m0 * m0
    else:
        h = n // 2
        m2 = no_hole2(h-2)
        m1 = no_hole2(h-1)
        m0 = no_hole2(h)
        return m1 * m1 + m2 * m0 + m1 * m0


def solv(n, m, a):
    ans = 1
    current_pos = 0
    for pos in a:
        dist = pos - 1 - current_pos
        if dist < 0:
            return 0
        ans *= no_hole2(dist)
        current_pos = pos + 1
    dist = n - current_pos
    ans *= no_hole2(dist)
    return ans


if __name__ == '__main__':

    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    ans = solv(n, m, a)

    P_NUM = 1000000007
    print(ans % P_NUM)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys

P_NUM = 1000000007


def solv(n, m, a):
    comb_m2 = 1
    if 1 in a:
        comb_m1 = 0
    else:
        comb_m1 = 1

    for i in range(2, n+1):
        if i in a:
            comb = 0
        else:
            comb = (comb_m1 + comb_m2) % P_NUM
        
        comb_m1, comb_m2 = comb, comb_m1

    return comb


if __name__ == '__main__':

    n, m = map(int, input().split())
    if m:
        a = set(map(int, sys.stdin))
    else:
        a = set()

    ans = solv(n, m, a)

    print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

from functools import lru_cache


a = {-1}

@lru_cache(maxsize=None)
def near(g):
    d = 99999999
    v = g
    for i in a:
        if abs(g-i) < d:
            d = abs(g-i)
            v = i
    return v


@lru_cache(maxsize=None)
def solv1(n, g):
    if n in a:
        return 0
    if n-g == 0:
        return 1
    if n-g < 0:
        return 0
    count = 0
    if (n-2) not in a:
        count += solv1(n-2, g)
    if (n-1) not in a:
        count += solv1(n-1, g)
    return count


def solv(n, a):
    if n < 100:
        return solv1(n, 0)
    g = near(n // 2)
    if g > 15:
        return solv1(g+1, 0) * solv1(n, g+1)
    else:
        return solv1(g-1, 0) * solv1(n, g-1)


if __name__ == '__main__':

    n, m = map(int, input().split())
    for _ in range(m):
        a.add(int(input()))

    ans = solv(n, a)

    print(ans % 1000000007)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

from functools import lru_cache

a = {-1}


@lru_cache(maxsize=10000)
def solv1(n):
    if n == 0:
        return 1
    if n < 0:
        return 0
    count = 0
    if (n-2) not in a:
        count += solv1(n-2)
    if (n-1) not in a:
        count += solv1(n-1)
    return count


def solv(n):
    m = 10000
    while m < n:
        solv1(m)
        m += 10000
    return solv1(n)


if __name__ == '__main__':

    n, m = map(int, input().split())
    for _ in range(m):
        a.add(int(input()))

    ans = solv(n)

    print(ans % 1000000007)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

from functools import lru_cache

a = {-1}


@lru_cache(maxsize=None)
def solv(n):
    if n == 0:
        return 1
    count = 0
    if (n-2) not in a:
        count += solv(n-2)
    if (n-1) not in a:
        count += solv(n-1)
    return count


if __name__ == '__main__':

    n, m = map(int, input().split())
    for _ in range(m):
        a.add(int(input()))

    ans = solv(n)

    print(ans % 1000000007)