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: Accepted

Solution code:
def cmb(n,r,mod):
  if r<0 or r>n:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod

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

g1=[1,1]
g2=[1,1]
inverse=[0,1]

for i in range(2,n+1):
  g1.append((g1[-1]*i)%m)
  inverse.append((-inverse[m%i]*(m//i))%m)
  g2.append((g2[-1]*inverse[-1])%m)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 16 18:40:19 2019

@author: Yamazaki Kenichi
"""

N,A,B,K = map(int,input().split())
mod = 998244353
def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inv = [0, 1] # 逆元テーブル計算用テーブル
for i in range(2, N+1):
    g1.append((g1[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inv[-1]) % mod)
def a(r,b):
    return cmb(N,r,mod)*cmb(N,b,mod)
ans = 0
R = K//A
for i in range(R+1):
    if (K-A*i)%B == 0:
        ans += a(i,(K-A*i)//B) % mod
print(ans%mod)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    def comb(a,b):
        return fact[a]*inv_fact[b]*inv_fact[a-b]%mod
    mod = 998244353
    n,a,b,k = LI()
    fact = [1]*(n+1)
    for i in range(1,n+1):
        fact[i] = fact[i-1]*i%mod
    inv_fact = [None]*(n+1)
    inv_fact[n] = pow(fact[n],mod-2,mod)
    for i in range(n)[::-1]:
        inv_fact[i] = inv_fact[i+1]*(i+1)%mod

    ans = 0
    for x in range(n+1):
        if (k-a*x)%b == 0 and k >= a*x and k-a*x <= n*b:
            y = (k-a*x)//b
            ans += comb(n,x)*comb(n,y)%mod
        ans %= mod
    print(ans)

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int

def solve(N: int, A: int, B: int, K: int):
    N_max = 3*10**5
# 元テーブル
    g1 = [1, 1]
# 逆元テーブル
    g2 = [1, 1]
# 逆元テーブル計算用テーブル
    inv = [0, 1]

    for i in range(2, N_max+1):
        g1.append((g1[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        g2.append((g2[-1] * inv[-1]) % MOD)

    ans = 0
    for x in range(N+1):
        if (K-A*x)%B==0:
            y = (K-A*x)//B
            if y<0 or y>N:
                continue
            ans += g1[N]*g2[x]*g2[N-x] * g1[N]*g2[y]*g2[N-y]
            ans %= MOD
    print(ans)

    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, A, B, K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,a,b,k=map(int,input().split())
mod=998244353
factorial=[1]
for i in range(1,n+1):
    factorial.append(factorial[i-1]*i%mod)
inverse=[0]*(n+1)
inverse[-1]=pow(factorial[-1],mod-2,mod)
for i in range(n-1,-1,-1):
    inverse[i]=inverse[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod
ans=0
for i in range(n+1):
    j=(k-a*i)//b
    if a*i+b*j==k and 0<=j<=n:
        ans+=comb(n,i)*comb(n,j)
        ans%=mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353


def get_inv(n):
    inv = [0] * (n + 1)
    inv[1] = 1

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

    return inv


def get_cmb(n):
    inv = get_inv(n)
    cmb = [0] * (n + 1)
    cmb[0] = 1

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

    return cmb


def solve(n, a, b, k):
    ans = 0
    cmb = get_cmb(n)
    for a_num in range(n + 1):
        b_num = (k - a * a_num) // b
        if (a * a_num + b * b_num == k) and (0 <= b_num <= n):
            ans += (cmb[a_num] * cmb[b_num]) % MOD
            ans %= MOD
    return ans


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


main()

Submission status: Accepted

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
def NC(k):
    tmp=(Finv[k]*Finv[N-k])%P
    return (Fact[N]*tmp)%P
ans=0
for s in range(N+1):
    t=(K-s*A)//B
    if s*A+t*B==K and 0<=t<=N:
        ans+=(NC(s)*NC(t))%P
print(ans%P)

Submission status: Accepted

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

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

inverseFactorial=[1]*(N+1)
inverseFactorial[N]=power(Factorial[N],mod-2)
for i in range(0,N)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y:
    return 0
  return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod
      
ans=0  
for i in range(K//A+1):
  if (K-A*i)%B==0:
    j=(K-A*i)//B
    ans+=comb(N,i)*comb(N,j)
    ans%=mod
  

    
print(ans%mod)

Submission status: Accepted

Solution code:
n,a,b,k=map(int,input().split())
mod=998244353
ans=0
fact=[1]*(n+1)
rev=[1]*(n+1)
fx=lambda a,b:(fact[a]*rev[a-b]*rev[b])%mod
for i in range(1,n+1):
    fact[i]=i*fact[i-1]%mod
    rev[i]=pow(fact[i],mod-2,mod)
for i in range(n+1):
    j,r=divmod((k-a*i),b)
    if r==0 and 0<=j<=n:
      ans+=(fx(n,i)*fx(n,j))%mod
print(ans%mod)

Submission status: Accepted

Solution code:
n,a,b,k=map(int,input().split())
mod=998244353
s=0
fact=[1]*(n+1)
rev=[1]*(n+1)

for i in range(1,n+1):
    fact[i]=i*fact[i-1]%mod
    rev[i]=pow(fact[i],mod-2,mod)
fx=lambda a,b:(fact[a]*rev[a-b]*rev[b])%mod

for i in range(n+1):
    j,r=divmod((k-a*i),b)
    if r==0 and 0<=j<=n:
      s+=(fx(n,i)*fx(n,j))%mod

print(s%mod)

Submission status: Accepted

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

MOD = 998244353


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

Fac = [1] * (N+1)
invFac = [1] * (N+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]

pl = []
for a in xrange(N+1):
	b = (K-A*a)//B
	if b < 0 or b > N:
		continue
	if A*a + B*b != K:
		continue
	pl.append((a, b))

# print pl

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

Submission status: Accepted

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)
        s0, s1 = s1, s0-q*s1
        r0, r1 = r1, rtmp
    return s0 % b


# def modInverse2(a, b, divmod=divmod):
#     b2 = b-2
#     tmp0 = a
#     tmp1 = 1
#     while b2 != 0:
#         if b2 & 0b1:
#             tmp1 = tmp1*tmp0
#         tmp0 = tmp0*tmp0 % b
#         b2 = b2 >> 1
#     return(tmp1 % b)


def GCD(a, b):
    r0, r1 = a, b
    while r1 != 0:
        r0, r1 = r1, r0 % r1
    return r0


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


a, b = max(a, b), min(a, b)
gcdab = GCD(a, b)
ahat, bhat = a//gcdab, b//gcdab
flag = False
for i in range(0, bhat+1):
    if (k-i*a) % b == 0:
        iinit = i
        flag = True
        break


if not flag:
    print(0)
    exit()

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

print(ans)

Submission status: Accepted

Solution code:
Q = 998244353
def getInv(N):
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

N, A, B, K = map( int, input().split())
ans = 0
invs = getInv(N)
nCk = [1]*(N+1)
for i in range(1,N+1):
    nCk[i] = (nCk[i-1]*(N-i+1)*invs[i])%Q
for i in range(N+1):
    j = (K-A*i)//B
    if A*i + B*j == K and j <= N and 0 <= j:
        j = (K-A*i)//B
        ans = (ans + nCk[i]*nCk[j])%Q
print(ans)

Submission status: Accepted

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[0] = 1
rC[0] = 1
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: Accepted

Solution code:
n,a,b,k=map(int,input().split())
m=998244353
I=[0]*n
for i in range(n):
  I[i]=pow(i+1,m-2,m)
c=[0]*(n+1)
c[0]=1
for i in range(1,n+1):
  c[i]=(c[i-1]*(n-i+1)*I[i-1])%m
q=0
for i in range(n+1):
  j=(k-i*a)//b
  if (k-i*a)%b or j<0 or j>n:continue
  q=(q+c[i]*c[j])%m 
print(q%m)

Submission status: Accepted

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+1):
  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: Accepted

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 (0 <= (K - i*A) // B <= N):
        ans = (ans + Comb[i]*Comb[(K - i*A) // B]) % NUM 

print(ans)

Submission status: Accepted

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 = (ans + nCr(n,red,MOD,fac,facInv) * nCr(n,blue,MOD,fac,facInv)) % MOD

print(ans)

Submission status: Accepted

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+1):
    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: Accepted

Solution code:
n,a,b,k=map(int,input().split())
mod=998244353
s=0
fac=[1]*(n+1)
rev=[1]*(n+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):
  j,r=divmod((k-a*i),b)
  if r==0 and 0<=j<=n:
    s+=(f(n,i)*f(n,j))%mod

print(s%mod)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# coding: utf-8

MOD = 998244353

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

    return inv

def getCmb(N):
    inv = getInv(N)
    nCr = [0] * (N + 1)
    nCr[0] = 1
    nCr[0] = 1
    
    for i in range(1, N + 1):
        nCr[i] = (nCr[i - 1] * (N - i + 1) * inv[i]) % MOD
    
    return nCr

def solve(N, A, B, K):
    ans = 0
    nCr = getCmb(N)
    for a in range(N + 1):
        b = (K - A * a) // B
        if (A * a + B * b == K) and (0 <= b <= N):
            ans += (nCr[a] * nCr[b]) % MOD
            ans %= MOD
    return ans
    

if __name__ == "__main__":
    N, A, B, K = map(int, input().split())
    print(solve(N,A,B,K))

Submission status: Accepted

Solution code:
fact_list=[None]*300001
inv_fact_list=[None]*300001
fact_list[0]=1
inv_fact_list[0]=1
"""
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(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
for i in range(n+1):
    if k-a*i<0:
        break
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res=(res+comb(n,i)*comb(n,(k-a*i)//b))%998244353
print(res)

Submission status: Accepted

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: Accepted

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 + 1):
    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: Accepted

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 mod_pow(a, n):
    x = 1
    while n > 0:
        if n & 1:
            x = x * a % M

        a = a * a % M
        n >>= 1

    return x


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

    return fact_n[n] * fact_inv[r] * fact_inv[n-r] % 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[n] = pow(fact_n[n], M-2, M)
    for i in range(n-1, 0, -1):
        fact_inv[i] = fact_inv[i+1] * (i+1) % M

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

    print(com % M)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for x in range(N+1):
    y = (K - A * x) / B
    if y.is_integer():
        ans += nCr(N, x) * nCr(N, int(y)) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
MOD = 998244353
fact = [1] * 300001
ifact = [1] * 300001

for i in range(1, 300001):
    fact[i] = (fact[i-1] * i) % MOD
    ifact[i] = pow(fact[i], MOD-2, MOD)

def nCk(n, k):
    if k < 0 or k > n: return 0
    return (fact[n] * ifact[n-k] * ifact[k]) % MOD

N, A, B, K = map(int, raw_input().split())
ab = []
max_a = K // A
max_a = min(max_a, N)
for i in range(max_a+1):
  if ((K-A*i) % B) == 0:
    j = (K-A*i) / B
    if j > N:
      continue
    ab.append([i, j])

total = 0
for a, b in ab:
  total += nCk(N, a) * nCk(N, b)
print(total % MOD)

Submission status: Accepted

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

factorial = [1 for i in range(N + 1)]
inverse = [1 for i in range(N + 1)]
for i in range(1, N + 1):
    factorial[i] = (factorial[i - 1] * i) % mod
    inverse[i] = inverse[i - 1] * pow(i, mod - 2, mod) % mod

com = [1 for i in range(N + 1)]
for i in range(1, N + 1):
    com[i] = (factorial[N] * inverse[i] % mod) * inverse[N - i] % mod

ans = 0
for x in range(N + 1):
    d = K - A * x
    if 0 <= d and d % B == 0:
        y = d // B
        if y <= N:
            ans += com[x] * com[y]
print(ans % mod)

Submission status: Accepted

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

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for x in range(N+1):
    y = (K-A*x)/B
    if y.is_integer():
        ans += nCr(N, x) * nCr(N, int(y)) % mod

print(ans % mod)

Submission status: Accepted

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
    else:
        f, x = divmod(x, bc)
        y += ac * f
    if y > n:
        f = (y - n - 1) // ac + 1
        x += bc * f
        y -= ac * f
    # print(x, y, a * x + b * y)

    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: Accepted

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 + 1):
    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: Accepted

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

mod = 998244353

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for x in range(N+1):
    y = (K-A*x) / B
    if y.is_integer():
        ans += nCr(N, x) * nCr(N, int(y)) % mod

print(ans % mod)

Submission status: Accepted

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+1):
        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: Accepted

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

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for x in range(N+1):
    y = (K-A*x) / B
    if y == int(y):
        ans += nCr(N, x) * nCr(N, int(y)) % mod

print(ans % mod)

Submission status: Accepted

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

a_max =  min(k // a, n) + 1
pair = []
for i in range(a_max):
    if (k - a * i) % b == 0:
        j = (k - a * i) // b
        if j <= n:
            pair.append([i % MOD,j % MOD])

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 r in range(1, n + 1):
    nCr[r] = (nCr[r - 1] * (n - r + 1) * inv[r]) % MOD

result = 0
for p in pair:
    result += (nCr[p[0]] % MOD) * (nCr[p[1]] % MOD)

if result == 0:
    print(1)
else:
    print(result % MOD)

Submission status: Accepted

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

MOD = 998244353

# inv[k]: kの逆元
inv = [0] * (N + 1)
inv[1] = 1
for k in range(2, N + 1):
    inv[k] = (-(MOD // k) * inv[MOD % k]) % MOD

# nCr[r]: C(N, r) % MOD
nCr = [0] * (N + 1)
nCr[0] = 1
for r in range(1, N + 1):
    nCr[r] = (nCr[r - 1] * (N - r + 1) * inv[r]) % MOD

ans = 0
for a in range(N + 1):
    b = (K - A * a) // B
    if A * a + B * b == K and 0 <= b <= N:
        ans += (nCr[a] * nCr[b]) % MOD
        ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import math

base = 998244353

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

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



def comb(n,r):
    hoge = (fac[n] * rev[r] * rev[n - r] ) % base
    return hoge





count = 0

an = 0 

for an in range(n+1):
    if k - an * a < 0 or (k - an * a) % b != 0:
        continue
    bn = (k -an * a) // b
    if not 0 <= bn <= n:
        continue

    count += comb(n, an) * comb(n, bn) % base
    count %= base



print(count)

Submission status: Accepted

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

INV=[None]*(N+1)
for i in range(1,N+1):
    INV[i]=pow(i,mod-2,mod)

Combi=[None]*(N+1)
Combi[0]=1
Combi[1]=N
for i in range(2,N//2+2):
    Combi[i]=Combi[i-1]*(N-i+1)*INV[i] %mod
for i in range(N//2+2,N+1):
    Combi[i]=Combi[N-i]


ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    q, r = divmod(K-(A*i), B)
    if r==0 and q<=N:
        ANS = (ANS+(Combi[i]*Combi[q])%mod)%mod

print(ANS)

Submission status: Accepted

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


mod=998244353
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))


def ncr(n,r):
	if n < 0 or r < 0 or n < r:
		return 0
	else:
		return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod

y=0
ans=0
for x in range(N+1):
	if (K-A*x)%B==0:
		y=(K-A*x)/B
		if x>=0 and y>=0:
			ans+=(ncr(N,x))%mod*(ncr(N,y))%mod

print ans%mod

Submission status: Accepted

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


mod=998244353
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))


def ncr(n,r):
	if n < 0 or r < 0 or n < r:
		return 0
	else:
		return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod

y=0
ans=0
for x in range(N+1):
	if (K-A*x)%B==0:
		if K-A*x<0: break
		y=(K-A*x)/B
		if y>N: continue
		ans+=(ncr(N,x))%mod*(ncr(N,y))%mod

print ans%mod