Problem p03332 (python)

Fixed submission:
n,a,b,k=map(int,input().split())
p=998244353
def getinv(n):
  inv=[0]*(n+1)
  inv[1]=1
  for i in range(2,n+1):
    inv[i]=(-(p//i)*inv[p%i])%p
  return inv
def getnCr(n):
  inv=getinv(n)
  nCr=[0]*(n+1)
  nCr[0]=1
  for i in range(1,n+1):
    nCr[i]=(nCr[i-1]*(n-i+1)*inv[i])%p
  return nCr
def solve(n,a,b,k):
  ans=0
  nCr=getnCr(n)
  for i in range(n+1):
    if (k-a*i)<0 or (k-a*i)%b!=0:
      continue
    j=(k-a*i)//b
    if a*i+b*j==k and 0<=j<=n:
      ans+= nCr[i]*nCr[j]
      ans%=p
  return ans
print(solve(n,a,b,k))

Buggy submission (verdict: Runtime Error):
p=998244353
def getinv(n):
  inv = [0]*(n+1)
  #フェルマーの小定理より、a=1の時は1であることが分かる
  inv[1] = 1
  for i in range(2,n+1):
    #そのまま計算すると負になってしまうので、最後にmod pを取ることで正に戻す
    inv[i] = (-(p//a)*inv[p%a])%p
  return inv

def getCmb(n):
  #逆元を取得
  inv = getinv(n)
  #0 <= r <= n に対してnCrを求める
  nCr = [0]*(n+1)
  #r=0の時は、r-1が存在しないので与えておく
  nCr[0] = 1
  for i in range(1,n+1):
    #iで割る代わりにinv[i]をかけ、mod pを求める
    nCr[i] = (nCr[i-1]*(n-i+1)*inv[i])%p
  return nCr

def solve(n,a,b,k):
  nCr = getCmb(n)
  ans=0
  for i in range(n+1):
    #割り切れない時もあるが、その時は次の条件a*i+b*j==kで弾かれるので問題ない
    j = (k-a*i)//b
    #条件に一致するものを選ぶ。jの範囲に注意
    if a*i + b*j == k and 0<=j<=n:
      ans+= (nCr[i]*nCr[j])%p
      ans%= p
  return ans

n,a,b,k=map(int,input().split())
print(solve(n,a,b,k))

Buggy submission (verdict: Runtime Error):
n,a,b,k=map(int,input().split())
p=998244353
def getinv(n):
  inv=[0]*(n+1)
  inv[1]=1
  for i in range(2,n+1):
    inv[i]=(-(p//i)*inv[p%i])%p
  return inv
def getnCr(n):
  inv=getinv(n)
  nCr=[0]*(n+1)
  nCr[0]=1
  for i in range(1,n+1):
    nCr[i]=(nCr[i-1]*(n-i+1)*inv[i])%p
  return nCr
def solve(n,a,b,k):
  ans=0
  nCr=getnCr(n)
  for i in range(n+1):
    if (k-a*i)<0 or (k-a*i)%b!=0:
      continue
    j=(k-a*i)//b
    if a*i+b*j==k:
      ans+= nCr[i]*nCr[j]
      ans%=p
  return ans
print(solve(n,a,b,k))

Buggy submission (verdict: Runtime Error):
n,a,b,k=map(int,input().split())
p=998244353
def getinv(n):
  inv=[0]*(n+1)
  inv[1]=1
  for i in range(2,n+1):
    inv[i]=(-(p//i)*inv[p%i])%p
  return inv
def getnCr(n):
  inv=getinv(n)
  nCr=[0]*(n+1)
  nCr[0]=1
  for i in range(1,n+1):
    nCr[i]=(nCr[i-1]*(n-i+1)*inv[i])%p
  return nCr
def solve(n,a,b,k):
  ans=0
  nCr=getnCr(n)
  for i in range(n+1):
    if (k-a*i)<0 or (k-a*i)%b!=0:
      continue
    j=(k-a*i)//b
    if a*i+b*j==k:
      print(i)
      print(j)
      ans+= nCr[i]*nCr[j]
      ans%=p
  return ans
print(solve(n,a,b,k))

Buggy submission (verdict: Runtime Error):
n,a,b,k=map(int,input().split())
p=998244353
def getinv(n):
  inv=[0]*(n+1)
  inv[1]=1
  for i in range(2,n+1):
    inv[i]=(-p//i*inv[p%i])%p
  return inv
def getnCr(n):
  inv=getinv(n)
  nCr=[0]*(n+1)
  nCr[0]=1
  for i in range(1,n+1):
    nCr[i]=(nCr[i-1]*(n-i-1)*inv[i])%p
  return nCr
def solve(n,a,b,k):
  ans=0
  nCr=getnCr(n)
  for i in range(n+1):
    if (k-a*i)%b!=0:
      continue
    j=(k-a*i)//b
    if a*i+b*j==k:
      ans+=(nCr[i]*nCr[j])%p
      ans%=p
  return ans
print(solve(n,a,b,k))

Buggy submission (verdict: Runtime Error):
n,a,b,k=map(int,input().split())
p=998244353
def getinv(n):
  inv=[0]*(n+1)
  inv[1]=1
  for i in range(2,N+1):
    inv[i]=(-p//i*inv[p%i])%p
  return inv
def getnCr(n):
  inv=getinv(n)
  nCr=[0]*(n+1)
  nCr[0]=1
  for i in range(1,n+1):
    nCr[i]=(nCr[i-1]*(n-i-1)*inv[i])%p
  return nCr
def solve(n,a,b,k):
  ans=0
  nCr=getnCr(n)
  for i in range(n+1):
    j=(k-a*i)//b
    if a*i+b*j==k:
      ans+=nCr[i]+nCr[j]
      ans%=p
  return ans
print(solve(n,a,b,k))

Buggy submission (verdict: Runtime Error):
from math import factorial
n,a,b,k=map(int,input().split())
def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y,x%y)
ans=0
p=998244353
x=gcd(a,b)
if k%x==0:
  A=a//x
  B=b//x
  K=k//x
  for i in range(n):
    if K-A*i>=0 and (K-A*i)%B==0:
      ans+= (((factorial(n)//factorial(n-i)//factorial(i))%p)*((factorial(n)//factorial(n-(K-A*i)//B)//factorial((K-A*i)//B))%p))%p
      ans=ans%p
print(ans)

Buggy submission (verdict: Runtime Error):
from math import factorial
n,a,b,k=map(int,input().split())
def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y,x%y)
ans=0
p=998244353
x=gcd(a,b)
if K%x==0:
  A=a//x
  B=b//x
  K=k//x
  for i in range(n):
    if (K-A*i)%B==0:
      ans+= (factorial(n)//factorial(n-i)//factorial(i))*(factorial(n)//factorial(n-(K-A*i)//B)//factorial((K-A*i)//B))
print(ans)

Buggy submission (verdict: Runtime Error):
import math
n,a,b,k=map(int,input().split())
def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y,x%y)
p=gcd(a,b)
ans=0
for i in range(k//(a+b)):
  if (k-(a+b)*i)%p!=0:
    continue
  else:
    q=gcd(p,k-(a+b)*i)
    A=a//q
    B=b//q
    K=k//q
    A_=(pow(A,B-2,B)*K)%p
    for i in range((n-i-A_)//B):
      ans+=math.factorial(n-i)//(math.factorial(A_+B*i)*math.factorial((k-A_+B*i)//B)*math.factorial(n-i-A_+B*i-(k-A_+B*i)//B))
print(ans)