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: Time Limit Exceeded

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

fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,n+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

def nPr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[n-r]%mod


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

Submission status: Time Limit Exceeded

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

fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,n+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

def nPr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[n-r]%mod

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

Submission status: Time Limit Exceeded

Solution code:
# ボールAとボールBをN個の箱に入れる
# A,Bを1つずつ同じ箱に入れることがあってもよい。
# まずAをN個の箱に1つずつ入れる
# その上で、BをN個の箱に1つずつ入れる（すでにAが入っているかどうか、区別する必要がない）
# AとBの個数の組み合わせを列挙し、そのすべてについて(N C (Aの個数)) * (N C (Bの個数))を計算した和が答え

import sys
readline = sys.stdin.readline

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

DIV = 998244353
n = (10 ** 6) * 2 # PyPyじゃないと通らない。 * 5が限界くらい
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

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

# AとBを足してKになる組み合わせを探索する
ans = 0
for a in range(N + 1):
  rest = K - a * A
  if rest < 0:
    break # a * Aの時点で負の数。これ以上の探索も不要。
  if rest % B != 0:
    continue # 組み合わせを作れない
  b = rest // B
  if b > N:
    continue # 箱に入れられない
  # この時点で、Aがa個とBがb個で作れることが確定する
  # (N C (Aの個数)) * (N C (Bの個数))
  ans += (nCr(N, a, DIV) * nCr(N, b, DIV)) % DIV
  ans %= DIV
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ボールAとボールBをN個の箱に入れる
# A,Bを1つずつ同じ箱に入れることがあってもよい。
# まずAをN個の箱に1つずつ入れる
# その上で、BをN個の箱に1つずつ入れる（すでにAが入っているかどうか、区別する必要がない）
# AとBの個数の組み合わせを列挙し、そのすべてについて(N C (Aの個数)) * (N C (Bの個数))を計算した和が答え

import sys
readline = sys.stdin.readline

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

DIV = 998244353
n = (10 ** 6) * 2 # PyPyじゃないと通らない。 * 5が限界くらい
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

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

# AとBを足してKになる組み合わせを探索する
ans = 0
for a in range(N + 1):
  b = K - a * A
  if b < 0:
    break # a * Aの時点で負の数。これ以上の探索も不要。
  if b % B != 0:
    continue # 組み合わせを作れない
  if (b // B) > N:
    continue # 箱に入れられない
  # この時点で、Aがa個とBがb個で作れることが確定する
  # (N C (Aの個数)) * (N C (Bの個数))
  ans += (nCr(N, a, DIV) * nCr(N, b // B, DIV)) % DIV
  ans %= DIV
  
print(ans)

Submission status: Time Limit Exceeded

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)%b>0:
        continue
    qr = (k-a*pq)//b
    if qr>n:
        continue
    q1 = max(0,pq+qr-n)
    q2 = min(pq,qr)
    for q in range(q1,q2+1):
        p = pq-q
        r = qr-q
        s = n-p-q-r
        sor = ((fact[p]*fact[q]%R)*(fact[r]*fact[s]%R))%R
        sm = (sm+fact[n]*modinv2(sor,R))%R
print(sm)

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb
n,a,b,k=map(int,input().split())
A=0
m=998244353
for i in range(n+1):
 if (k-i*a)%b==0:A+=comb(n,i,exact=True)*comb(n,(k-i*a)//b,exact=True)%m
print(A%m)

Submission status: Time Limit Exceeded

Solution code:
# 拡張ユークリッド互除法
# gcd(a,b) と ax + by = gcd(a,b) の最小整数解を返す
def extgcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = extgcd(b % a, a)
        return g, x - (b // a) * y, y

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    gcd, x, y = extgcd(a,m)
    return (m+x%m)%m



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

mod = 998244353
ans = 0
for a in range(N+1):
    if (K - A*a) % B == 0 and A*a <= K:
        b = (K- A*a) // B
        res_a = 1
        for i in range(1,N+1):
            res_a = res_a*i%mod
        for i in range(1,a+1):
            res_a = res_a*mod_inv(i,mod)%mod
        for i in range(1,(N-a)+1):
            res_a = res_a*mod_inv(i,mod)%mod
        res_b = 1
        for i in range(1,N+1):
            res_b = res_b*i%mod
        for i in range(1,b+1):
            res_b = res_b*mod_inv(i,mod)%mod
        for i in range(1,(N-b)+1):
            res_b = res_b*mod_inv(i,mod)%mod
        ans += res_a*res_b%mod

print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


ans = 0
for x in range(N+1):
    if (K - A * x) % B != 0:
        continue
    y = (K - A * x) // B
    tmp = 0
    for g in range(max(0, x + y - N), min(x, y, N)+1):
        r = x - g
        b = y - g
        if r < 0 or b < 0:
            break
        tmp = (tmp + fact_inv[r] * fact_inv[b] * fact_inv[g] * fact_inv[N - r - g - b]) % mod
    ans = (ans + tmp) % mod
ans = ans * fact[N] % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a,b,k=map(int,input().split())
mod=998244353
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
ans=0
for ac in range(k//a+1):
  asum=ac*a
  if (k-asum)%b:continue
  bc=(k-asum)//b
  if max(ac,bc)>n:continue
  ans=(ans+comb(n,ac)*comb(n,bc))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, A, B, K = lr()
answer = 0
# A * x + B * y = K
# nCx * nCy



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

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = N + 100 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

for x in range(N+1):
    temp = K-A*x
    if temp%B != 0:
        continue
    y = temp // B
    if y > N:
        continue
    if y < 0:
        break
    answer += cmb(N, x) * cmb(N, y)
    answer %= MOD

print(answer % MOD)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, A, B, K = lr()
answer = 0
# A * x + B * y = K
# nCx * nCy



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

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 6 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

for x in range(N+1):
    temp = K-A*x
    if temp%B != 0:
        continue
    y = temp // B
    if y > N:
        continue
    if y < 0:
        break
    answer += cmb(N, x) * cmb(N, y)
    answer %= MOD

print(answer % MOD)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, A, B, K = lr()
answer = 0
# A * x + B * y = K
# nCx * nCy

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

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

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 6 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

for x in range(K//A+1):
    temp = K-A*x
    if temp%B != 0:
        continue
    y = temp // B
    if y > N:
        continue
    if y < 0:
        break
    answer += cmb(N, x) * cmb(N, y)
    answer %= MOD

print(answer % MOD)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, A, B, K = lr()
answer = 0
# A * x + B * y = K
# nCx * nCy

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

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

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 6 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

for x in range(K//A+1):
    temp = K-A*x
    if temp%B != 0:
        continue
    y = temp // B
    answer += cmb(N, x) * cmb(N, y)
    answer %= MOD

print(answer % MOD)
#

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

mod = 998244353

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

ans = 0
for i in range(n+1):
    Num = (k-a*i)
    if (0 <= Num//b) and (Num//b <= n) and (Num%b == 0):
      j = Num//b
      ans += comb(n, i, exact=True) * comb(n, j, exact=True)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
  
def comb(n, r):
    if 2*r > n: return comb(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % mod

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

fac = [1] * (n+2)
inv = [1] * (n+2)
for i in range(2, n+1):
    fac[i] = fac[i-1] * i % mod
inv[n] = pow(fac[n], mod-2, mod)
for i in range(n-1, 1, -1):
    inv[i] = inv[i+1] * (i+1) % mod
    
ans = 0
for i in range(n+1):
    for j in range(n+1):
        if a*i + b*j > k: break
        if a*i + b*j == k:
          ans += comb(n, i) * comb(n, j)
print(ans % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

MOD = 998244353 # prime
fact_inv, inv = [0]*10**6, [0]*10**6

def init_nCk():
    fact_inv[0] = fact_inv[1] = 1
    inv[1] = 1
    for i in range(2,10**6):
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        fact_inv[i] = fact_inv[i-1] * inv[i] % MOD

def nCk(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    ans = 1
    for i in range(n, n-k+1 - 1, -1):
        ans *= i
        ans %= MOD
    return ans * fact_inv[k] % MOD

# WAKARAN
res = 0
init_nCk()
for a in range(0,N+1):
    # 割り切れることを確認
    if (K - A*a)%B == 0 and (K -A*a)//B >= 0:
        b = (K -A*a)//B
        res += nCk(N,a)*nCk(N,b)
        res %= MOD
print(res)

Submission status: Time Limit Exceeded

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

MOD = 998244353 # prime
fact_inv, inv = [0]*10**6, [0]*10**6

def init_nCk():
    fact_inv[0] = fact_inv[1] = 1
    inv[1] = 1
    for i in range(2,10**6):
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        fact_inv[i] = fact_inv[i-1] * inv[i] % MOD

def nCk(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    ans = 1
    for i in range(n, n-k+1 - 1, -1):
        ans *= i
        ans %= MOD
    return ans * fact_inv[k] % MOD

res = 0
init_nCk()
for a in range(0,N+1):
    # 割り切れることを確認
    if (K - A*a)%B == 0 and (K -A*a)//B >= 0:
        b = (K -A*a)//B
        res += nCk(N,a)*nCk(N,b)
        res %= MOD
print(res)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy


N,A,B,K=map(int,input().split())
mod=998244353
Fac=[0 for i in range(N+1)]
iFac=[0 for i in range(len(Fac))]
Fac[0]=1
Fac[1]=1
for i in range(2,N+1):
    Fac[i]=i*Fac[i-1]%mod
for i in range(N+1):
    iFac[i]=pow(Fac[i],mod-2,mod)
lst=[]
for a in range(N+1):
    value=(K-a*A)
    if value%B==0:
        lst.append([a,value//B])

def comb(x,y):
    if x==0 or y==0:
        return(1)
    else:
        return(Fac[x]*iFac[x-y]%mod*iFac[y]%mod)



count=0
for a,b in lst:
    for i in range(max(a+b-N,0),min(a,b)+1):
        count+=iFac[a-i]*iFac[b-i]%mod*iFac[i]%mod*iFac[N-a-b+i]%mod
        count%=mod
count*=Fac[N]
count%=mod
print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy


N,A,B,K=map(int,input().split())
mod=998244353
Fac=[0 for i in range(N+1)]
iFac=[0 for i in range(len(Fac))]
Fac[0]=1
Fac[1]=1
for i in range(2,N+1):
    Fac[i]=i*Fac[i-1]%mod
for i in range(N+1):
    iFac[i]=pow(Fac[i],mod-2,mod)
lst=[]
for a in range(N+1):
    value=(K-a*A)
    if value%B==0:
        lst.append([a,value//B])

def comb(x,y):
    if x==0 or y==0:
        return(1)
    else:
        return(Fac[x]*iFac[x-y]%mod*iFac[y]%mod)



count=0
for a,b in lst:
    for i in range(max(a+b-N,0),min(a,b)+1):
        count+=Fac[N]*iFac[a-i]%mod*iFac[b-i]%mod*iFac[i]%mod*iFac[N-a-b+i]%mod
        count%=mod

print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy


N,A,B,K=map(int,input().split())
mod=998244353
Fac=[0 for i in range(N+1)]
iFac=[0 for i in range(len(Fac))]
Fac[0]=1
Fac[1]=1
for i in range(2,N+1):
    Fac[i]=i*Fac[i-1]%mod
for i in range(N+1):
    iFac[i]=pow(Fac[i],mod-2,mod)
lst=[]
for a in range(N+1):
    value=(K-a*A)
    if value%B==0:
        lst.append([a,value//B])

def comb(x,y):
    if x==0 or y==0:
        return(1)
    else:
        return(Fac[x]*iFac[x-y]%mod*iFac[y]%mod)


count=0
for a,b in lst:
    for i in range(0,min(a,b)+1):
        if a+b-i<=N:
            count+=Fac[N]*iFac[a-i]%mod*iFac[b-i]%mod*iFac[i]%mod*iFac[N-a-b+i]%mod
            count%=mod
        #if i<=50000:

        #    count+=comb(N,a-i) * comb(N-(a-i),b-i)  * comb(N-(a-i)-(b-i),i)

print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy


N,A,B,K=map(int,input().split())
mod=998244353
Fac=[0 for i in range(N+1)]
iFac=[0 for i in range(len(Fac))]
Fac[0]=1
Fac[1]=1
for i in range(2,N+1):
    Fac[i]=i*Fac[i-1]%mod
for i in range(N+1):
    iFac[i]=pow(Fac[i],mod-2,mod)
lst=[]
for a in range(N+1):
    value=(K-a*A)
    if value%B==0:
        lst.append([a,value//B])

def comb(x,y):
    if x==0 or y==0:
        return(1)
    else:
        return(Fac[x]*iFac[x-y]%mod*iFac[y]%mod)


count=0
for a,b in lst:
    for i in range(0,min(a,b)+1):
        #count+=Fac[N]*iFac[a-i]%mod*iFac[b-i]%mod*iFac[i]%mod*iFac[N-a-b+i]%mod
        #if i<=50000:
        if a+b-i<=N:
            count+=comb(N,a-i) * comb(N-(a-i),b-i)  * comb(N-(a-i)-(b-i),i)
            count%=mod
print(count)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
rng = 300100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)

def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*pow(fctr[n-k],mod-2,mod)*pow(fctr[k],mod-2,mod)%mod
n,a,b,k = map(int,input().split())
pair = []
for i in range(n+1):
  if (k-a*i)%b == 0 and (k-a*i)//b <= n:
    pair.append((i,(k-a*i)//b))
ans = 0
for x,y in pair:
  ans = (ans+cmb(n,x)*cmb(n,y))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
rng = 300100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
n,a,b,k = map(int,input().split())
pair = []
for i in range(n+1):
  if (k-a*i)%b == 0 and (k-a*i)//b <= n:
    pair.append((i,(k-a*i)//b))
ans = 0
for x,y in pair:
  ans = (ans+cmb(n,x)*cmb(n,y))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, A, B, K = map(int, input().split())
maxAB = max(A, B)
minAB = min(A, B)
ans = 0


def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return fac[n] * finv[r] * finv[n-r] % mod


mod = 998244353  # 問題によって変える、ここは素数でないとうまく動かない
N_cmb = 0
N_cmb += N  # 入力の制約によって変えるところ、nCrの計算で欲しいnの最大値
fac = [1, 1]  # 階乗テーブル
finv = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for ZZZ in range(2, N_cmb + 1):
    fac.append((fac[-1] * ZZZ) % mod)
    inverse.append(mod-inverse[mod % ZZZ]*(mod//ZZZ) % mod)
    finv.append((finv[-1] * inverse[-1]) % mod)

for i in range(N+1):
    j = (K - maxAB * i) // minAB
    if (K - maxAB * i) % minAB == 0 and 0 <= j <= N:
        #print(i, j)
        for h in range(min(i, j)+1):
            if i + j - h <= N:
                #print(cmb(N, h), cmb(N - h, i - h), cmb(N - i, j - h))
                ans += ((cmb(N, h) * cmb(N - h, i - h)) %
                        mod) * cmb(N - i, j - h)
                ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 998244353

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

def gcd(a, b):
    if a > b:
        a, b = b, a
    if b % a == 0:
        return a
    return gcd(b % a, a)

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

if A < B:
    A, B = B, A

# n = 2 * min(K // A + 2, N + 1) + 3
n = min((K + A - 1) // A, N) + 1
lcm = A * B // gcd(A, B)
step = lcm // A

lst = Factorial(N + 1, MOD) #O(N)
N_factrorial = lst.factorial(N)
ilst = np.array(lst.i, dtype = np.int64)

def calc(a, b):
    if a > b:
        a, b = b, a #必ずaのほうが小さくなる
    tmp = 0
    G = min(a, b) #緑色の最大値
    # print ('a=', a, 'b=', b)
    # print ('G=', G)
    if a == b:
        if N - a - b >= 0:
            tmp = sum(((ilst[a: : -1] * ilst[b:: -1] % MOD) * ilst[0: G + 1] % MOD) * ilst[N - a - b: N - a - b + G + 1] % MOD) % MOD
            tmp *= N_factrorial
        else:
            n = a + b - N #少なくともn枚は緑色を作らないとだめ
            # print (n)
            if n > G:
                # print ('&')
                return 0            # print (n)
            tmp = sum(((ilst[a - n: :-1] * ilst[b - n: : -1] % MOD) * ilst[n: G + 1] % MOD) * ilst[0: N - a - b + G + 1] % MOD) % MOD
            tmp *= N_factrorial
    elif N - a - b >= 0:
        # print ('Y')
        # print (ilst[a: : -1])
        # print (ilst[b: b - G - 1: -1])
        # print (ilst[0: G + 1])
        # print (ilst[N - a - b: N - a - b + G + 1])
        tmp = sum(((ilst[a: : -1] * ilst[b: b - G - 1: -1] % MOD) * ilst[0: G + 1] % MOD) * ilst[N - a - b: N - a - b + G + 1] % MOD) % MOD
        tmp *= N_factrorial
    else:
        # print ('N')
        n = a + b - N #少なくともn枚は緑色を作らないとだめ
        # print (n)
        if n > G:
            # print ('&')
            return 0
        # print (n)
        tmp = sum(((ilst[a - n: :-1] * ilst[b - n: b - G - 1: -1] % MOD) * ilst[n: G + 1] % MOD) * ilst[0: N - a - b + G + 1] % MOD) % MOD
        tmp *= N_factrorial
    # print ('tmp=', tmp)
    tmp %= MOD
    return tmp

def count(a, b):
    if a + b > 2 * N:
        return 0
    # print ('to calc')
    return calc(a, b)

def maike_satrt(step):
    for i in range(step):
        if (K - A * i) % B == 0:
            return i

start = maike_satrt(step)
# print (start, n)
ans = 0
for a in range(start, n, step): #Aの数
    if A * a > K:
        break
    # if (K - A * a) % B != 0:
    #     continue
    b = (K - A * a) // B
    # print ('a=', a, 'b=', b)
    ans += count(a, b)
    ans %= MOD

print (ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

def gcd(a, b):
    if a > b:
        a, b = b, a
    if b % a == 0:
        return a
    return gcd(b % a, a)

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

if A < B:
    A, B = B, A

# n = 2 * min(K // A + 2, N + 1) + 3
n = min((K + A - 1) // A, N) + 1
lcm = A * B // gcd(A, B)
step = lcm // A

lst = Factorial(N + 1, MOD) #O(N)
N_factrorial = lst.factorial(N)

def calc(a, b):
    tmp = 0
    G = min(a, b) #緑色の最大値
    # print ('G=', G)
    for green in range(G, -1, -1):
        red = a - green
        blue = b - green
        none_color = N - red - green - blue
        # print (red, green, blue, none_color)
        if none_color < 0:
            break
        tmp += ((((N_factrorial * lst.ifactorial(red) % MOD) * lst.ifactorial(green) % MOD) * lst.ifactorial(blue) % MOD) * lst.ifactorial(none_color) % MOD)
        tmp %= MOD
    # print ('tmp=', tmp)
    return tmp

def count(a, b):
    if a + b > 2 * N:
        return 0
    # print ('to calc')
    return calc(a, b)

def maike_satrt(step):
    for i in range(step):
        if (K - A * i) % B == 0:
            return i

start = maike_satrt(step)

ans = 0
for a in range(start, n, step): #Aの数
    if A * a > K:
        break
    # if (K - A * a) % B != 0:
    #     continue
    b = (K - A * a) // B
    # print ('a=', a, 'b=', b)
    ans += count(a, b)
    ans %= MOD

print (ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0


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

if A < B:
    A, B = B, A

# n = 2 * min(K // A + 2, N + 1) + 3
n = min((K + A - 1) // A, N) + 1

lst = Factorial(N + 1, MOD) #O(N)
N_factrorial = lst.factorial(N)

def calc(a, b):
    tmp = 0
    G = min(a, b) #緑色の最大値
    # print ('G=', G)
    for green in range(G, -1, -1):
        red = a - green
        blue = b - green
        none_color = N - red - green - blue
        # print (red, green, blue, none_color)
        if none_color < 0:
            break
        tmp += ((((N_factrorial * lst.ifactorial(red) % MOD) * lst.ifactorial(green) % MOD) * lst.ifactorial(blue) % MOD) * lst.ifactorial(none_color) % MOD)
        tmp %= MOD
    # print ('tmp=', tmp)
    return tmp

def count(a, b):
    if a + b > 2 * N:
        return 0
    # print ('to calc')
    return calc(a, b)

ans = 0
for a in range(n): #Aの数
    if A * a > K:
        break
    if (K - A * a) % B != 0:
        continue
    b = (K - A * a) // B
    # print ('a=', a, 'b=', b)
    ans += count(a, b)
    ans %= MOD

print (ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0


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

if A < B:
    A, B = B, A

n = 2 * min(K // A + 2, N + 1) + 3

lst = Factorial(N + 1, MOD) #O(N)
N_factrorial = lst.factorial(N)
l_ifactorial = lst.ifactorial

def calc(a, b):
    tmp = 0
    G = min(a, b) #緑色の最大値
    # print ('G=', G)
    for green in range(G, -1, -1):
        red = a - green
        blue = b - green
        none_color = N - red - green - blue
        # print (red, green, blue, none_color)
        if none_color < 0:
            break
        tmp += ((((N_factrorial * l_ifactorial(red) % MOD) * l_ifactorial(green) % MOD) * l_ifactorial(blue) % MOD) * l_ifactorial(none_color) % MOD)
        tmp %= MOD
    return tmp

def count(a, b):
    if a + b > 2 * N:
        return 0
    # print ('to calc')
    return calc(a, b)

ans = 0
for a in range(n): #Aの数
    if A * a > K:
        break
    if (K - A * a) % B != 0:
        continue
    b = (K - A * a) // B
    # print ('a=', a, 'b=', b)
    ans += count(a, b)
    ans %= MOD

print (ans)