Problem p03270 (python)

Fixed submission:
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def solve_sub(k, n, p, factorials, invs):
    """Number of patterns where any pair(s) of p pairs appear when n dices are rolled"""
    ret = 0
    fp, ik = factorials[p], invs[k - 1]
    for q in range(1, min(p, n // 2) + 1):
        # tmp1 = factorials[p + q - 1] * invs[q] * invs[p - 1] % MOD
        tmp1 = (fp * invs[q] % MOD) * invs[p - q] % MOD
        tmp2 = (factorials[k + n - 2 * q - 1] * invs[n - 2 * q] % MOD) * ik % MOD
        if q % 2 == 1:
            ret += tmp1 * tmp2
        else:
            ret -= tmp1 * tmp2
        ret %= MOD
    return ret


def solve(k, n):
    if k == 1:
        return [0]
    factorials, invs = prepare(k + n, MOD)
    all_patterns_odd = factorials[k + n - 1] * invs[n] * invs[k - 1] % MOD
    all_patterns_even0 = factorials[k + n - 2] * invs[n] * invs[k - 2] % MOD
    all_patterns_even1 = factorials[k + n - 3] * invs[n - 1] * invs[k - 2] % MOD
    buf = []

    for i in range(2, k + 2):
        pairs = i // 2 - max(0, i - k - 1)
        if i % 2 == 0:
            ans = all_patterns_even0 - solve_sub(k - 1, n, pairs - 1, factorials, invs)
            ans += all_patterns_even1 - solve_sub(k - 1, n - 1, pairs - 1, factorials, invs)
            ans %= MOD
        else:
            ans = (all_patterns_odd - solve_sub(k, n, pairs, factorials, invs)) % MOD
        buf.append(ans)

    return buf


MOD = 998244353
k, n = map(int, input().split())
ans = solve(k, n)
print('\n'.join(map(str, ans)))
print('\n'.join(map(str, ans[-2::-1])))

Buggy submission (verdict: Runtime Error):
def prepare(k, n, MOD):
    def get_factorials(m):
        f = 1
        factorials = [1]
        for m in range(1, m + 1):
            f *= m
            f %= MOD
            factorials.append(f)
        inv = pow(f, MOD - 2, MOD)
        invs = [1] * (m + 1)
        invs[m] = inv
        for m in range(m, 1, -1):
            inv *= m
            inv %= MOD
            invs[m - 1] = inv

        return factorials, invs

    def solve(p):
        """Number of patterns where no pair of p appears when n dices are rolled"""
        if cache[p] > -1:
            return cache[p]

        ret = 0
        fp = factorials[p]
        for q in range(1, min(p, n // 2) + 1):
            tmp1 = (fp * invs[q] % MOD) * invs[p - q] % MOD
            tmp2 = (factorials[k + n - 2 * q - 1] * invs[n - 2 * q] % MOD) * ik % MOD
            if q % 2 == 1:
                ret += tmp1 * tmp2
            else:
                ret -= tmp1 * tmp2
            ret %= MOD

        cache[p] = ret = (all_patterns - ret) % MOD
        return ret

    factorials, invs = get_factorials(k + n)
    ik = invs[k - 1]
    all_patterns = factorials[k + n - 1] * invs[n] * ik % MOD
    cache = [-1] * (k // 2 + 1)

    return solve


MOD = 998244353
k, n = map(int, input().split())
if k == 1:
    print(0)
else:
    solve = prepare(k, n, MOD)
    ans = [solve(i // 2 - max(0, i - k - 1)) for i in range(2, k + 2)]
    print('\n'.join(map(str, ans)))
    print('\n'.join(map(str, ans[-2::-1])))