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 = tuple(map(int, (input().split())))
mod = 998244353

def ab(n):
    ab = []
    a = n // A
    while (n - A * a) % B != 0:
        a -= 1
    b = (n - A * a) // B
    ab.append((a, b))
    while a > 0:
        a, b = a - B // gcd(A, B), b + A // gcd(A, B)
        if a < 0:
            break
        ab.append((a, b))
    return ab

def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    return gcd(b, a - b * (a // b))

def mpow(x, n):
    ans = 1
    while n != 0:
        if n & 1:
            ans = ans * x % mod
        x = x * x % mod
        n = n >> 1
    return ans

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

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

ans = 0
for a, b in ab(K):
    if a > N or b > N:
        continue
    ans += com[a] * com[b]
print(ans % mod)

Submission status: Time Limit Exceeded

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

import sys, math, copy
from functools import lru_cache
sys.setrecursionlimit(10 ** 6)

MOD = 998244353
HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

facts = [1]
for i in range(1, 300001):
    facts.append(facts[i - 1] * i % MOD)

@lru_cache(maxsize=10 ** 6)
def comb(n, k):
    # nCk mod p
    p = MOD
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = facts[n]
    b = facts[k]
    c = facts[n - k]
    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

def main():
    n, a, b, k = map(int, input().split())
    # print(n, a, b, k)
    res = 0
    for i in range(0, n + 1):
        residual = k - a * i
        if residual < 0:
            continue
        if residual % b > 0:
            continue
        j = residual // b
        res += comb(n, i) * comb(n, j)
        res %= MOD
    print(res)

main()

Submission status: Time Limit Exceeded

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

import sys, math, copy
from functools import lru_cache
# import fractions, itertools
# import numpy as np
# import scipy
sys.setrecursionlimit(10 ** 6)

MOD = 998244353
HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

# @lru_cache(maxsize=3 * 10 ** 5)
# def fact(i):
#     if i <= 1:
#         return 1
#     return i * fact(i - 1) % MOD

facts = [1]
for i in range(1, 300001):
    facts.append(facts[i - 1] * i % MOD)

# 
# def combi(n, i):
#     return fact(n) // (fact(i) * fact(n - i))

# @lru_cache(maxsize=10 ** 6)
def comb(n, k):
    # nCk mod p
    p = MOD
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = facts[n]
    b = facts[k]
    c = facts[n - k]
    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

def main():
    n, a, b, k = map(int, input().split())
    # print(n, a, b, k)
    res = 0
    for i in range(0, n + 1):
        residual = k - a * i
        if residual < 0:
            continue
        if residual % b > 0:
            continue
        j = residual // b
        res += comb(n, i) * comb(n, j)
        res %= MOD
    print(res)

main()

Submission status: Time Limit Exceeded

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

import sys, math, copy
from functools import lru_cache
# import fractions, itertools
# import numpy as np
# import scipy
sys.setrecursionlimit(10 ** 6)

MOD = 998244353
HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

# @lru_cache(maxsize=10 ** 6)
# def fact(i):
#     if i <= 1:
#         return 1
#     return i * fact(i - 1) % MOD
# 
# def combi(n, i):
#     return fact(n) // (fact(i) * fact(n - i))

@lru_cache(maxsize=10 ** 6)
def comb(n, k):
    # nCk mod p
    p = MOD
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = math.factorial(n) % p
    b = math.factorial(k) % p
    c = math.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

def main():
    n, a, b, k = map(int, input().split())
    # print(n, a, b, k)
    res = 0
    for i in range(0, n + 1):
        residual = k - a * i
        if residual < 0:
            continue
        if residual % b > 0:
            continue
        j = residual // b
        res += comb(n, i) * comb(n, j)
        res %= MOD
    print(res)

main()

Submission status: Time Limit Exceeded

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

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


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

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


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

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

    print(com % M)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
DIV_NUM = 998244353

def comb(c, d):
    t = 1
    u = 1
    for p in range(d):
        t *= (c - p)
        u *= (p + 1)
    return ( t // u ) % DIV_NUM


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

result = 0

i = 0
j = 0
for i in range(n + 1):
    if k < a * i:
        break
    if ( k - a * i ) % b == 0:
        j = ( k - a * i ) // b
        result += comb(n, i) * comb(n, j) % DIV_NUM

print(result)

Submission status: Time Limit Exceeded

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

mod = 998244353
F = [1]
RF = []


def inv(x):
    res = 1
    k = mod - 2
    y = x
    while k:
        if k & 1:
            res = (res * y) % mod
        y = (y * y) % mod
        k //= 2
    return res


def init():
    for i in range(N):
        F.append((F[i] * (i + 1)) % mod)
    for i in F:
        RF.append(inv(i))


def comb(x, y):
    if y < 0 or x < y:
        return 0
    return (F[x] * ((inv(F[x - y]) * inv(F[y])) % mod)) % mod


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

Submission status: Time Limit Exceeded

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

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


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

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


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

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

    print(com % M)

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

MOD = 998244353
mod_inv_dp = [0, 1]


def mod_inv(n):
    if len(mod_inv_dp) >= n + 1:
        return mod_inv_dp[n]
    else:
        ans = MOD - (MOD // n) * mod_inv(MOD % n) % MOD
        mod_inv_dp.append(ans)
        return ans


def nCr(n, r):
    r = min(r, n - r)
    ans = 1
    for i in range(n, n - r, -1):
        ans = (ans * i) % MOD
    for i in range(1, r + 1):
        ans = mod_inv(i) * ans % MOD
    return ans


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


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

    gcdab = gcd(a, b)
    solutions = []

    if n==0:
        print(1)
        return

    if k % gcdab != 0:
        print(0)
        return

    for x in range(0, n + 1):
        yb = k - a*x
        if yb >= 0 and yb % b == 0: # and x + yb//b <= n:
            solutions.append([x, yb // b])

    ways = 0
    for x, y in solutions:
        for z in range(0, min(x, y) + 1):
            ways += nCr(n, z) * nCr(n - z, x - z) * nCr(n - x, y - z)
            ways %= MOD

    print(ways)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

MOD = 998244353

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

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

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

ab_patterns = []
max_a = K // A
for a_count in range(max_a + 1):
    remaining = K - A * a_count
    if remaining % B == 0:
        b_count = remaining // B
        ab_patterns.append((a_count, b_count))

ans = 0
for a_count, b_count in ab_patterns:
    for n_greens in range(min(a_count, b_count), -1, -1):
        n_reds = a_count - n_greens
        n_blues = b_count - n_greens
        if n_greens + n_reds + n_blues > N:
            break
        n_nocolors = N - n_reds - n_greens - n_blues
        result = (f[N] * finv[n_greens] * finv[n_reds] * finv[n_blues] * finv[n_nocolors]) % MOD
        ans += result
        ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 998244353

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

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

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

ab_patterns = []
max_a = K // A
for a_count in range(max_a + 1):
    remaining = K - A * a_count
    if remaining % B == 0:
        b_count = remaining // B
        ab_patterns.append((a_count, remaining // B))

ans = 0
for a_count, b_count in ab_patterns:
    result = None
    for n_greens in range(min(a_count, b_count), -1, -1):
        n_reds = a_count - n_greens
        n_blues = b_count - n_greens
        if n_greens + n_reds + n_blues > N:
            break
        n_nocolors = N - n_reds - n_greens - n_blues
        result = (f[N] * finv[n_greens] * finv[n_reds] * finv[n_blues] * finv[n_nocolors]) % MOD
        ans += result
        if ans > MOD:
            ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

ab_patterns = []
max_a = K // A
for a_count in range(max_a + 1):
    remaining = K - A * a_count
    if remaining % B == 0:
        b_count = remaining // B
        ab_patterns.append((a_count, remaining // B))

ans_ceil = 998244353

ans = 0
for a_count, b_count in ab_patterns:
    result = None
    for n_greens in range(min(a_count, b_count), -1, -1):
        n_reds = a_count - n_greens
        n_blues = b_count - n_greens
        if n_greens + n_reds + n_blues > N:
            break
        n_nocolors = N - n_reds - n_greens - n_blues
        # print(n_greens, n_reds, n_blues, n_nocolors)
        if result:
            result *= (n_greens + 1)
            result //= n_reds
            result //= n_blues
            result *= (n_nocolors + 1)
        else:
            result = math.factorial(N) // (math.factorial(n_greens) * math.factorial(n_reds) * math.factorial(n_blues) * math.factorial(n_nocolors))
        ans += result
        if ans > ans_ceil:
            ans %= ans_ceil

print(ans)

Submission status: Time Limit Exceeded

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

def squaremod(A,p,mod):#A^p(mod p)の計算
    if p==0:
        return 1
    if p%2==1:
        return (A*squaremod(A,p-1,mod))%mod
    if p%2==0:
        return (squaremod(A,p/2,mod) %mod)**2 %mod

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

def Combi(n,r):
    ANS=1
    for i in range(min(r,n-r)):
        ANS *= (N-i)*INV[i+1]

    return ANS
        

ANS=0

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

ran=K//A

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

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
def squaremod(A,p,mod):#A^pの計算
    if p==0:
        return 1
    if p%2==1:
        return (A*squaremod(A,p-1,mod))%mod
    if p%2==0:
        return (squaremod(A,p/2,mod) %mod)**2 %mod

    

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

def Combi(n,r):
    UP=1
    DOWN=1
    DOWN_r=1
    for i in range(r):
        UP=UP*(n-i) %mod
        DOWN=DOWN*(i+1)
        if i==r-1:
            DOWN_r=DOWN_r*squaremod(DOWN,mod-2,mod) %mod
        elif DOWN>mod**2:
            DOWN_r=DOWN_r*squaremod(DOWN,mod-2,mod) %mod
            DOWN=1

    return UP*DOWN_r %mod

ANS=0

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

ran=K//A

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

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
#1/A mod p の計算
#フェルマーの小定理より
#1/a=a^(p-2)  (mod p)を用いる。
#つまり、A^(p-2)(mod p)を求める.

def squaremod(A,p,mod):#A^pの計算
    if p==0:
        return 1
    if p%2==1:
        return (A*squaremod(A,p-1,mod))%mod
    if p%2==0:
        return (squaremod(A,p/2,mod) %mod)**2 %mod

    

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

def factorial(n):
    ANS=1
    for i in range(1,n+1):
        ANS=(ANS*i)%mod

    return ANS
        
    

def Combi(n,r):
    #return factorial(n) // (factorial(n - r) * factorial(r))
    #return factorial(n) * (factorial(n - r) * factorial(r))^(mod -2)
    return factorial(n) *squaremod(factorial(n - r) * factorial(r) %mod ,mod-2,mod)%mod


ANS=0

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

ran=K//A

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

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
N, A, B, K = map(int, input().split())
mod = 998244353
f_table = [1, 1]
inverse_table = {}


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

  
def inverse(x):
    if x in inverse_table:
        return inverse_table[x]
    res = pow(f_table[x], mod-2, mod)
    inverse_table[x] = res
    return res


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

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

Submission status: Time Limit Exceeded

Solution code:
def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

P = 998244353

N, A, B, K = reads()

fact = [1]
for i in range(1, N+1):
  fact.append(fact[i-1] * i % P)

def egcd(a, b):
  if b == 0:
    return a, 1, 0
  else:
    q, r = divmod(a, b)
    g, x, y = egcd(b, r)
    return g, y, x - q * y

def inv(n):
  g, x, _ = egcd(n, P)
  # assert g == 1
  return x

invfact = [inv(fact[i]) for i in range(N+1)]

def comb(n, k):
  # assert 0 <= k <= n
  return fact[n] * invfact[k] * invfact[n-k] % P

result = 0
for x in range(N+1):
  y, r = divmod(K - A * x, B)
  if r == 0 and 0 <= y <= N:
    result = result + comb(N, x) * comb(N, y) % P

print(result % P)

Submission status: Time Limit Exceeded

Solution code:
def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

P = 998244353

N, A, B, K = reads()

fact = [1]
for i in range(1, N+1):
  fact.append(fact[i-1] * i % P)

def egcd(a, b):
  if b == 0:
    return a, 1, 0
  else:
    q, r = divmod(a, b)
    g, x, y = egcd(b, r)
    return g, y, x - q * y

def inv(n):
  g, x, _ = egcd(n, P)
  # assert g == 1
  return x

def comb(n, k):
  # assert 0 <= k <= n
  return fact[n] * inv(fact[k]) * inv(fact[n-k]) % P

result = 0
for x in range(N+1):
  y, r = divmod(K - A * x, B)
  if r == 0 and 0 <= y <= N:
    result = result + comb(N, x) * comb(N, y) % P

print(result % P)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

P = 998244353

fact = [1]
for i in range(1, 300010):
  fact.append(fact[i-1] * i % P)

def egcd(a, b):
  if b == 0:
    return a, 1, 0
  else:
    q, r = divmod(a, b)
    g, x, y = egcd(b, r)
    return g, y, x - q * y

def inv(n):
  g, x, _ = egcd(n, P)
  # assert g == 1
  return x

def comb(n, k):
  # assert 0 <= k <= n
  return fact[n] * inv(fact[k]) % P * inv(fact[n-k]) % P

N, A, B, K = reads()

result = 0
for x in range(N+1):
  y, r = divmod(K - A * x, B)
  if r == 0 and 0 <= y <= N:
    result = (result + comb(N, x) * comb(N, y) % P) % P

print(result)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

def ncr(n,r):
    # 10C7 = 10C3
    r = min(r, n-r)

    # Calculate the numerator.
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    # Calculate the denominator. Should use math.factorial?
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator


if K==0: print 1;quit()

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

print ans

Submission status: Time Limit Exceeded

Solution code:
import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

MOD = 998244353

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)] % MOD
    
N,A,B,K = Is()
ans = 0
for x in range(N+1):
    if N >= (K-A*x)/B >= 0 and (K-A*x)/B == int((K-A*x)/B):
        ans += cmb(N,x)*cmb(N,(K-A*x)/B) % MOD
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import math

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

def Combi(n,r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


ANS=0

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

ran=K//A

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

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def Combi(n,r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


ANS=0

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

ran=K//A

for i in range(min(ran,N)+1):
    if (K-(A*i))%B==0:
        if (K-(A*i))//B<=N:
            ANS = (ANS+(Combi(N,i)*Combi(N,(K-(A*i))//B)))%998244353

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def Combi(n,r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


ANS=0

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

ran=K//A

for i in range(min(ran,N)+1):
    if (K-(A*i))%B==0:
        if (K-(A*i))//B<=N:
            ANS = (ANS+(Combi(N,i)*Combi(N,(K-(A*i))//B)))%998244353

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
def C(n,k):
    k=min(k,n-k)
    t=1
    for i in range(k):
        t*=(n-i)
        t//=(1+i)
    return t

n,a,b,k=map(int, input().split())
psb=[]
for i in range(n+1):
    if (k-a*i)%b==0 and i<=n and (k-a*i)//b<=n:
        psb.append([i, (k-a*i)//b])
    if a*(i+1)>k:
        break
ans=0
for ai, bi in psb:
    ans+=C(n,ai)*C(n,bi)
    ans%=998244353
#print(psb)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc_factorial(n):
    if n == 0:
        return 1
    else:
        num = 1
        for i in range(2, n+1):
            num = num * i
        return num


def calc_comb(n, k, fact_N):
    if 0 in [n, k, n-k]:
        return 1
    else:
        return int(fact_N/(calc_factorial(k)*calc_factorial(N-k)))


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

count = 0
num_A = 0
fact_N = calc_factorial(N)

for num_A in range(K//A + 1):
    left_beauty = K - num_A * A
    if left_beauty < 0:
        break
    # print("left_b: {}".format(left_beauty))

    if left_beauty % B == 0:
        # print("OK")
        num_B = int(left_beauty / B)

        comb_A = calc_comb(N, num_A, fact_N)
        comb_B = calc_comb(N, num_B, fact_N)
        count += comb_A * comb_B

        # print("comb_A: {}, comb_B: {}, count: {}".format(comb_A, comb_B, count))

print(count % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def calc_factorial(n):
    if n == 0:
        return 1
    else:
        num = 1
        for i in range(2, n+1):
            num = num * i
        return num


def calc_comb(n, k, fact_N):
    if 0 in [n, k, n-k]:
        return 1
    else:
        return int(fact_N/(calc_factorial(k)*calc_factorial(N-k)))


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

count = 0
num_A = 0
max_A = int(K / A)
fact_N = calc_factorial(N)

for num_A in range(N):
    left_beauty = K - num_A * A
    if left_beauty < 0:
        break
    # print("left_b: {}".format(left_beauty))

    if left_beauty % B == 0:
        # print("OK")
        num_B = int(left_beauty / B)

        comb_A = calc_comb(N, num_A, fact_N)
        comb_B = calc_comb(N, num_B, fact_N)
        count += comb_A * comb_B

        # print("comb_A: {}, comb_B: {}, count: {}".format(comb_A, comb_B, count))

print(count % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def calc_factorial(n):
    if n == 0:
        return 1
    else:
        num = 1
        for i in range(2, n+1):
            num = num * i
        return num


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

count = 0
num_A = 0
max_A = int(K / A)
fact_N = calc_factorial(N)

for num_A in range(N):
    left_beauty = K - num_A * A
    # print("left_b: {}".format(left_beauty))

    if left_beauty % B == 0:
        # print("OK")
        num_B = int(left_beauty / B)

        comb_A = int(fact_N/(calc_factorial(num_A)*calc_factorial(N-num_A)))
        comb_B = int(fact_N/(calc_factorial(num_B) * calc_factorial(N - num_B)))

        count += comb_A * comb_B

        # print("comb_A: {}, comb_B: {}, count: {}".format(comb_A, comb_B, count))

print(count % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k,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,b,c = factorial(n)%p,factorial(k)%p,factorial(n-k)%p
	return (a*pf(b,p-2,p)*pf(c,p-2,p))%p
def pf(a,b,p):
	if b==0: return 1
	if b%2==0:
		d = pf(a,b//2,p)
		return d**2%p
	if b%2==1: return (a*pf(a,b-1,p))%p
n,a,b,k = (int(i) for i in input().split())
mod,ans = 998244353,0
for i in range(n+1):
	if (k-a*i)%b==0:
		j = (k-a*i)//b
		ans = (ans+comb(n,i,mod)*comb(n,j,mod))%mod
print(ans)

Submission status: Time Limit Exceeded

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

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

i = 0
ans = 0
while k - i * a >= 0:
    j = (k - i * a) // b
    if (k - i * a) % b == 0 and 0 <= i <= n and 0 <= j <= n:
        ans_ = 1
        for x in range(i):
            ans_ *= (n - x)
            ans_ %= mod
        ans_ *= rev[i]
        for y in range(j):
            ans_ *= (n - y)
            ans_ %= mod
        ans_ *= rev[j]
        ans += ans_
    i += 1
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
# https://agc025.contest.atcoder.jp/tasks/agc025_b
import math


p_cache = {}

def factorial(n):
    if n in p_cache:
        return p_cache[n]
    p_cache[n] = math.factorial(n)

    return p_cache[n]


c_cache = {}

def combinations_count(n, r):
    if r == 0:
        return 1
    if n in c_cache and r in c_cache[n]:
        return c_cache[n][r]
    else:
        if n not in c_cache:
            c_cache[n] = {}
        c_cache[n][r] = factorial(n) // (factorial(n - r) * factorial(r))
    return c_cache[n][r]


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

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


BASE = 998244353

RED = A
GREEN = A + B
BLUE = B


candidates = []

a_count = 0
val = K
while val >= 0:
    if val % B == 0:
        b_count = val // B
        if a_count <= N and b_count <= N and a_count * RED + b_count * BLUE == K:
            candidates.append((a_count, b_count))

    val -= A
    a_count += 1


# print(candidates)


total = 0
for c in candidates:
    a_pattern = combinations_count(N, c[0])
    b_pattern = combinations_count(N, c[1])
    total += a_pattern * b_pattern

print(total % BASE)

Submission status: Time Limit Exceeded

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

X = set()
for n in range(0, K//A+1):
    m = (K - n * A) // B
    if n <= N and m <= N and n * A + m * B == K:
        X.add((n, m))

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

ans = 0
for n, m in X:
    ans += comb[n] * comb[m]
    ans = ans % M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def power_func(a,b,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

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, A, B, K] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2]), long(input_raw[3])]
    cnt = 0
    li = []
    for t in range(N + 1):
        if (K - t * A)%B == 0:
            u = (K - t * A)/B
            if t >= 0 and u >= 0 and t <= N and u <= N:
                li.append((t, u))


    frac_N = [0 for i in range(N + 1)]
    power_N = [0 for i in range(N + 1)]
    frac_N[0] = 1
    power_N[0] = 1
    p = 998244353L
    for i in range(1, N + 1):
        frac_N[i] = (frac_N[i - 1] * i ) % p
        power_N[i] = -1

    s = 0L
    for i in range(len(li)):
        t = li[i][0]
        u = li[i][1]
        if power_N[t] == -1:
            power_N[t] = power_func(frac_N[t], p - 2, p)
        if power_N[N - t] == -1:
            power_N[N - t] = power_func(frac_N[N - t], p - 2, p)
        if power_N[u] == -1:
            power_N[u] = power_func(frac_N[u], p - 2, p)
        if power_N[N - u] == -1:
            power_N[N - u] = power_func(frac_N[N - u], p - 2, p)

        s = (s + ((frac_N[N] * power_N[t] * power_N[N - t]) % p) * ((frac_N[N] * power_N[u] * power_N[N - u]) % p)) % p
    print s


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://agc025.contest.atcoder.jp/tasks/agc025_b
import math


def combinations_count(n, r):
    if r == 0:
        return 1
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

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


BASE = 998244353

RED = A
GREEN = A + B
BLUE = B


candidates = []

a_count = 0
val = K
while val >= 0:
    if val % B == 0:
        b_count = val // B
        if a_count <= N and b_count <= N and a_count * RED + b_count * BLUE == K:
            candidates.append((a_count, b_count))

    val -= A
    a_count += 1


# print(candidates)


total = 0
for c in candidates:
    a_pattern = combinations_count(N, c[0])
    b_pattern = combinations_count(N, c[1])
    total += a_pattern * b_pattern

print(total % BASE)