Problem:


Score : 700 points

Problem Statement

Takahashi has a tower which is divided into N layers.
Initially, all the layers are uncolored. Takahashi is going to paint some of the layers in red, green or blue to make a beautiful tower.
He defines the beauty of the tower as follows:

The beauty of the tower is the sum of the scores of the N layers, where the score of a layer is A if the layer is painted red, A+B if the layer is painted green, B if the layer is painted blue, and 0 if the layer is uncolored.

Here, A and B are positive integer constants given beforehand. Also note that a layer may not be painted in two or more colors.

Takahashi is planning to paint the tower so that the beauty of the tower becomes exactly K.
How many such ways are there to paint the tower? Find the count modulo 998244353.
Two ways to paint the tower are considered different when there exists a layer that is painted in different colors, or a layer that is painted in some color in one of the ways and not in the other.

Constraints

1 ≤ N ≤ 3×10^5

1 ≤ A,B ≤ 3×10^5

0 ≤ K ≤ 18×10^{10}

All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N A B K

Output

Print the number of the ways to paint tiles, modulo 998244353.

Sample Input 1

4 1 2 5

Sample Output 1

40

In this case, a red layer worth 1 points, a green layer worth 3 points and the blue layer worth 2 points. The beauty of the tower is 5 when we have one of the following sets of painted layers:

1 green, 1 blue

1 red, 2 blues

2 reds, 1 green

3 reds, 1 blue

The total number of the ways to produce them is 40.

Sample Input 2

2 5 6 0

Sample Output 2

1

The beauty of the tower is 0 only when all the layers are uncolored. Thus, the answer is 1.

Sample Input 3

90081 33447 90629 6391049189

Sample Output 3

577742975



Sample input:
4 1 2 5


Sample output:
40

Submission status: Accepted

Solution code:
import sys
# input関係の定義
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
# template


# BEGIN CUT HERE
class Modint(int):
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。
    Parameters
    ----------
        n (int) : Modintの初期値
        mod=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。
    Methods
    ----------
        inverse(n: int) -> Modint
            n の逆元を返す。
    '''
    # mod = int(1e9 + 7)
    mod = 998244353  # AGC025_B
    def __init__(self, n: int):
        self.n = n % self.__class__.mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.__class__.mod
        return self

    def __radd__(self, other):
        return self.__add__(other)

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.__class__.mod
        return self

    def __rsub__(self, other):
        return self.__sub__(other)

    def __imul__(self, other):
        self.n = self.n * int(other) % self.__class__.mod
        return self

    def __rmul__(self, other):
        return self.__mul__(other)

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return self.__class__(pow(self.n, self.__class__.mod - 2, self.__class__.mod))

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.__class__.mod - 2, self.__class__.mod)
        return self

    def __rfloordiv__(self, other):
        return self.__class__(other).__floordiv__(self)

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * self.__class__(int(other)).inverse())

    def comb(self, n: int, k: int):
        '''
        コンビネーション絡みの定義。comb(n,k):特に前処理をせずnCkを求める
        毎回O(N)かかるので死ぬ覚悟でO(N^2)を投げるくらいしか無理

        ちなみにですが，これでABC132_D()を出すとPyPy3で1932msくらいですれすれセーフ
        '''
        if n < k or k < 0:
            return Modint(0)
        res = Modint(1)
        for i in range(int(k)):
            res *= Modint(n - i)
            res //= Modint(i + 1)
        return res

    def H(self, n: int, k: int):
        if n < 0 or k < 0:
            return Modint(0)
        elif n == 0 and k == 0:
            return Modint(1)
        else:
            return self.comb(n + k - 1, k)


COMBINATION_MAX = 2 * 10**5


class Combination():
    def __init__(self, sz=COMBINATION_MAX):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [Modint(0)] * (sz + 1)
        self._rfact = [Modint(0)] * (sz + 1)
        self._fact[0] = Modint(1)
        self._rfact[sz] = Modint(1)
        for i in range(1, sz + 1):
            self._fact[i] = self._fact[i - 1] * i
        self._rfact[sz] = self._fact[sz].inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = self._rfact[i + 1] * (i + 1)

    def fact(self, k: int) -> int:
        """階乗の計算"""
        return self._fact[k]

    def rfact(self, k: int) -> int:
        """階乗の逆元の計算"""
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）

        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        return self._fact[n] * self._rfact[n - k]

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）

        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        if n - k < k:
            k = n - k
        return self._fact[n] * self._rfact[k] * self._rfact[n - k]

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理された n+k-1 以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。

        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）

        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return Modint(0)
        elif k == 0:
            return Modint(1)
        return self.C(n + k - 1, k)

# END CUT HERE


def ABC021_D():
    """https://atcoder.jp/contests/abc021/tasks/abc021_d"""
    n = ii()
    k = ii()
    res = Combination()
    print(res.H(n, k))
# verified on 2019/07/01
# PyPy3: 243ms https://atcoder.jp/contests/abc021/submissions/6207045


def ABC132_D():
    """https://atcoder.jp/contests/abc132/tasks/abc132_d"""
    N, K = mi()
    res = Combination(N)
    for i in range(1, K + 1):
        print(res.C(K - 1, i - 1) * res.C(N - K + 1, i))
# verified on 2019/07/01
# Python3: 32ms https://atcoder.jp/contests/abc132/submissions/6200580
# PyPy3だとオーバヘッドが大きいのか240msくらいかかるけど，基本はPyPyで良いと思う。


def AGC025_B():
    """https://atcoder.jp/contests/agc025/tasks/agc025_b"""
    N, A, B, K = mi()
    res = Combination(N)
    ans = Modint(0)
    for a in range(min(K // A + 1, N + 1)):
        b = (K - a * A) // B
        if A * a + B * b == K and a >= 0 and b >= 0:
            ans += res.C(N, a) * res.C(N, b)
    print(ans)
# verified on 2019/07/01
# PyPy3: https://atcoder.jp/contests/agc025/submissions/6200598
# Python3だとTLE


def ABC130_E():
    """https://atcoder.jp/contests/abc130/tasks/abc130_e"""
    N, M = mi()
    S = lmi()
    T = lmi()
    a = [[Modint(0) for __ in range(M + 1)] for _ in range(N + 1)]
    for i in range(N + 1):
        for j in range(M + 1):
            if i == 0 or j == 0:
                a[i][j] = Modint(1)
            else:
                a[i][j] = a[i - 1][j] + a[i][j - 1] - \
                    (a[i - 1][j - 1] if S[i - 1] != T[j - 1] else 0)
    print(a[N][M])
# verified on 2019/07/01
# PyPy3: 1839ms https://atcoder.jp/contests/abc130/submissions/6204339
# やっぱりクソ遅い


if __name__ == '__main__':
    # import cProfile
    # cProfile.run('AGC025_B()')
    # ABC021_D()
    # ABC132_D()
    AGC025_B()
    # ABC130_E()

Submission status: Accepted

Solution code:
import sys
# input関係の定義
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
# template


# BEGIN CUT HERE
class Modint(int):
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。
    Parameters
    ----------
        n (int) : Modintの初期値
        mod=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。
    Methods
    ----------
        inverse(n: int) -> Modint
            n の逆元を返す。
    '''
    # mod = int(1e9 + 7)
    mod = 998244353  # AGC025_B
    def __init__(self, n: int):
        self.n = n % self.__class__.mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.__class__.mod
        return self

    def __radd__(self, other):
        return self.__add__(other)

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.__class__.mod
        return self

    def __rsub__(self, other):
        return self.__sub__(other)

    def __imul__(self, other):
        self.n = self.n * int(other) % self.__class__.mod
        return self

    def __rmul__(self, other):
        return self.__mul__(other)

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return self.__class__(pow(self.n, self.__class__.mod - 2, self.__class__.mod))

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.__class__.mod - 2, self.__class__.mod)
        return self

    def __rfloordiv__(self, other):
        return self.__class__(other).__floordiv__(self)

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * self.__class__(int(other)).inverse())

    def comb(self, n: int, k: int):
        '''
        コンビネーション絡みの定義。comb(n,k):特に前処理をせずnCkを求める
        毎回O(N)かかるので死ぬ覚悟でO(N^2)を投げるくらいしか無理

        ちなみにですが，これでABC132_D()を出すとPyPy3で1932msくらいですれすれセーフ
        '''
        if n < k or k < 0:
            return Modint(0)
        res = Modint(1)
        for i in range(int(k)):
            res *= Modint(n - i)
            res //= Modint(i + 1)
        return res

    def H(self, n: int, k: int):
        if n < 0 or k < 0:
            return Modint(0)
        elif n == 0 and k == 0:
            return Modint(1)
        else:
            return self.comb(n + k - 1, k)


COMBINATION_MAX = 2 * 10**5


class Combination():
    def __init__(self, sz=COMBINATION_MAX):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [Modint(0)] * (sz + 1)
        self._rfact = [Modint(0)] * (sz + 1)
        self._fact[0] = Modint(1)
        self._rfact[sz] = Modint(1)
        for i in range(1, sz + 1):
            self._fact[i] = self._fact[i - 1] * Modint(i)
        self._rfact[sz] = self._fact[sz].inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = self._rfact[i + 1] * Modint(i + 1)

    def fact(self, k: int) -> int:
        """階乗の計算"""
        return self._fact[k]

    def rfact(self, k: int) -> int:
        """階乗の逆元の計算"""
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）

        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        return self._fact[n] * self._rfact[n - k]

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）

        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        if n - k < k:
            k = n - k
        return self._fact[n] * self._rfact[k] * self._rfact[n - k]

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理された n+k-1 以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。

        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）

        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return Modint(0)
        elif k == 0:
            return Modint(1)
        return self.C(n + k - 1, k)

# END CUT HERE


def ABC021_D():
    """https://atcoder.jp/contests/abc021/tasks/abc021_d"""
    n = ii()
    k = ii()
    res = Combination()
    print(res.H(n, k))
# verified on 2019/07/01
# PyPy3: 243ms https://atcoder.jp/contests/abc021/submissions/6207045


def ABC132_D():
    """https://atcoder.jp/contests/abc132/tasks/abc132_d"""
    N, K = mi()
    res = Combination(N)
    for i in range(1, K + 1):
        print(res.C(K - 1, i - 1) * res.C(N - K + 1, i))
# verified on 2019/07/01
# Python3: 32ms https://atcoder.jp/contests/abc132/submissions/6200580
# PyPy3だとオーバヘッドが大きいのか240msくらいかかるけど，基本はPyPyで良いと思う。


def AGC025_B():
    """https://atcoder.jp/contests/agc025/tasks/agc025_b"""
    N, A, B, K = mi()
    res = Combination(N)
    ans = Modint(0)
    for a in range(min(K // A + 1, N + 1)):
        b = (K - a * A) // B
        if A * a + B * b == K and a >= 0 and b >= 0:
            ans += res.C(N, a) * res.C(N, b)
    print(ans)
# verified on 2019/07/01
# PyPy3: https://atcoder.jp/contests/agc025/submissions/6200598
# Python3だとTLE


def ABC130_E():
    """https://atcoder.jp/contests/abc130/tasks/abc130_e"""
    N, M = mi()
    S = lmi()
    T = lmi()
    a = [[Modint(0) for __ in range(M + 1)] for _ in range(N + 1)]
    for i in range(N + 1):
        for j in range(M + 1):
            if i == 0 or j == 0:
                a[i][j] = Modint(1)
            else:
                a[i][j] = a[i - 1][j] + a[i][j - 1] - \
                    (a[i - 1][j - 1] if S[i - 1] != T[j - 1] else 0)
    print(a[N][M])
# verified on 2019/07/01
# PyPy3: 1839ms https://atcoder.jp/contests/abc130/submissions/6204339
# やっぱりクソ遅い


if __name__ == '__main__':
    # import cProfile
    # cProfile.run('AGC025_B()')
    # ABC021_D()
    # ABC132_D()
    AGC025_B()
    # ABC130_E()

Submission status: Accepted

Solution code:
def fib(n, p):
  F = [1] * (n + 1)
  for i in range(2, n + 1):
    F[i] = F[i - 1] * i % p
  return F
def finv(F, p):
  N = len(F) - 1
  Finv = list(F)
  Finv[-1] = pow(F[-1], p - 2, p)
  for i in range(N - 1, -1, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv
def comb(F, Finv, n, a, p):
  return F[n] * Finv[a] * Finv[n - a] % p
N, A, B, K = map(int, input().split())
p = 998244353
F = fib(N, p)
Finv = finv(F, p)
cnt = 0
for a in range(min(N + 1, K // A + 1)):
  _A = A * a
  if _A > K:
    continue
  if (K - _A) % B > 0:
    continue
  b = (K - _A) // B
  if b > N:
    continue
  cnt += comb(F, Finv, N, a, p) * comb(F, Finv, N, b, p)
  cnt %= p
print(cnt)

Submission status: Accepted

Solution code:
from fractions import gcd
from math import factorial
mod = 998244353

# comb init
nmax = 3 * 10 ** 5 + 1  # change here
fac = [0] * (nmax + 1)
finv = [0] * (nmax + 1)
inv = [0] * (nmax + 1)
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, nmax):
    fac[i] = fac[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def comb(n, r):
    if n < r:
        return 0
    else:
        return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod


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

gcdAB = gcd(A, B)
da = B // gcdAB
db = A // gcdAB

numAB = []
for i in range(N, -1, -1):
    if A * i > K:
        continue
    numB, m = divmod(K - A * i, B)
    if m == 0:
        numAB = (i, numB)
        break

numAB_list = [numAB]
if len(numAB) > 0:
    numA = numAB[0]
    numB = numAB[1]
    while True:
        numA -= da
        numB += db
        if numA >= 0 and numB <= N:
            numAB_list.append((numA, numB))
        else:
            break

for numAB in numAB_list:
    numA = numAB[0]
    numB = numAB[1]
    ans = (ans + comb(N, numA) * comb(N, numB)) % mod

print(ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = []
    r = 1
    for inv in mod_invs(max, mod):
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


N, A, B, K = list(map(int, sys.stdin.readline().split()))
comb = Combination(max=N, mod=MOD)
# ans = 0
# # A の数が決まれば B の数も決まる
# for a in range(N + 1):
#     if (K - a * A) % B != 0:
#         continue
#     b = int((K - a * A) // B)
#     if not (0 <= a <= N and 0 <= b <= N):
#         continue
#
#     s = 0
#     # 緑
#     c = min(a, b)
#     # A
#     a -= c
#     # B
#     b -= c
#     # 無色
#     d = N - a - b - c
#     # ここ高速化したい
#     while c >= 0 and d >= 0:
#         s += comb.ncr(N, a) * comb.ncr(N - a, b) * comb.ncr(N - a - b, c)
#         a += 1
#         b += 1
#         c -= 1
#         d -= 1
#
#     ans += s
#     ans %= MOD
# print(ans)


# # dp[i, a, b]: i番目までで、残り使うべき A が a 個、B が b 個残ってるパターン数
# dp = np.zeros((N + 1, N + 1, N + 1), dtype=int)
#
# # A の数が決まれば B の数も決まる
# for a in range(N + 1):
#     if (K - a * A) % B != 0:
#         continue
#     b = int((K - a * A) // B)
#     if not (0 <= a <= N and 0 <= b <= N):
#         continue
#     dp[0][a][b] += 1
#
# for i in range(1, N + 1):
#     dp[i] += dp[i - 1]
#     dp[i, :-1] += dp[i - 1, 1:]
#     dp[i, :, :-1] += dp[i - 1, :, 1:]
#     dp[i, :-1, :-1] += dp[i - 1, 1:, 1:]
# print(dp)
# print(dp[-1][0][0])


# 未証明、DP テーブル見た
ans = 0
for a in range(N + 1):
    if (K - a * A) % B != 0:
        continue
    b = int((K - a * A) // B)
    if not (0 <= a <= N and 0 <= b <= N):
        continue
    ans += comb.ncr(N, a) * comb.ncr(N, b)
    ans %= MOD
print(ans)

Submission status: Accepted

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

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

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

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


ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

# 赤と青を独立に塗る → 重なった場所が緑

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

MOD = 998244353
fact = [1]
for n in range(1,N+1):
    fact.append(fact[-1] * n % MOD)
fact_inv = [1] * (N+1)
fact_inv[N] = pow(fact[N],MOD-2,MOD)
for n in range(N,0,-1):
    fact_inv[n-1] = fact_inv[n] * n % MOD

comb = [fact[N] * x * y % MOD for x,y in zip(fact_inv, reversed(fact_inv))]

answer = 0
for a in range(N+1):
    q,r = divmod(K - a * A, B)
    if q > N:
        continue
    if q < 0:
        break
    if r != 0:
        continue
    answer += comb[a] * comb[q]

answer %= MOD
print(answer)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


# BEGIN CUT HERE
# MOD = 10**9 + 7
MOD = 998244353  # AGC025_B


class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。
    Parameters
    ----------
        n (int) : Modintの初期値
        MOD=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。
    Methods
    ----------
        inverse(n: int) -> Modint
            n の逆元を返す。
    '''

    def __init__(self, n: int, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        return self.__add__(other)

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        return self.__sub__(other)

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        return self.__mul__(other)

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return pow(self.n, self.mod - 2, self.mod)

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        return self.__class__(other).__floordiv__(self)

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * Modint(int(other)).inverse())

    # def comb(self, n: int, k: int):
    #     '''
    #     コンビネーション絡みの定義。comb(n,k):特に前処理をせずnCkを求める
    #     毎回O(N)かかるので死ぬ覚悟でO(N^2)を投げるくらいしか無理

    #     ちなみにですが，これでABC132_D()を出すとPyPy3で1932msくらいですれすれセーフ
    #     '''
    #     if n < k or k < 0:
    #         return Modint(0)
    #     res = Modint(1)
    #     for i in range(int(k)):
    #         res *= Modint(n - i)
    #         res //= Modint(i + 1)
    #     return res

    # def H(self, n: int, k: int):
    #     if n < 0 or k < 0:
    #         return Modint(0)
    #     elif n == 0 and k == 0:
    #         return Modint(1)
    #     else:
    #         return self.comb(n + k - 1, n)


COMBINATION_MAX = 2 * 10**5


class Combination():
    def __init__(self, sz=COMBINATION_MAX):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [Modint(0)] * (sz + 1)
        self._rfact = [Modint(0)] * (sz + 1)
        self._fact[0] = Modint(1)
        self._rfact[sz] = Modint(1)
        for i in range(1, sz + 1):
            self._fact[i] = self._fact[i - 1] * Modint(i)
        self._rfact[sz] = self._fact[sz].inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = self._rfact[i + 1] * Modint(i + 1)

    def fact(self, k: int) -> int:
        return self._fact[k]

    def rfact(self, k: int) -> int:
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ
        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）
        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return 0
        return self._fact[n] * self._rfact[n - k]

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ
        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）
        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return 0
        if n - k < k:
            k = n - k
        return self._fact[n] * self._rfact[k] * self._rfact[n - k]

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。
        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）
        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return 0
        elif k == 0:
            return 1
        return self.C(n + k - 1, k)

# END CUT HERE


def ABC021_D():
    n = ii()
    k = ii()
    res = Combination()
    print(res.H(n, k))
# verified on 2019/07/01
# https://atcoder.jp/contests/abc021/tasks/abc021_d
# PyPy3: 243ms https://atcoder.jp/contests/abc021/submissions/6207045


def ABC132_D():
    N, K = mi()
    res = Combination(N)
    for i in range(1, K + 1):
        print(res.C(K - 1, i - 1) * res.C(N - K + 1, i))
# verified on 2019/07/01
# https://atcoder.jp/contests/abc132/tasks/abc132_d
# Python3: 32ms https://atcoder.jp/contests/abc132/submissions/6200580
# PyPy3だとオーバヘッドが大きいのか240msくらいかかるけど，基本はPyPyで良いと思う。


def AGC025_B():
    N, A, B, K = mi()
    res = Combination(N)
    ans = Modint(0)
    for a in range(min(K // A + 1, N + 1)):
        b = (K - a * A) // B
        if A * a + B * b == K and a >= 0 and b >= 0:
            ans += res.C(N, a) * res.C(N, b)
    print(ans)
# verified on 2019/07/01
# https://atcoder.jp/contests/agc025/tasks/agc025_b
# PyPy3: https://atcoder.jp/contests/agc025/submissions/6200598
# Python3だとTLE


def ABC130_E():
    N, M = mi()
    S = lmi()
    T = lmi()
    a = [[Modint(0) for __ in range(M + 1)] for _ in range(N + 1)]
    for i in range(N + 1):
        for j in range(M + 1):
            if i == 0 or j == 0:
                a[i][j] = Modint(1)
            else:
                a[i][j] = a[i - 1][j] + a[i][j - 1] - \
                    (a[i - 1][j - 1] if S[i - 1] != T[j - 1] else 0)
    print(a[N][M])
# verified on 2019/07/01
# https://atcoder.jp/contests/abc130/tasks/abc130_e
# PyPy3: 1839ms https://atcoder.jp/contests/abc130/submissions/6204339
# やっぱりクソ遅い


if __name__ == '__main__':
    # ABC021_D()
    # ABC132_D()
    AGC025_B()
    # ABC130_E()