Problem:


Score : 700 points

Problem Statement

Takahashi has a tower which is divided into N layers.
Initially, all the layers are uncolored. Takahashi is going to paint some of the layers in red, green or blue to make a beautiful tower.
He defines the beauty of the tower as follows:

The beauty of the tower is the sum of the scores of the N layers, where the score of a layer is A if the layer is painted red, A+B if the layer is painted green, B if the layer is painted blue, and 0 if the layer is uncolored.

Here, A and B are positive integer constants given beforehand. Also note that a layer may not be painted in two or more colors.

Takahashi is planning to paint the tower so that the beauty of the tower becomes exactly K.
How many such ways are there to paint the tower? Find the count modulo 998244353.
Two ways to paint the tower are considered different when there exists a layer that is painted in different colors, or a layer that is painted in some color in one of the ways and not in the other.

Constraints

1 ≤ N ≤ 3×10^5

1 ≤ A,B ≤ 3×10^5

0 ≤ K ≤ 18×10^{10}

All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N A B K

Output

Print the number of the ways to paint tiles, modulo 998244353.

Sample Input 1

4 1 2 5

Sample Output 1

40

In this case, a red layer worth 1 points, a green layer worth 3 points and the blue layer worth 2 points. The beauty of the tower is 5 when we have one of the following sets of painted layers:

1 green, 1 blue

1 red, 2 blues

2 reds, 1 green

3 reds, 1 blue

The total number of the ways to produce them is 40.

Sample Input 2

2 5 6 0

Sample Output 2

1

The beauty of the tower is 0 only when all the layers are uncolored. Thus, the answer is 1.

Sample Input 3

90081 33447 90629 6391049189

Sample Output 3

577742975



Sample input:
4 1 2 5


Sample output:
40

Submission status: Wrong Answer

Solution code:
import math

def ncr(n, r):
    r = int(min(r, n - r))
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    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):
        if numerator[k] > 1: 
            result = (result * numerator[k]) % 998244353
    return int(result)
  
n,a,b,k = map(int,input().split())
mod = 998244353
c = 0
for s in range(n):
  t = (k-s*a) / b
  if t >= 0 and t % 1 == 0:
    c += (ncr(n,s) % mod * ncr(n,t) % mod) % mod


print(c)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

MOD = 998244353
N = 1000

Fac = [0] * (3*(10**5) + 100)
invFac = [0] * (3*(10**5) + 100)

Fac[0] = 1
Fac[1] = 1
invFac[0] = 1
invFac[1] = 1
for i in xrange(2, N+1):
	Fac[i] = (Fac[i-1] * i) % MOD

for i in xrange(2, N+1):
	invFac[i] = pow(Fac[i], MOD-2, MOD)

def C(n, m):
	return (((Fac[n] * invFac[m]) % MOD) * invFac[n-m]) % MOD

# print invFac[:20]

############
l = raw_input()
N, A, B, K = [int(x) for x in l.split()]

a = 0
pl = []
while True:
	b = (K-A*a)/B
	if b < 0:
		break
	if A*a + B*b != K:
		a += 1
		continue
	if a + b > N:
		a += 1
		continue
	pl.append((a, b))
	a += 1

# print pl

ans = 0
for a, b in pl:
	ans = (ans + (C(N, a) * C(N, b)) % MOD) % MOD
print ans

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC025 B
"""

import itertools
from functools import reduce

cut = 998244353


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


def modInverse(a, b, divmod=divmod):
    r0, r1, s0, s1 = a, b, 1, 0
    while r1 != 0:
        q, rtmp = divmod(r0, r1)
        stmp = s0-q*s1
        r0, s0 = r1, s1
        r1, s1 = rtmp, stmp
    return s0 % b


fact = [1]
tmp = 1
for i in range(1, n+1):
    tmp = tmp*i % cut
    fact.append(tmp)


def binom(nn, kk):
    return (fact[nn]*modInverse(fact[kk], cut) % cut)*modInverse(fact[nn-kk], cut) % cut


ans = 0
for i in range(0, min(n+1, k//a+1)):
    ita = i*a
    ib, bmod = divmod(k-ita, b)
    if bmod == 0 and ib <= n:
        ans = ans+binom(n, i)*binom(n, ib) % cut

print(ans)

Submission status: Wrong Answer

Solution code:
Q = 998244353
def modpower(a,b,Q):#a^b mod Q
    if b == 0:
        return 1
    if b%2 == 0:
        d = modpower(a,b//2,Q)
        return d*d%Q
    if b%2 == 1:
        return (a*modpower(a,b-1,Q))%Q
def factorials(n,Q):#n以下の階乗のリストと階乗の逆元のmodQでのリスト
    F = [1]*(n+1)
    R = [1]*(n+1)
    for i in range(n):
        F[i+1] = F[i]*(i+1)%Q
        R[i+1] = R[i]*modpower(i+1,Q-2,Q)
    return F, R

N, A, B, K = map( int, input().split())
ans = 0
F, R = factorials(N,Q)
print(F)
print(R)
for i in range( min(K//A, N)+1):
    if (K-A*i)%B == 0:
        print(i)
        j = (K-A*i)//B
        print(F[N]*R[j]*R[N-j]%Q*F[N]*R[i]*R[N-i]%Q)
        ans = (ans + F[N]*R[j]*R[N-j]%Q*F[N]*R[i]*R[N-i]%Q)%Q
print(ans)

Submission status: Wrong Answer

Solution code:
N, A, B, K = map(int, input().split())

C = [0] * (3 * 10 ** 5 + 5)
rC = [0] * (3 * 10 ** 5 + 5)
MOD = 998244353

C[1] = 1
rC[1] = 1
for i in range(2, N + 1):
    C[i] = C[i - 1] * i % MOD

rC[N] = pow(C[N], MOD - 2, MOD)

for i in range(N, 1, -1):
    rC[i - 1] = rC[i] * i % MOD


def calc(n, m):
    return C[n] * rC[n - m] * rC[m] % MOD

num = 0
for i in range(N + 1):
    if (K - A * i) % B == 0:
        j = (K - i * A) // B
        if 0 <= j <= N:
            num += calc(N, i) * calc(N, j)
            num = num % MOD

if K == 0:
    print(1)
else:
    print(num % MOD)

Submission status: Wrong Answer

Solution code:
N, A, B, K = map(int, input().split())

C = [0] * (3 * 10 ** 5 + 5)
rC = [0] * (3 * 10 ** 5 + 5)
MOD = 998244353

C[1] = 1
rC[1] = 1
for i in range(2, N + 1):
    C[i] = C[i - 1] * i % MOD

rC[N] = pow(C[N], MOD - 2, MOD)

for i in range(N, 1, -1):
    rC[i - 1] = rC[i] * i % MOD


def calc(n, m):
    return C[n] * rC[n - m] * rC[m] % MOD

num = 0
for i in range(N + 1):
    if (K - A * i) % B == 0:
        j = (K - i * A) // B
        if 0 <= j <= N:
            num += calc(N, i) * calc(N, j) % MOD

if K == 0:
    print(1)
else:
    print(num % MOD)

Submission status: Wrong Answer

Solution code:
N, A, B, K = map(int, input().split())

C = [0] * (3 * 10 ** 5 + 5)
rC = [0] * (3 * 10 ** 5 + 5)
MOD = 998244353

C[1] = 1
rC[1] = 1
for i in range(2, N + 1):
    C[i] = C[i - 1] * i % MOD

rC[N] = pow(C[N], MOD - 2, MOD)

for i in range(N, 1, -1):
    rC[i - 1] = rC[i] * i % MOD


def calc(n, m):
    return C[n] * rC[n - m] * rC[m] % MOD

num = 0
for i in range(N + 1):
    if (K - A * i) % B == 0:
        j = (K - i * A) // B
        if 0 <= j <= N:
            num += calc(N, i) * calc(N, j) % MOD

if K == 0:
    print(1)
else:
    print(num)

Submission status: Wrong Answer

Solution code:
n,a,b,k=map(int,input().split())
s=0
m=998244353
f=[1]
r=[1]
 
for i in range(1,n+1):
  f+=[i*f[i-1]%m]
  r+=[pow(f[i],m-2,m)]

cb=lambda x,y:(f[x]*r[x-y]*r[y])%m

for i in range(n):
  c,d=divmod(k-a*i,b)
  if d==0 and 0<=c<=n:
    s+=(cb(n,i)*cb(n,c))%m

print(s%m)

Submission status: Wrong Answer

Solution code:
n,a,b,k=map(int,input().split())
s=0
m=998244353
f=[1]
r=[1]
 
for i in range(1,n+1):
  f+=[i*f[i-1]%m]
  r+=[pow(f[i],m-2,m)]

cb=lambda x,y:f[x]*r[x-y]*r[y]

for i in range(n):
  c,d=divmod(k-a*i,b)
  if d==0 and 0<=c<=n:
    s=(s+cb(n,i)*cb(n,c))%m

print(s)

Submission status: Wrong Answer

Solution code:
n,a,b,k=map(int,input().split())
s=0
m=998244353
f=[1]
r=[1]
 
for i in range(1,n+1):
  f+=[i*f[i-1]%m]
  r+=[pow(f[i],m-2,m)]

cb=lambda x,y:f[x]*r[x-y]*r[y]

for i in range(n//a):
  c,d=divmod(k-a*i,b)
  if d==0 and 0<=c<=n:
    s=(s+cb(n,i)*cb(n,c))%m

print(s)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import math

in_strings = lambda: stdin.readline()[:-1] # s = in_strings()
in_int = lambda: int(stdin.readline()) # N = in_int()
in_intlist = lambda: list(map(int, stdin.readline().split())) # List = in_intlist()

N, A, B, K = in_intlist()
NUM = 998244353

# 逆元
Inv = [0 for _ in range(N)]
for i in range(N):
    Inv[i] = pow(i+1, NUM-2, NUM)

# Combination
Comb = [0 for _ in range(N+1)]
Comb[0] = 1
for i in range(1, N+1):
    Comb[i] = (Comb[i-1] * (N-i+1) * Inv[i-1]) % NUM


ans = 0
for i in range(N+1):
    if ((K - i*A) % B == 0) and ((K - i*A) // B <= N):
        ans = (ans + Comb[i]*Comb[(K - i*A) // B]) % NUM 
        if i*A > K:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        
# 二項係数
def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod



MOD = 998244353

n,a,b,k = li()

# 二項係数の準備
inv = inv_mod(n,MOD)
fac = fact(n,MOD)
facInv = fact_inv(n,inv,MOD)

ans = 0

for red in range(n+1):
    res = k - red*a
    if res%b != 0:
        continue
    else:
       blue = res//b
       
       ans += nCr(n,red,MOD,fac,facInv) * nCr(n,blue,MOD,fac,facInv)

print(ans)

Submission status: Wrong Answer

Solution code:
N,A,B,K=map(int,input().split())
P=998244353
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(1,N+1):
    Fact[i]=(i*Fact[i-1])%P
    Finv[i]=(Finv[i-1]*inv(i))%P
ans=0
def NC(k):
    tmp=(Finv[k]*Finv[N-k])%P
    return (Fact[N]*tmp)%P
for x in range(N):
    y=(K-x*A)//B
    if x*A+y*B==K and 0<=y<=N:
        ans+=(NC(x)*NC(y))%P
print(ans%P)

Submission status: Wrong Answer

Solution code:
n,a,b,k=map(int,input().split())
l=[]

mod=998244353
fac=[None]*(n+1)
rev=[None]*(n+1)

fac[0]=1
rev[0]=1

for i in range(1,n+1):
  fac[i]=i*fac[i-1]%mod
  rev[i]=pow(fac[i],mod-2,mod)

f=lambda a,b:(fac[a]*rev[a-b]*rev[b])%mod

for i in range(n+1):
  if not (k-a*i)%b:
    j=(k-a*i)//b
    if 0<=j<=n:
      l.extend([(i,j)])

s=0
for (i,j) in l:
  s+=(f(n,i)*f(n,j))%mod

print(s)

Submission status: Wrong Answer

Solution code:
import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    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):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result;

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

if a<0 or b<0 or k<a or k<b:
    print("0")
    exit()

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

Submission status: Wrong Answer

Solution code:
import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    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):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result;

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, int((k-i*a)/b))
print(count%998244353)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def aCb(a,b):
	res = 1
	for i in range(b):
		res*=(a-i)/(i+1)
	return res
	
N, A, B, K = map(int, input().split())

total=0

# (a+c)=n, (b+c)=mとすると nA+mB=K, a+b+c<=N
#塗り方を地道に数える
for n in range(N+1):
	#mB = K - n*A, N-n=残りブロック
	if K-n*A<0 or (N-n)*B+n*A<K:
		#ポイントオーバー or ブロックが足りない
		continue
	m=(K-n*A)/B
	if m!=int(m):
		#該当するmがない
		continue
	#n=a+cの内訳を考える
	for a in range(n+1):
		#a, b, cの組み合わせが決定する
		c=n-a
		b=int(m-c)
		if b<0 or a+b+c > N:
			continue
		#組み合わせ数=NCa*(N-a)Cb*(N-a-b)Cc
		comb = aCb(N, a)* aCb(N-a, b)* aCb(N-a-b, c)
		total += comb

result=total%998244353
print(int(result))

Submission status: Wrong Answer

Solution code:
import math
import sys
import fractions
inp = input()
N,A,B,K = list(map(int,inp.split()))
# g = math.gcd(A,B)
g = fractions.gcd(A,B)
if K % g != 0:
    print(0)
    sys.exit()
A = A // g
B = B // g
K = K // g
xn = []
yn = []
for i in range(10 ** 100):
    if (A * i- K) % B == 0:
        n = i
        xn.append(n)
        yn.append((K - A *n) // B)
        break
if yn[-1] < 0:
    if K % B == 0 and (K // B <= N):
        print(1)
    else:
        print(0)
    sys.exit()
while True:
    x  = xn[-1] + B
    y  = yn[-1] - A
    if y < 0:
        break
    xn.append(x)
    yn.append(y)
ans = 0
P = 998244353
def inv(n):
  return pow(n, P-2, P)
fact = [1] * (N+1)
for i in range(1, N+1):
  fact[i] = fact[i-1] * i % P
invfact = [inv(fact[N])] * (N+1)
for i in range(N, 0, -1):
  invfact[i-1] = invfact[i] * i % P
def comb(n, k):
  return fact[n] * invfact[k] * invfact[n-k] % P 
 
for x,y in zip(xn,yn):
    if N-x< 0 or N -y < 0:
        continue 
    ans = (ans + (comb(N,x) * comb(N,y)) % P)
print(ans)

Submission status: Wrong Answer

Solution code:
n, A, B, k = list(map(int, input().split()))

MOD = 998244353
MAX = n+2

fact, inverse = [0]*(MAX), [0]*(MAX)
fact[0], inverse[0] = 1, 1
for i in range(1, MAX):
  fact[i] = (fact[i-1]*i)%MOD
  inverse[i] = pow(fact[i], MOD-2, MOD)

def mod_comb(n, r):
  if n<r or n==0: return 0
  if r==0: return 1
  return (((fact[n]*inverse[r])%MOD)*inverse[n-r])%MOD

ans = 0
for i in range(n+1):
  b = (k-A*i)/B
  if b%1==0:
    b = int(b)
  else:
    continue
  if 0<=b<=n:
    ans += (mod_comb(n, i)*mod_comb(n, b))%MOD

if ans==0:
  print(1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
n, A, B, k = list(map(int, input().split()))

MOD = 998244353
MAX = n+2

fact, inverse = [0]*(MAX), [0]*(MAX)
fact[0], inverse[0] = 1, 1
for i in range(1, MAX):
  fact[i] = (fact[i-1]*i)%MOD
  inverse[i] = pow(fact[i], MOD-2, MOD)

def mod_comb(n, r):
  if n<r or n==0: return 0
  if r==0: return 1
  return (((fact[n]*inverse[r])%MOD)*inverse[n-r])%MOD

ans = 0
if n==0:
  print(1)
else:
  for i in range(n+1):
    b = (k-A*i)/B
    if b%1==0:
      b = int(b)
    else:
      continue
    if 0<=b<=n:
      ans += (mod_comb(n, i)*mod_comb(n, b))%MOD
  print(ans)

Submission status: Wrong Answer

Solution code:
n,a,b,k= map(int,input().split())	
w = []


w = [1]
for i in range(0,n):
    w.append(w[-1]*(n-i)//(i+1)% 998244353)
#コンビネーションw[i] = nCi


c = 0
if k//a >= n:
    x = n
else:
    x = k //a

if k == 0:
    c = 1   
else:
    for h in range(0,x+1):
        i = (k-a*h)/b
    
        if i == int(i) and n >= i:
            c = w[h]*w[int(i)]%998244353+c

print(c%998244353)

Submission status: Wrong Answer

Solution code:
fact_list=[None]*300001
fact_list[0]=1
for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
if b>a:
    a,b=b,a
for i in range(n+1):
    if k-a*i<0:
        break
    j=(k-a*i)//b
    if (k-a*i)%b==0 and 0<=j<=n:
        if i==0 or i==n:
            x=1
        else:
            x=fact_list[i]*fact_list[n-i]%998244353
        if j!=0 and j!=n:
            x*=fact_list[j]*fact_list[n-j]%998244353
            x%=998244353
        invx=1
        for i in range(30):
            if i!=23 and i!=26:
                invx=(invx*x)%998244353
            x=(x**2)%998244353
        ncr=invx*fact_list[n]**2%998244353
        ncr%=998244353
        res=(res+ncr)%998244353
print(res)

Submission status: Wrong Answer

Solution code:
fact_list=[None]*300001
fact_list[0]=1
for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
if b>a:
    a,b=b,a
for i in range(n+1):
    if k-a*i<0:
        break
    j=(k-a*i)//b
    if (k-a*i)%b==0 and 0<=j<=n:
        if i==0 or i==n:
            x=1
        else:
            x=fact_list[i]*fact_list[n-i]%998244353
        if j!=0 and j!=n:
            x*=fact_list[j]*fact_list[n-j]%998244353
            x%=998244353
        invx=1
        for i in range(30):
            if i!=23 and i!=26:
                invx=(invx*x)%998244353
            x=(x**2)%998244353
        ncr=invx*fact_list[n]**2%998244353
        ncr%998244353
        res=(res+ncr)%998244353
print(res)

Submission status: Wrong Answer

Solution code:
fact_list=[None]*300001
fact_list[0]=1

def inv(n):
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*n)%998244353
        n=(n**2)%998244353
    return s
"""
def enc(n):
    if n==0:
        return "("
    s=""
    while n>0:
        s+=chr(n%86+40)
        n//=86
    return s

def dec(s):
    n=0
    for i in range(len(s)):
        n+=(86**i)*(ord(s[i])-40)
    return n
def comb(n,r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    if inv_fact_list[n-r]!=None:
        invnr=inv_fact_list[n-r]
    else:
        m=fact_list[n-r]
        invnr=1
        for i in range(30):
            if i!=23 and i!=26:
                invnr=(invnr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[n-r]=invnr
    if inv_fact_list[r]!=None:
        invr=inv_fact_list[r]
    else:
        m=fact_list[r]
        invr=1
        for i in range(30):
            if i!=23 and i!=26:
                invr=(invr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[r]=invr
    return (((fact_list[n]*invnr)%998244353)*invr)%998244353
"""

for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
if b>a:
    a,b=b,a
for i in range(n):
    if k-a*i<0:
        break
    j=(k-a*i)//b
    if (k-a*i)%b==0 and 0<=j<=n:
        res=(res+(fact_list[n]**2)*inv((((fact_list[i]*fact_list[j]%998244353)*fact_list[n-i]%998244353)*fact_list[n-j]%998244353)))%998244353
print(res)

Submission status: Wrong Answer

Solution code:
fact_list=[None]*300001
inv_fact_list=[None]*300001
fact_list[0]=1
inv_fact_list[0]=1
s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353
"""
def inv(n):
    if inv_fact_list[n]!=None:
        return inv_fact_list[n]
    m=fact_list[n]
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*m)%998244353
        m=(m**2)%998244353
    inv_fact_list[n]=s
    return s
def enc(n):
    if n==0:
        return "("
    s=""
    while n>0:
        s+=chr(n%86+40)
        n//=86
    return s

def dec(s):
    n=0
    for i in range(len(s)):
        n+=(86**i)*(ord(s[i])-40)
    return n
"""
def comb(r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    if inv_fact_list[n-r]!=None:
        invnr=inv_fact_list[n-r]
    else:
        m=fact_list[n-r]
        invnr=1
        for i in range(30):
            if i!=23 and i!=26:
                invnr=(invnr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[n-r]=invnr
    if inv_fact_list[r]!=None:
        invr=inv_fact_list[r]
    else:
        m=fact_list[r]
        invr=1
        for i in range(30):
            if i!=23 and i!=26:
                invr=(invr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[r]=invr
    return (((fact_list[n]*invnr))*invr)%998244353

res=0
if b>a:
    a,b=b,a
for i in range(n):
    if k-a*i<0:
        break
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res=(res+comb(i)*comb((k-a*i)//b))%998244353
print(res)

Submission status: Wrong Answer

Solution code:
fact_list=[1 for i in range(300001)]
def inv(n):
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*n)%998244353
        n=(n**2)%998244353
    return s

def comb(n,r):
    if r==0 or r==n:
        return 1
    return (((fact_list[n]*inv(fact_list[n-r]))%998244353)*inv(fact_list[r]))%998244353

for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n):
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res+=comb(n,i)*comb(n,(k-a*i)//b)
        res%=998244353
print(res)

Submission status: Wrong Answer

Solution code:
fact_list=[1 for i in range(300001)]
def inv(n):
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*n)%998244353
        n=(n**2)%998244353
    return s

def comb(n,r):
    if r==0:
        return 1
    return (((fact_list[n]*inv(fact_list[n-r]))%998244353)*inv(fact_list[r]))%998244353

for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n):
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res+=comb(n,i)*comb(n,(k-a*i)//b)
        res%=998244353
print(res)

Submission status: Wrong Answer

Solution code:
fact_list=[1 for i in range(300001)]
def inv(n):
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*n)%998244353
        n=(n**2)%998244353
    return s
def comb(n,r):
    return (((fact_list[n]*inv(fact_list[n-r]))%998244353)*inv(fact_list[r]))%998244353

for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n):
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res+=comb(n,i)*comb(n,(k-a*i)//b)
        res%=998244353
print(res)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

n, a, b, k = map(int, input().split())
MOD = 998244353

inv = [0] * ( n + 1)
inv[1] = 1
for i in range(2, n + 1):
    inv[i] = (-(MOD // i) * inv[MOD % i]) % MOD

nCr = [0] * ( n + 1)
nCr[0] = 1
for i in range(1, n+1):
    nCr[i] = (nCr[i-1] * (n - i + 1) * inv[i]) % MOD

result = 0
maxA = min(n, k//a)
for i in range(maxA):
    if ( k - a * i) % b == 0:
        j = ( k - a * i) // b
        if j <= n:
            result += (nCr[i] * nCr[j]) % MOD
if result == 0:
    print(1)
else:
    print(result % MOD)

Submission status: Wrong Answer

Solution code:
n, a, b, k = map(int, input().split())
MOD = 998244353

inv = [0] * ( n + 1)
inv[1] = 1
for i in range(2, n + 1):
    inv[i] = (-(MOD // i) * inv[MOD % i]) % MOD

nCr = [0] * ( n + 1)
nCr[0] = 1
for i in range(1, n+1):
    nCr[i] = nCr[i-1] * (n - i + 1) * inv[i] % MOD

result = 0
maxA = min(n, k//a)
for i in range(maxA):
    if ( k - a * i) % b == 0:
        j = ( k - a * i) // b
        if j <= n:
            result += nCr[i] * nCr[j] % MOD
if result == 0:
    print(1)
else:
    print(result % MOD)

Submission status: Wrong Answer

Solution code:
import itertools
import math

N,A,B,K=map(int,input().split())
GREEN=0
RED=0
BLUE=0
KUMI=[]
num=0
Nfactorial=math.factorial(N)

def KUMIinc():
  global num
  if K==(GREEN*(A+B)+BLUE*B+RED*A):
    KUMI.append((RED,BLUE,GREEN,N-RED-BLUE-GREEN))
    print(KUMI)
    num+=Nfactorial//((math.factorial(RED)*math.factorial(BLUE)*math.factorial(GREEN)*math.factorial(N-RED-BLUE-GREEN)))

for i in range(N+1):
  GREEN=i
  for j in range(N+1-(i)):
    BLUE=j
    for k in range(N+1-(i+j)):
      RED=k
      KUMIinc()


print(num%998244353)

Submission status: Wrong Answer

Solution code:
import operator as op
N, A, B, K = map(int, raw_input().split())
if A < B:
  A, B = B, A
ab = []
max_a = K // A
for i in range(max_a+1):
  if (K-A*i) % B == 0:
    j = (K-A*i) // B
    if i + j > N:
      continue
    ab.append([i, j])
xyz = []
for a, b in ab:
  c = min(a, b)
  for i in range(c+1):
    y = i
    x = a - y
    z = b - y
    if x + y + z > N:
      continue
    xyz.append([x, y, z])

def ncr(n, r):
  r = min(r, n-r)
  numer = reduce(op.mul, xrange(n, n-r, -1), 1)
  denom = reduce(op.mul, xrange(1, r+1), 1)
  return numer//denom

total = 0
for x, y, z in xyz:
  total += ncr(N, x) * ncr(N-x, y) * ncr(N-x-y, z)
print(total)

Submission status: Wrong Answer

Solution code:
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD

    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 f, invs


def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1

    while c1 != 0:
        m = c0 % c1
        q = c0 // c1

        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)

    return c0, a0, b0


def solve(n, a, b, k):
    MOD = 998244353
    fn, invs = prepare(n, MOD)

    if a < b:
        a, b = b, a
    c, x, y = ex_euclid(a, b)
    d, m = divmod(k, c)
    if m != 0:
        return 0
    ac, bc = a // c, b // c
    x, y = x * d, y * d
    if x < 0:
        f = ((x % bc) - x) // bc
        x += bc * f
        y -= ac * f
    if y > n:
        f = (y - n - 1) // ac + 1
        x += bc * f
        y -= ac * f

    ans = 0
    base = fn * fn % MOD
    while x <= n and y >= 0:
        tmp = base * invs[x]
        tmp %= MOD
        tmp *= invs[n - x]
        tmp %= MOD
        tmp *= invs[y]
        tmp %= MOD
        tmp *= invs[n - y]
        ans += tmp
        ans %= MOD
        x += bc
        y -= ac

    return ans


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

print(solve(n, a, b, k))

Submission status: Wrong Answer

Solution code:
N, A, B, K = map(int, input().split())

mod = 998244353
fact = [1] * (N + 1)
ifact = [1] * (N + 1)


def init():
    for i in range(N):
        fact[i + 1] = fact[i] * (i + 1) % mod
        ifact[i + 1] = pow(fact[i + 1], mod - 2, mod)


def comb(x, y):
    if y < 0 or y > x:
        return 0
    return (fact[x] * ifact[x - y] * ifact[y]) % mod


ans = 0
init()
for a in range(N):
    n = K - a * A
    if n < 0:
        break
    if n % B == 0:
        ans += (comb(N, a) * (comb(N, n // B))) % mod
print(ans % mod)

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    n,a,b,k=map(int,input().split())
    ans = solve(n,a,b,k)
    print(ans)

def calcFactTable(n,p):
    fact=[1] * (n+1)
    invfact=[1] * (n+1)
    for i in range(1,n+1):
        fact[i] = i*fact[i-1]%p
    invfact[n]=pow(fact[n],p-2,p)
    for i in range(1,n+1):
        invfact[n-i] = (n-i+1)*invfact[n-i+1]%p
    return (fact,invfact) 

def mComb(n,m,fact,invfact,p):
    return (fact[n] * invfact [m] % p) * invfact[n-m] % p

def mprod(x,y,p):
    return x*y%p

def solve(n,a,b,k):
    #ax+by=k x,y<-[0..n]
    solutions=[]
    for x in range(0,n+1):
        right = k - a*x
        y = right//b
        if (y<=n and y>= 0 and right%b ==0):
            solutions.append((x,y))
    ans = 0
    #combinations
    p = 998244353
    fs,invs = calcFactTable(n,p)
    for (x,y) in solutions:
        ans += mComb(n,x,fs,invs,p) * mComb(n,y,fs,invs,p) % p
    return ans

main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    n,a,b,k=map(int,input().split())
    ans = solve(n,a,b,k)
    print(ans)

def calcFactTable(n,p):
    fact=[1] * (n+1)
    invfact=[1] * (n+1)
    for i in range(1,n+1):
        fact[i] = i*fact[i-1]%p
    invfact[n]=pow(fact[n],p-2,p)
    for i in range(1,n+1):
        invfact[n-i] = (n-i+1)*invfact[n-i+1]%p
    return (fact,invfact) 

def mComb(n,m,fact,invfact,p):
    return (fact[n] * invfact [m] % p) * invfact[n-m] % p

def mprod(x,y,p):
    return x*y%p

def solve(n,a,b,k):
    #ax+by=k x,y<-[0..n]
    solutions=[]
    for x in range(0,n+1):
        right = k - a*x
        y = right//b
        if (y<=n and y>= 0 and right%b ==0):
            solutions.append((x,y))
    ans = 0
    #combinations
    p = 998244353
    fs,invs = calcFactTable(n,p)
    for (x,y) in solutions:
        ans += mComb(n,x,fs,invs,p) * mComb(n,y,fs,invs,p) % p
    return ans

Submission status: Wrong Answer

Solution code:
n, a, b, k = map(int, input().split())

M = 998244353
fact_n = [0 for m in range(n+1)]
fact_inv = [0 for m in range(n+1)]


def combination(n, r):
    if n == 0 and r == 0:
        return 1
    elif n < r or n < 0:
        return 0

    c = fact_inv[r] * fact_inv[n-r] % M
    return fact_n[n] * c % M


def main():
    fact_n[0] = fact_inv[0] = 1
    for i in range(1, n+1):
        fact_n[i] = fact_n[i-1] * i % M
        fact_inv[i] = fact_inv[i-1] * pow(i, M-2, M) % M

    com = 0
    for i in range(n):
        if (k-a*i) % b == 0 and k >= a * i:
            j = (k-a*i) // b
            com += combination(n, i) * combination(n, j) % M

    print(com % M)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,a,b,k = map(int,(input().split()))

b_K = k // b
ab_list = []

for i in range(1,min(n,b_K + 1)):
    if (k - i * b) % a == 0:
        ab_list.append([(k - i * b) // a, i])

def facto(n):
    li = [1,1]
    k = 1
    while (k < n):
        k = k + 1
        li.append(li[-1] * k)
    return li

ans = 0
fac = facto(n)
for a, b in ab_list:
    for i in range(min(a,b) + 1):
        delta = fac[n] //(fac[i] * fac[a - i] * fac[b - i] * fac[n - a - b + i])
        print (a- i,i,b-i,delta)
        ans = ans + delta

print (ans)

Submission status: Wrong Answer

Solution code:
# https://beta.atcoder.jp/contests/agc025/tasks/agc025_b
from functools import reduce
import operator as op

MOD = 998244353
mod_inv = [0, 1]


def init_mod_inv(n):
    for i in range(2, n + 1):
        ans = MOD - (MOD // i) * mod_inv[MOD % i] % MOD
        mod_inv.append(ans)


def main():
    n, a, b, k = map(int, input().split())

    init_mod_inv(n)
    nCr = [0] * (n + 1)
    nCr[0] = 1
    for i in range(1, n):
        nCr[i] = (nCr[i - 1] * (n - i + 1) * mod_inv[i]) % MOD

    ways = 0
    for x in range(0, n + 1):
        yb = k - a * x
        if yb >= 0 and yb % b == 0 and yb // b <= n:
            ways += nCr[x] * nCr[yb // b]
            ways %= MOD
    print(ways)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import factorial

N, A, B, K = tuple(map(int, input().split()))

result = 0
for a in range(1, N):
  b = (K-A*a)/B
  if b.is_integer() and b < N:
    comb_a = factorial(N) // (factorial(N - a) * factorial(a))
    comb_b = factorial(N) // (factorial(N - b) * factorial(b))
    result += comb_a*comb_b
print(result%998244353)