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):
import math
import sys
sys.setrecursionlimit(100000000000000000000000000000000000000000)
 
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]
 
 
n, a, b, k = map(int, input().split())
count = 0
 
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += cmb(n, i) * cmb(n, (k-i*a)/b)
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import math
import sys
sys.setrecursionlimit(100000)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0

for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += cmb(n, i) * cmb(n, (k-i*a)/b)
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
if k ==0:
    print("0")
    exit()
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += int(cmb(n, i) * cmb(n, int((k-i*a)/b)))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
if k ==0:
    print("0")
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += int(cmb(n, i) * cmb(n, int((k-i*a)/b)))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += int(cmb(n, i) * cmb(n, int((k-i*a)/b)))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += int(cmb(n, i) * cmb(n, (k-i*a)/b))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += (cmb(n, i) * cmb(n, (k-i*a)/b))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += (cmb(n, i) * cmb(n, (k-a*i)/b))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
for i in range(n):
    if (k - (i * a)) % b == 0:
        count += (cmb(n, i) * cmb(n, (k-a*i)/b))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(k/a)):
    if (k - (i * a)) % b == 0:
        count += (cmb(n, i) * cmb(n, (k-a*i)/b))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import math
from scipy.special import comb

n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(k/a)):
    if (k - (i * a)) % b == 0:
        count += (comb(n, i) * comb(n, (k-a*i)/b))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import math
def C(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(k/a)):
    if (k - (i * a)) % b == 0:
        count += (C(n, i) * C(n, (k-a*i)/b))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import math

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)

def C(n, r):
    return P(n, r)//math.factorial(r)

n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(k/a)):
    if (k - (i * a)) % b == 0:
        count += (C(n, i) * C(n, (k-a*i)/b))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import itertools
import math

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)

def C(n, r):
    return P(n, r)//math.factorial(r)

n, a, b, k = map(int, input().split())
count = 0
for i in range(k):
    if (k - (i * a)) % b == 0:
        count += (C(n, i) * C(n, (k-a*i)/b))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import itertools
import math
n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(k/a)):
    if (k - (i * a)) % b == 0:
        count += (itertools.combinations(n, i) * itertools.combinations(n, (k-i*a)/b))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import itertools
import math
n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(n/a)):
    if (n - (i * a)) % b == 0:
        count += (itertools.combinations(n, i) * itertools.combinations(n, (n-i*a)/b))
print(count%998244353)

Buggy submission (verdict: Runtime Error):
import itertools
import math
n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(n/a)):
    if (n - (i * a)) % b == 0:
        count += (itertools.combinations(n, i) * itertools.combinations(n, (n-i*a)/b))
print(count/998244353)

Buggy submission (verdict: Runtime Error):
import itertools
n, a, b, k = map(int, input().split())
count = 0
for i in range(n):
    if (n - (i * a)) % b == 0:
        count += (itertools.combinations(n, i) * itertools.combinations(n, (n-i*a)/b))
print(count/998244353)