Problem p03332 (python)

Fixed submission:
N,A,B,K = map(int,input().split())
sprime = 998244353 # approx 10**9
A,B = sorted((A,B))
if (A+B) * N < K:
	print(0)
	exit()
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 
memo = [0] * (N+1)
memo[0] = memo[N] = 1
for i in range(1,N//2+1):
	v = memo[i-1] * (N-i+1) * modinv(i,sprime)
	v = v % sprime
	memo[i] = memo[N-i] = v
 
# max is A*N + B*N
sum = 0
for b in range(N+1):
  a = (K-b*B)//A
  if 0 <= a <= N and a*A+b*B == K:
    sum += memo[a]*memo[b]
    sum %= sprime

print(sum)

Buggy submission (verdict: Runtime Error):
N,A,B,K = map(int,input().split()
sprime = 998244353 # approx 10**9
A,B = sorted((A,B))
if (A+B) * N < K:
	print(0)
	exit()

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

memo = [0] * (N+1)
memo[0] = memo[N] = 1
for i in range(1,N//2+1):
	v = memo[i-1] * (N-i+1) * modinv(i,sprime)
	v = v % sprime
	memo[i] = memo[N-i] = v

# max is A*N + B*N
sum = 0
for j in range(0,N):
	i = (K-B*j)//A
	if 0 <= i <= N and A*i+B*j==K:
		sum += memo[i] * memo[j]
		sum %= sprime

print(sum)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

L = input().split()
sprime = 998244353 # approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

memo = [0] * (N+1)
memo[0] = memo[N] = 1
for i in range(1,N//2+1):
	v = memo[i-1] * (N-i+1) * modinv(i,sprime)
	v = v % sprime
	memo[i] = memo[N-i] = v

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		sum += (memo[i] * memo[j]) % sprime

print(sum)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

L = input().split()
sprime = 998244353 # approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

@lru_cache(maxsize=N)
def factorial(m):
	a = 1
	for i in range(1,m):
		a = (a*i) % sprime
	return a

def binom(m):
	if N == m:
		return 1
	elif m == 1:
		return N
	elif m > N:
		return 0
	else:
		return (factorial(N) * modinv(factorial(m),sprime) * modinv(factorial(N-m),sprime)) % sprime

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		sum += (binom(N,i) * binom(N,j)) % sp

print(sum)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

L = input().split()
sprime = 998244353 # approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

@lru_cache(maxsize=N)
def factorial(m):
	a = 1
	for i in range(1,m):
		a = (a*i) % sprime

def binom(m):
	if N == m:
		return 1
	elif m == 1:
		return N
	elif m > N:
		return 0
	else:
		return (factorial(N) * modinv(factorial(m),sprime) * modinv(factorial(N-m),sprime)) % sprime

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		sum += (binom(N,i) * binom(N,j)) % sp

print(sum)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

L = input().split()
sprime = 998244353 # approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

@lru_cache(maxsize=N)
def factorial(m):
	a = 1
	for i in range(1,m):
		a = (a*i) % sprime

def binom(m):
	if N == m:
		return 1
	elif m == 1:
		return N
	elif m > N:
		return 0
	else:
		return (a * modinv(b,sprime) * modinv(c*sprime)) % sprime

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		sum += (binom(N,i) * binom(N,j)) % sp

print(sum)

Buggy submission (verdict: Runtime Error):
import math
L = input().split()
sp = 998244353
# approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

def my_binom(n,m):
	if n == m:
		return 1
	elif m == 1:
		return n
	elif m > n:
		return 0
	else:
		a = math.factorial(n)
		b = math.factorial(m)
		c = math.factorial(n - m)
		return a // (b*c)

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		sum += (binom(N,i) * binom(N,j)) % sp

print(sum)