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:
import sys
sys.setrecursionlimit(1000000)
N, A, B, K = map(int, input().split())
mod = 998244353

def paint(i, k, memo = {}):
    if i == N-1:
        if k in [A, B, A+B, 0]: return 1
        else: return 0
    try:
        return memo[(i, k)]
    except KeyError:
        ans = 0
        for c in [A, B, A+B, 0]:
            ans += paint(i+1, k-c, memo)
            ans %= mod
        memo[(i, k)] = ans
        return ans
memo = {}
print(paint(0, K, memo))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fac
def cc(n,r):
  def fac2(n,r):
    m = 1
    for i in range(n-r+1,n+1):
      m*=i
    return m
  r = min(r,n-r)
  return fac2(n,r)//fac(r)
n, a, b, k = map(int, input().split())
mod = 998244353
ans = 0
for i in range(min(k//a+1,n+1)):
  jof = k-a*i
  if jof%b==0 and jof<=n*b:
    j = jof//b
    ans += cc(n,i)*cc(n,j)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fac
def cc(n,r):
  return fac(n)//fac(r)//fac(n-r)
n, a, b, k = map(int, input().split())
mod = 998244353
ans = 0
for i in range(min(k//a+1,n+1)):
  jof = k-a*i
  if jof%b==0 and jof<=n*b:
    j = jof//b
    ans += cc(n,i)*cc(n,j)%mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

@author: Yamazaki Kenichi
"""

N,A,B,K = map(int,input().split())
mod = 998244353
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,g,b):
    return g1[N]*g2[r]*g2[g]*g2[b]*g2[N-r-g-b]%mod

ans = 0
R = K//A
for i in range(R+1):
    if i == 0:
        if K%B == 0 and K//B <= N:
            ans += a(0,0,K//B)
        continue
    if (K - (A*i)) % B == 0:
        r = i
        b = (K - (A*i)) // B
        g = min(r,b)
        r,b = r-g, b-g
        while r+g+b <=N and g>=0:
            ans += a(r,g,b)
            r,g,b = r+1,g-1,b+1
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 16 15:50:39 2019

@author: Yamazaki Kenichi
"""

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

T = []
R = K//A
for i in range(R+1):
    if i == 0:
        if K%B == 0 and K//B <= N:
            T.append([0,0,K//B,N-K%B])
        continue
    if (K - (A*i)) % B == 0:
        r = i
        b = (K - (A*i)) // B
        g = min(r,b)
        r,b = r-g, b-g
        while r+g+b <=N and g>=0:
            T.append([r,g,b,N-(r+g+b)])
            r,g,b = r+1,g-1,b+1
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)

ans = 0
for c in T:
    ans += g1[N]*g2[c[0]]*g2[c[1]]*g2[c[2]]*g2[c[3]]%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/agc025/tasks/agc025_b

import itertools
import collections
import bisect


# Calculate count of combination
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b


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

    if K == 0:
        print(1)
        exit()

    combi_cache = [0] * (N + 1)
    combi_cache[1] = N
    for i in range(2, N+1):
        combi_cache[i] = combi_cache[i-1] * (N-i+1) // i

    ans = 0
    for a in range(N+1):
        b = (K - a * A) // B
        if A*a + B*b != K or b < 0 or N < b:
            continue

        ans += (combi_cache[a] * combi_cache[b]) % 998244353

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
P=998244353
MAX_N=3*10**5+1
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(MAX_N+1)]
Finv=[0 for i in range(MAX_N+1)]
Fact[0]=1
Finv[0]=1
for i in range(MAX_N):
    Fact[i+1]=(Fact[i]*(i+1))%P
    Finv[i+1]=inv(Fact[i+1])%P
def C(n,k):
    return (Fact[n]*(Finv[k]*Finv[n-k])%P)%P
N,A,B,K=map(int,input().split())
L=[]
for i in range(K//A+1):
    if (K-A*i)%B==0:
        j=(K-A*i)//B
        if 0<=i<=N and 0<=j<=N:
            L.append((i,j))
ans=0
for x,y in L:
    ans+=C(N,x)*C(N,y)
    ans%=P
print(ans)

Submission status: Time Limit Exceeded

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

mod = 998244353
fact = [1] + [0] * n
inv_fact = [0] * (n+1)
for i in range(n):
    fact[i+1] = (fact[i] * (i+1)) % mod

for i in range(n+1):
    inv_fact[i] = pow(fact[i],mod-2,mod)
    
def cb(n, k, mod):
    return (fact[n] * inv_fact[k] * inv_fact[n-k]) % mod

ans = 0
for x in range(n+1):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        if y >= 0:
            if x > n or y > n:
                pass
            else:
                ans += cb(n, x, mod) * cb(n, y, mod)
                ans %= mod
    
print(ans)

Submission status: Time Limit Exceeded

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

mod = 998244353
fact = [1] + [0] * n
inv_fact = [0] * (n+1)
for i in range(n):
    fact[i+1] = (fact[i] * (i+1)) % mod

for i in range(n+1):
    inv_fact[i] = pow(fact[i],mod-2,mod)
    
def cb(n, k, mod):
    return (fact[n] * inv_fact[k] * inv_fact[n-k]) % mod

ans = 0
for x in range(n+1):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        if y >= 0:
            if x > n or y > n:
                pass
            else:
                ans += cb(n, x, mod) * cb(n, y, mod)
                ans %= mod
    
print(ans)

Submission status: Time Limit Exceeded

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

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
    
def mod_combination(N, K, M):
    def mod_permutation(n, k, mod):
        ret = 1
        for i in range(n, n-k, -1):
            ret *= i
            ret %= mod
        return ret

    def mod_inv(k, mod):
        return (pow(k,mod-2,mod))
    
    def mod_inv_permutation(n, k, mod):
        return mod_inv(mod_permutation(n, k, mod), mod)

    return (mod_permutation(N,K,M) * mod_inv_permutation(K, K, M))%M

g = gcd(k, gcd(a, b))
a //= g
b //= g
k //= g

if a < b:
    tmp = a
    a = b
    b = tmp

mod = 998244353
ans = 0
for x in range(max(-int(-(k-b*n)//a),0), k//a+1):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        
        ans += mod_combination(n, x, mod) * mod_combination(n, y, mod)
        ans %= mod
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
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 f(i,j):
  if i>j:
    i,j=j,i
  res=0
  if j<=N:
    for k in range(max(0,i+j-N),i+1):
      t=Factorial[N]
      t=(t*inverseFactorial[i-k])
      t=(t*inverseFactorial[j-k])
      t=(t*inverseFactorial[k])
      t=(t*inverseFactorial[N-i-j+k])%mod
      res+=t
  return res%mod
      
ans=0
g=gcd(A,B)
if K%g==0:
  A,B,K=A//g,B//g,K//g
else:
  print(0)
  exit()
x0,y0=-1,-1
for i in range(K//A+1):
  if (K-A*i)%B==0:
    x0=i
    y0=(K-A*i)//B
    break

for m in range(max(0,(y0-N)//A),min(y0//A+1,(N-x0)//B+1)):
  ans+=f(x0+B*m,y0-A*m)
  ans%=mod
  
    
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
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 f(i,j):
  if i>j:
    i,j=j,i
  res=0
  if j<=N:
    for k in range(max(0,i+j-N),i+1):
      t=Factorial[N]
      t=(t*inverseFactorial[i-k])%mod
      t=(t*inverseFactorial[j-k])%mod
      t=(t*inverseFactorial[k])%mod
      t=(t*inverseFactorial[N-i-j+k])%mod
      res+=t
  return res%mod
      
ans=0
g=gcd(A,B)
if K%g==0:
  A,B,K=A//g,B//g,K//g
else:
  print(0)
  exit()
for i in range(K//A+1):
  if (K-A*i)%B==0:
    x0=i
    y0=(K-A*i)//B
    break

for m in range(max(0,(y0-N)//A),min(y0//A+1,(N-x0)//B+1)):
  ans+=f(x0+B*m,y0-A*m)
  ans%=mod
  
    
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
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 f(i,j):
  if i>j:
    i,j=j,i
  res=0
  if j<=N:
    for k in range(max(0,i+j-N),i+1):
      res+=Factorial[N]*inverseFactorial[i-k]*inverseFactorial[j-k]*inverseFactorial[k]*inverseFactorial[N-i-j+k]
  return res%mod
      
ans=0
g=gcd(A,B)
if K%g==0:
  A,B,K=A//g,B//g,K//g
else:
  print(0)
  exit()
for i in range(K//A+1):
  if (K-A*i)%B==0:
    x0=i
    y0=(K-A*i)//B
    break
m=0
while y0-A*m>=0:
  ans+=f(x0+B*m,y0-A*m)
  ans%=mod
  m+=1
    
print(ans%mod)

Submission status: Time Limit Exceeded

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 f(i,j):
  if i>j:
    i,j=j,i
  res=0
  if j<=N:
    for k in range(max(0,i+j-N),i+1):
        res+=Factorial[N]*inverseFactorial[i-k]*inverseFactorial[j-k]*inverseFactorial[k]*inverseFactorial[N-i-j+k]
  return res%mod
      
ans=0  
for i in range(K//A+1):
  if (K-A*i)%B==0:
    j=(K-A*i)//B
    ans+=f(i,j)
    ans%=mod
    
print(ans%mod)

Submission status: Time Limit Exceeded

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 f(i,j):
  if i>j:
    i,j=j,i
  res=0
  for k in range(i+1):
    if i+j-k<=N:
      res+=Factorial[N]*inverseFactorial[i-k]*inverseFactorial[j-k]*inverseFactorial[k]*inverseFactorial[N-i-j+k]
  return res%mod
      
ans=0  
for i in range(K//A+1):
  if (K-A*i)%B==0:
    j=(K-A*i)//B
    ans+=f(i,j)
    ans%=mod
    
print(ans)

Submission status: Time Limit Exceeded

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

"""
AGC025 B
"""

import itertools
from functools import reduce

cut = 998244353


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


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


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


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


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


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(n, i)*binom(n, ib)) % cut

print(ans)

Submission status: Time Limit Exceeded

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

N, A, B, K = map( int, input().split())
ans = 0
F, R = factorials(N,Q)

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

Submission status: Time Limit Exceeded

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

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

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

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

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


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

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

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

Submission status: Time Limit Exceeded

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

def g(a, b):
    if a<b:
        a, b = b, a
    if b == 0:
        return 1
    c = a%b
    if c == 0:
        return b
    while True:
        a = b%c
        if a == 0:
            return c
        else:
            b = c
            c = a
        
def combine(n, k, key):
    dp = [[0 for j in range(k+1)] for i in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    for i in range(1, n+1):
        temp = min(i+1, k)
        for j in range(1, temp):
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % key
    return dp
        
t = g(g(a, b), k)

at = a//t
bt = b//t
kt = k//t

f = -1
for i in range(bt):
    if (kt - at*i) % bt == 0:
        f = i
        break
        
if f == -1:
    print(0)
else:
    key = 998244353
    ans = 0
    i = f
    dp = combine(n, kt//at, key)
    while at*i <= kt:
        if i > n:
            break
        j = (kt - at*i) // bt
        if j > n:
            continue
        ans += (dp[n][i]*dp[n][j]) % key
        i += bt
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fa
f=lambda a,b:fa(a)//(fa(a-b)*fa(b))
n,a,b,k=map(int,input().split())
v=998244353
l=[]

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

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

print(s)

Submission status: Time Limit Exceeded

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

MOD = 998244353
MAX = n+2

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here
import math
n,a,b,k= map(int,input().split())



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


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

if k == 0:
    c = 1
else:
    for h in range(0,x+1):
        i = (k-a*h)/b

        if i == int(i) and n >= i:
            c = w[h]*w[int(i)]%998244353+c

print(c%998244353)

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here
import math
n,a,b,k= map(int,input().split())



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


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

if k == 0:
    c = 1
else:
    for h in range(0,x+1):
        i = (k-a*h)/b

        if i == int(i) and n >= i:
            c = w[h]*w[int(i)]%998244353+c

print(c%998244353)

Submission status: Time Limit Exceeded

Solution code:

import math
n,a,b,k= map(int,input().split())	
w = []


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


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

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

print(c%998244353)

Submission status: Time Limit Exceeded

Solution code:

import math
n,a,b,k= map(int,input().split())	
def w(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
#コンビネーション


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

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

print(c%998244353)

Submission status: Time Limit Exceeded

Solution code:

import math

li = list(map(int,input().split()))
n = li[0]
k = li[3]
a = max(li[1:3:])
b = min(li[1:3:])
def w(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
#コンビネーション


c = 0

for h in range(0,k//(a+b)+1):
    for i in range(0,(k-(a+b)*h)//a+1):
        j = (k-(a+b)*h-a*i)/b
        if j == int(j) and j >= 0 and n >= h+i+j:
            c = c + w(n,h)*w(n-h,i)*w(n-h-i,j)
if c == 0:
    c = 1

print(c%9982443535)

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

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

Submission status: Time Limit Exceeded

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

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 comb(n,r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    return (((fact_list[n]*inv(n-r))%998244353)*inv(r))%998244353

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

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n+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: Time Limit Exceeded

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

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

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

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n+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)

"""
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
"""

Submission status: Time Limit Exceeded

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

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

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

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n+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: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

def tyoufuku_jyunnretsu(r,g,b,c):
	return math.factorial(r+g+b+c)//(math.factorial(r)*math.factorial(g)*math.factorial(b)*math.factorial(c))

ans = 0

if K==0:
	print(1)
else:
	i_a_count = int(K/A)+1
	i_b_count = int(K/B)+1
	i_ab_count = int(K/(A+B))+1

	for i_a in range(i_a_count):
		for i_b in range(i_b_count):
			for i_ab in range(i_ab_count):
				ans_tmp = i_a*A+i_b*B+i_ab*(A+B)
				if ans_tmp == K and (N-i_a-i_b-i_ab) > -1:
					ans += tyoufuku_jyunnretsu(i_a,i_ab,i_b,N-i_a-i_b-i_ab)
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def c(n,p):
    return math.factorial(n)//(math.factorial(p)*math.factorial(n-p))
N,A,B,K=map(int,input().split())
(A,B)=(min(A,B),max(A,B))
ans=0
for i in range((K//B)+1):
    s=((K-B*i)//A)
    if ((K-B*i)%A)==0 and i<=N and s<=N:
        ans+=c(N,i)*c(N,s)
        ans%=998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def C(N,i,j,k):
    def c(n,p):
        return math.factorial(n)/(math.factorial(p)*math.factorial(n-p))
    return c(N,i)*c(N-i,j)*c(N-i-j,k)  
ans=0
N,A,B,K=map(int,input().split())
t=[A,B,A+B]
s1=range(min(N,K//A)+1)
s2=range(min(N,K//B)+1)
s3=range(min(N,K//(A+B))+1)
from itertools import product
for i,j,k in list(product(s1,s2,s3)):
    if t[0]*i+t[1]*j+t[2]*k==K:
        ans+=C(N,i,j,k)%998244353
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import operator as op
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])

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

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

Submission status: Time Limit Exceeded

Solution code:
n,a,b,k=map(int,input().split())
def kai(n):
    k=1
    s=1
    while k<=n:
        s=(s*k)%998244353
        k=k+1
    return int(s%998244353)

def com(n,m):
    l=((kai(n)%998244353)/((kai(m)%998244353)*(kai(n-m)%998244353)))%998244353
    return int(l)

def rbg(n,a,b,k):
    x=0
    while x<=b:
        if (a*x)%b==k%b:
            y=(k-a*x)/b
            s=0
            while y>=0:
                    c=x+y
                    if c<=n:
                        d=0
                    else:
                        d=c-n
                    e=min(x,y)
                    z=0
                    while d<=e:
                        z=(z+(com(n,d)%998244353)*(com(n-d,x-d)%998244353)*(com(n-x,y-d)%998244353))%998244353
                        d=d+1
                    s=(s+z)%998244353
                    x=x+b
                    y=y-a
            return(s%998244353)
        x=x+1
    return False
print(rbg(n,a,b,k))

Submission status: Time Limit Exceeded

Solution code:
n, A, B, K = map(int, input().strip().split(" "))

P = 998244353

def Pow(a, b):
	ret = 1
	while b :
		if (b & 1) :
			ret = ret * a % P
		a = a * a % P
		b >>= 1
	return ret
	
def C(a, b):
	return L[a] * R[b] * R[a - b] % P

L = [0] * (n + 1)
R = [0] * (n + 1)

L[0] = 1
for i in range(1, n + 1):
	L[i] = L[i-1] * i % P

for i in range(n + 1):
	R[i] = Pow(L[i], P - 2)

ans = 0

for i in range(n + 1):
	j = K - i * A
	if j < 0 or j % B != 0:
		continue
	j //= B 
	
	if j < 0 or j > n:
		continue
	
	ans+= C(n, i) * C(n, j) % P 

print(ans % P)

Submission status: Time Limit Exceeded

Solution code:
n, A, B, K = map(int, input().strip().split(" "))

P = 998244353

def Pow(a, b):
	ret = 1
	while b :
		if (b & 1) :
			ret = ret * a % P
		a = a * a % P
		b >>= 1
	return ret

L = [0] * (n + 1)
R = [0] * (n + 1)

L[0] = 1
for i in range(1, n + 1):
	L[i] = L[i-1] * i % P

for i in range(n + 1):
	R[i] = Pow(L[i], P - 2)

ans = 0
for i in range(2 * n + 1):
	x = i
	if K - x * A < 0 or (K - x * A) % B != 0 :
		continue
	y = (K - x * A) // B
	
	z = max(0, x + y - n)
	x -= z
	y -= z 
	
	if x < 0 or x > n or y < 0 or y > n or z < 0 or z > n:
		continue
	
	for j in range(min(x, y) + 1):
		ans += R[x - j] * R[y - j] * R[z + j] * R[n - x - y - z + j] % P 

ans *= L[n]
print(ans % P)

Submission status: Time Limit Exceeded

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

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

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

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    for green in range(min(a,b) + 1):
        red = a - green
        blue = b - green
        if red + green + blue > N: continue
        tmp = 1
        tmp *= ncr(N, red+green+blue)
        tmp *= ncr(red+green+blue, green+blue)
        tmp *= ncr(green+blue, blue)
        ans += tmp % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

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

fac = [1,1]
finv = [1,1]
inv = [0,1]
for i in range(2,N+10):
    fac.append(fac[i-1] * i % MOD)
    inv.append(-inv[MOD%i] * (MOD // i) % MOD)
    finv.append(finv[i-1] * inv[i] % MOD)

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

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    for green in range(min(a,b) + 1):
        red = a - green
        blue = b - green
        if red + green + blue > N: continue
        tmp = 1
        tmp *= ncr(N, red+green+blue)
        tmp *= ncr(red+green+blue, green+blue)
        tmp *= ncr(green+blue, blue)
        ans += tmp % MOD
print(ans % MOD)