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:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	n,a,b,k=MI()

	m=998244353

	C=[1]
	for i in range(n):
		t=C[-1]*(n-i)*pow(i+1,m-2,m)
		C.append(t%m)
	#print(C)

	ans=0

	for x in range(n+1):
		if (k-a*x)%b==0:
			y=(k-a*x)//b
			if 0<=y<=n:
				ans+=C[x]*C[y]
				ans%=m
	print(ans)

























if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# RGB coloring


import math
mod = 998244353


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def C(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def P(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


def main():
    N, A, B, K = map(int, input().split())
    c = Combi(N, mod)    
    res = 0
    for i in range(N+1):
        if (K-A*i) % B == 0 and K >= A*i:
            res += c.C(N, i)*c.C(N, (K-A*i)//B)
    res %= mod
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 998244353

def main():
    N, A, B, K = map(int, input().split())

    a = [None] * (N+1)
    inva = [None] * (N+1)
    a[0] = 1
    
    for i in range(1, N+1):
        a[i] = i * a[i-1] % m
    
    inva[N] = pow(a[N],m-2,m)
    for i in range(N):
        inva[N-i-1] = inva[N-i] * (N-i) % m

    ans = 0
    for i in range(N+1):
        if (K-A*i) % B == 0:
            j = (K-A*i)//B
            if 0 <= j <= N:
                tmp1 = (a[N] * inva[i] % m) * inva[N-i] % m
                tmp2 = (a[N] * inva[j] % m) * inva[N-j] % m
                ans += tmp1 * tmp2 % m
                ans %= m
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def combs_mod(n,k,mod):
  #nC0からnCkまで
  inv = [1]*(k+1)
  for i in range(1,k+1):
    inv[i] = pow(i,mod-2,mod)
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*inv[i]%mod
  return ans
def solve():
  mod = 998244353
  N, A, B, K = map(int, input().split())
  com = combs_mod(N,N,mod)
  ans = 0
  for x in range(N+1):
    if (K-A*x)%B==0:
      y = (K-A*x)//B
      if y>=0 and y<=N:
        ans += com[x]*com[y]
        ans %= mod
  return ans
print(solve())

Submission status: Accepted

Solution code:
MAX = 3*10**5+100
MOD = 998244353
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
MOD = 998244353

class Factorial:
    def __init__(self, n, mod):
        self.f = f =[0] * (n + 1)
        f[0] = b = 1
        for i in range(1, n + 1):
            f[i] = b = b * i % mod
        self.inv = inv = [0] * (n + 1)
        inv[n] = b = pow(self.f[n], -1, mod)
        for i in range(n, 0, -1):
            inv[i - 1] = b = b * i % mod
        self.mod = mod

    def factorial(self, i):
        return self.f[i]

    def ifactorial(self, i):
        return self.inv[i]

    def C(self, n, k):
        if not 0 <= k <= n: return 0
        return self.f[n] * self.inv[n - k] * self.inv[k] % self.mod

    def P(self, n, k):
        if not 0 <= k <= n: return 0
        return self.f[n] * self.inv[n - k] % self.mod

    def H(self, n, k):
        if (n == 0 and k > 0) or k < 0: return 0
        return self.f[n + k - 1] * self.inv[k] % self.mod * self.inv[n - 1] % self.mod


# pA + qB = K
n, a, b, k = map(int, input().split())
F = Factorial(n, MOD)
c = 0
for p in range(k // a + 1):
    q, _ = divmod(k - p*a, b)
    if _:continue
    c = (c + F.C(n, p) * F.C(n, q)) % MOD
print(c)

Submission status: Accepted

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

# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
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] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,n+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

def func(na,nb):
  if 0<=na<=n and 0<=nb<=n:
    ret=1
    ret*=cmb(n,na,mod)
    ret%=mod
    ret*=cmb(n,nb,mod)
    ret%=mod
    return ret
  else:
    return 0
ans=0
for na in range(n+1):
  if (k-na*a)%b==0:
    ans+=func(na,(k-na*a)//b)
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n,a,b,k=map(int,input().split())
mod=998244353
import math
def lcm(x, y):
  return (x * y) // math.gcd(x, y)
g=math.gcd(a,b)
if k%g!=0:
  print(0)
  exit()
k//=g
a//=g
b//=g

# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
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] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,n+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

def func(na,nb):
  ret=1
  ret*=cmb(n,na,mod)
  ret%=mod
  ret*=cmb(n,nb,mod)
  ret%=mod
  return ret

def func0(na,nb):
  ret=0
  if na<nb:na,nb=nb,na
  for nc in range(min(nb,n)+1):
    # 緑がnc 他がna-nc,nb-nc個ずつ
    reti=1
    if 0<=nc<=n and 0<=na-nc<=n and  0<=nb-nc<=n:
      reti*=g1[n]
      reti%=mod
      reti*=g2[nc]
      reti%=mod
      reti*=g2[na-nc]
      reti%=mod
      reti*=g2[nb-nc]
      reti%=mod
      reti*=g2[n+nc-na-nb]
      reti%=mod
      ret+=reti
  return ret
pat=[]
for i in range(1+k//a):
  if (k-a*i)%b==0:
    pat.append([i,(k-a*i)//b])
    break
na=pat[0][0]
nb=pat[0][1]
while nb-a>=0:
  na+=b
  nb-=a
  pat.append([na,nb])
ans=0
for na,nb in pat:
  if na>n or nb>n:continue
  ans+=func(na,nb)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
mod = 998244353
n, a, b, k = map(int, input().split())
ans = 0
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
for i in range(n + 1):
    x = k - a * i
    if x >= 0 and x % b == 0:
        j = x // b
        if j <= n:
            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())
mod1,mod2=10**9+7,998244353
mod=mod2
fact=[1]*(n+1)
inv=[1]*(n+1)
for i in range(2,n+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod if x>=y>=0 else 0
ans=0
for i in range(n+1):
    if (k-(a*i))%b:continue
    o=(k-(a*i))//b
    ans=(ans+comb(n,i)*comb(n,o)%mod)%mod
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

MOD = 998244353

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

#precompute combination(N, t)
inv = [1, 1]
comb_N = [1, N]
for i in range(2, N//2 + 3):
    inv.append(-inv[MOD%i] * (MOD//i) % MOD)
    comb_N.append(comb_N[-1] * (N-i+1) * inv[i] % MOD)

#reduce A*m + B*n == K to easier one.
g = gcd(A, B)
if K % g != 0:
    print(0)
    exit()

a = A // g
b = B // g
k = K // g

#Solve a*m + b*n == k (m >= 0, n >= 0)
#if (a, b, k) = (5, 11, 83) then the first pair is (m, n) == (10, 3)
for n in range(A):
    if (K - B * n) % A == 0:
        m = (K - B * n) // A
        break

#let m <= N
if m > N:
    times = -((N - m) // b) # == ceil((m-N) / b)
    m -= b * times
    n += a * times

ans = 0
while m >= 0 and n <= N:
    ans += comb_N[min(m, N-m)] * comb_N[min(n, N-n)] % MOD
    ans %= MOD
    m -= b
    n += a
    
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret

N,A,B,K = map(int,input().split())
ans=0
MOD=998244353

F=FactMod(N+1,MOD)

for a in range(N+1):
    Ascore = a*A
    Bscore=K-Ascore
    if Bscore%B==0:
        b=Bscore//B
        if 0<=b<=N:
            ans+=(F.comb(N,a)*F.comb(N,b))%MOD
            ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

### 素数の逆元とCombination

M = 998244353 # 出力の制限
N = n+10 # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

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


def gcd2(a, b):
    """a*x + b*y = gcd(a,b)なるx,yも求める
    """
    l = []
    while b:
        l.append(divmod(a,b))
        a, b = b, a%b
    x, y = 1, 0
    for aa,bb in l[::-1]:
        x, y = y, x - aa*y
    return a, x, y
g,xa,xb = gcd2(a,b)
# xa*a + xb*b = g
if k%g!=0:
    ans = 0
else:
    va, vb = xa*(k//g), xb*(k//g)
    l = a*b//g
    if vb<0:
        tmp = abs(vb)//(l//b) + int(abs(vb)//(l//b)!=0)
        vb += tmp*(l//b)
        va -= tmp*(l//a)
    elif vb>0:
        tmp = abs(vb)//(l//b)
        vb -= tmp*(l//b)
        va += tmp*(l//a)
    init = (va,vb)
    ans = 0
    while va>=0:
#         print(va,vb,va*a + vb*b)
        assert va*a + vb*b == k
        ans += cmb(n, va, M) * cmb(n, vb,M)
        ans %= M
        va -= l//a
        vb += l//b
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=998244353
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,a,b,k=map(int,input().split())
# MOD combination
def cmb(n, r, mod=998244353):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

ans=0
for i in range(n+1):
    aka=i
    if k-aka*a>=0 and (k-aka*a)%b==0:
        ao=(k-aka*a)//b
    else:
        continue
    ans+=cmb(n,aka)*cmb(n,ao)
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n, a, b, k = map(int, input().split())
m = n // 2 + 1
mod = 998244353
comb = [1] * m
for i in range(1, m):
    comb[i] = comb[i - 1] * (n + 1 - i) * pow(i, mod - 2, mod)
    comb[i] %= mod
ans = 0
for i in range(n + 1):
    if a * i > k:
        break
    j = k - a * i
    if j % b == 0:
        j //= b
        if 0 <= j <= n:
            i, j = min(i, n - i), min(j, n - j)
            ans += comb[i] * comb[j]
            ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def comb(n,a,R):
    return (fact[n]*modinv2(fact[n-a]*fact[a],R))

def factinit(n,R):
    global fact
    fact = [1]*(n+1)
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%R


n,a,b,k = inm()
sm = 0
factinit(n,R)
for pq in range(n+1):
    if k<a*pq or (k-a*pq)%b>0:
        continue
    qr = (k-a*pq)//b
    if qr>n:
        continue
    sm = (sm+comb(n,pq,R)*comb(n,qr,R))%R
print(sm)

Submission status: Accepted

Solution code:
###==================================================
### import
#import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip("\n") for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst): print(*lst)
def OutV(lst): print(*lst, sep="\n")
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

## factorial library
## 

## begin library factorial here
## usage: fac = Factorial()
## usage: nCr = fac.comb(n, r)
## usage: nPr = fac.perm(n, r)
class Factorial:

    def __init__(self, N):
        self.fact = [0] * (N+1)
        self.fact_inv = [0] * (N+1)
        self.calc_factorial(N)
        self.calc_inv_factorial(N)

    def calc_factorial(self, N):
        self.fact[0] = 1
        for i in range(N):
            self.fact[i+1] = self.fact[i] * (i+1) % MOD

    def calc_inv_factorial(self, N):
        self.fact_inv[N] = pow(self.fact[N], MOD-2, MOD)
        for i in range(N, 0, -1):
            self.fact_inv[i-1] = self.fact_inv[i] * i % MOD

    def comb(self, n, r):
        if (n < 0 or r < 0 or n < r): return 0
        res = self.fact[n]
        res = res * self.fact_inv[r] % MOD
        res = res * self.fact_inv[n-r] % MOD
        return res

    def perm(self, n, r):
        if (n < 0 or r < 0 or n < r): return 0
        res = self.fact[n]
        res = res * self.fact_inv[r] % MOD
        return res

MOD = 998244353

N, A, B, K = iInM()

fac = Factorial(300000)

ans = 0
for a in range(N+1):
    if (K - A * a) % B == 0:
        b = (K - A * a) // B
        ans = (ans + fac.comb(N, a) * fac.comb(N, b)) % MOD
    else:
        continue

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 998244353
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N,A,B, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    def extgcd1(a0,b0):#計算量log(b0),フェルマーの小定理より早い
        u,v,a,b=1,0,a0,b0
        while b: t=a//b; a-=t*b; a,b=b,a; u,v=v,u-t*v
        if a!=1: return -1#互いに素じゃない
        return u%b0
    
    maxn=N
    fact=[1]*(maxn+1)#NはnCrの最大のn
    ifact=[1]*(maxn+1)
    x=1
    for i in range(2,maxn+1):
        x=(x*i)%mod
        fact[i]=x; ifact[i]=extgcd1(x,mod)
        
    def comb(n,r): return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod
    ans=0
    for i in range(N+1):
        b=K-A*i
        if b<0:break
        d,x=divmod(b,B)
        if x!=0 or d>N:
            continue
        ans+=comb(N,i)*comb(N,d)%mod
        ans%=mod
    print(ans)
        





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.fct[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.fct[i + 1] = self.fct[i] * (i + 1) % mod
        self.inv[n] = pow(self.fct[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod

    def comb(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[k] * self.inv[m - k] % self.mod

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

f = Factorial(N, MOD)

res = 0

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

print(res)

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.fct[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.fct[i + 1] = self.fct[i] * (i + 1) % mod
        self.inv[n] = pow(self.fct[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod

    def comb(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[k] * self.inv[m - k] % self.mod

def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
    while c1:
        a0, a1 = a1, a0 - c0 // c1 * a1
        b0, b1 = b1, b0 - c0 // c1 * b1
        c0, c1 = c1, c0 % c1
    return c0, a0, b0

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

f = Factorial(N, MOD)
c, a, b = ex_euclid(A, B)

if K == 0:
    print(1)

elif K % c != 0:
    print(0)

else:
    lo = -10**18
    hi = 10**18
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if a * K // c + mid * B // c >= 0:
            hi = mid
        else:
            lo = mid
    x0 = a * K // c + hi * B // c

    lo = -10**18
    hi = 10**18
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if b * K // c - mid * A // c >= 0:
            lo = mid
        else:
            hi = mid
    y0 = b * K // c - lo * A // c

    res = 0
    x = x0
    y = (K - A * x0) // B

    while True:
        res += f.comb(N, x) * f.comb(N, y)
        res %= MOD
        if y == y0:
            break
        x += B // c
        y -= A // c

    print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
mod = 998244353

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 3 * 10**5 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

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

red = defaultdict(int)
for i in range(n+1):
    red[i*a] = com(n,i)

ans = 0
for i in range(n+1):
    point = k - b*i
    if(point < 0):
        break
    ans += red[point] * com(n,i)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

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

p = 998244353
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0

for a in range(N+1):
    if (K - A*a) % B == 0 and A*a <= K:
        b = (K- A*a) // B
        ans += cmb(N, a, p)*cmb(N, b, p)%p

print(ans%p)

Submission status: Accepted

Solution code:
M=998244353;n,A,B,K=map(int,input().split());F=[1];a=0
for i in range(n):F+=[F[-1]*(n-i)*pow(i+1,M-2,M)%M]
for i in range(n+1):
 r=K-i*A
 if r%B==0and 0<=r//B<=n:a+=F[i]*F[r//B]
print(a%M)

Submission status: Accepted

Solution code:
M=998244353;n,A,B,K=map(int,input().split());F=[1];a=0
for i in range(n):F+=[F[-1]*(n-i)*pow(i+1,M-2,M)%M]
for i in range(n+1):
 r=K-i*A;q=r//B
 if(r%B==0)&(0<=q<=n):a+=F[i]*F[q]
print(a%M)

Submission status: Accepted

Solution code:
M=998244353;n,A,B,K=map(int,input().split());F=[1];a=0
for i in range(n):F+=[F[-1]*(n-i)*pow(i+1,M-2,M)%M]
for i in range(n+1):
 q,r=divmod(K-i*A,B)
 if(r==0)&(0<=q<=n):a+=F[i]*F[q]
print(a%M)

Submission status: Accepted

Solution code:
M=998244353;n,A,B,K=map(int,input().split());F=[1];a=0
for i in range(n):F+=[F[-1]*(n-i)*pow(i+1,M-2,M)%M]
for i in range(n+1):
 r=K-i*A
 if(r%B==0)&(0<=r//B<=n):a+=F[i]*F[r//B]
print(a%M)

Submission status: Accepted

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
N,A,B,K=map(int,input().split())
p=998244353
fracmod=[1]*(N+1)
fracmodinv=[1]*(N+1)
ans=0
i=0
j=0
for i in range(1,N+1):
    fracmod[i]=(fracmod[i-1]*i)%p
#print(fracmod[:6])
for i in range(N+1):
    fracmodinv[i]=modinv(fracmod[i],p)
for i in range(N+1):
    forb=K-i*A      #bに割く得点
    if (forb%B==0)and(0<=(forb//B)<=N):
        j=forb//B
        #print(i,j)
        ans=(ans+((((fracmod[N]*fracmodinv[N-i]*fracmodinv[i])%p)*(fracmod[N]*fracmodinv[N-j]*fracmodinv[j]))%p))%p
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n,a,b,k=map(int,input().split())
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = n # N は必要分だけ用意する
mod = 998244353
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

ls=[]
res=0
#print(g,numa)
for i in range(n+1):
    #print((k-a*i)%b)
    if (k-a*i)%b==0:
      j= (k-a*i)//b
      #print(a,b,i,j)
      #ls.append((p*numa+i,j))
      if j<=n:
        ls.append((i,j))
#print(ls)
for tup in ls:
  res+=cmb(n,tup[0])*cmb(n,tup[1])
  #print(res)
print(res%mod)

Submission status: Accepted

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

MAX = 3 * 10 ** 5

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = (fact[i-1] * i) % mod

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

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


ans = 0
for ea in range(n + 1):
    ebb = k - ea * a
    if ebb % b == 0:
        eb = ebb // b
        if 0 <= eb <= n:
            ans += comb(n, ea) * comb(n, eb)
            ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

N, A, B, K = map(int, input().split())
if K == 0:
    print(1)
    exit()
c = gcd(A, B)
if K % c != 0:
    print(0)
    exit()
A //= c; B //= c; K //= c
mod = 998244353

fact = [1] * (N+1)
fact_inv = [1] * (N+1)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[N] = pow(fact[N], mod-2, mod)
for i in range(1, N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

ans = 0
for x in range(N+1):
    y, r = divmod(K - A * x, B)
    if r != 0:
        continue
    if 0 <= y <= N:
        ans = (ans + comb(N, x) * comb(N, y)) % mod
print(ans)

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

mod = 998244353 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

N,A,B,K = map(int, input().split())
ans = 0
for i in range(N+1):
  if (K-A*i)%B!=0:
    continue
  j = (K-A*i)//B
  m = cmb(N,i,mod)*cmb(N,j,mod)%mod
  ans += m
  ans %= mod
print(ans)

Submission status: Accepted

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

def cmb1(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

mod = 998244353 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

ans = 0
for i in range(n+1):
    x = a*i
    y = k-x
    if y < 0:
        continue
    if y%b == 0:
        j = y//b
        ans += cmb1(n, i, mod)*cmb1(n, j, mod)
print(ans%mod)

Submission status: Accepted

Solution code:
N, A, B, K = map(int, input().split())
mod = 998244353
# AとBの組み合わせと、(A+B)と0の組み合わせが可換
# 順番というよりは個数の組み合わせがどうなるかの問題？
# 赤と青の個数の組み合わせは、(無色も含める？)


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]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル


for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)
ans = 0
for i in range(N+1):
    D = (K - A*i)
    if D % B == 0 and D//B <= N:
        ans += cmb(N, i, mod) * cmb(N, D//B, mod)
        ans %= mod

print(ans)