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
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 self.__class__(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()

Submission status: Accepted

Solution code:
n,a,b,k=map(int,input().split())
if k==0:
    print(1)
    quit()
mod=998244353
fra=[1]*(n+2)
inv=[1]*(n+2)
t1=1
t2=1
for i in range(1,n+2):
    t1*=i
    t1%=mod
    t2*=pow(i,mod-2,mod)
    t2%=mod
    fra[i]=t1
    inv[i]=t2
def comb(n,r):
    return fra[n]*inv[n-r]%mod*inv[r]%mod
ans=0
b,a=sorted([a,b])
for i in range(max(0,-(-(k-b*n)//a)),min(n+1,k//a+1)):
    t=k-i*a
    if t>b*n or t%b!=0:
        continue
    else:
        t//=b
        ans+=(comb(n,i)*comb(n,t))%mod
        ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n,a,b,k=map(int,input().split())
if k==0:
    print(1)
    quit()
mod=998244353
fra=[1]*(n+2)
inv=[1]*(n+2)
t1=1
t2=1
for i in range(1,n+2):
    t1*=i
    t1%=mod
    t2*=pow(i,mod-2,mod)
    t2%=mod
    fra[i]=t1
    inv[i]=t2
def comb(n,r):
    return fra[n]*inv[n-r]*inv[r]%mod
ans=0
for i in range(max(0,-(-(k-b*n)//a)),min(n+1,k//a+1)):
    t=k-i*a
    if t>b*n or t%b!=0:
        continue
    else:
        t//=b
        ans+=(comb(n,i)*comb(n,t))%mod
        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。素数である必要がある。
    '''

    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, self.mod)

    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):
        self.n += int(other)
        self.n %= self.mod
        return self

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

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

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

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

    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):
        self *= pow(int(other), self.mod - 2, self.mod)
        return 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)


class Combination():
    def __init__(self, sz):
        '''
        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
        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, n)

# END CUT HERE


def ABC132_D():
    N, K = mi()
    res = Combination(N)
    for i in range(1, K + 1):
        print(res.C(K - 1, i - 1) * res.H(N - K - i + 1, i + 1))
# 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__':
    # ABC132_D()
    AGC025_B()
    # ABC130_E()

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 = 998244353


class Modint():
    '''
        自動でMODで割った余りを返してくれる。
    '''

    def __init__(self, n, 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 Modint(-self.n, self.mod)

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

    def __int__(self):
        return int(self.n)

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

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

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

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

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

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

    def inverse(self):
        return self.__class__(pow(self.n, self.mod - 2, self.mod), self.mod)

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

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

    def __add__(self, other):
        self += other
        return self

    def __sub__(self, other):
        self -= other
        return self

    def __mul__(self, other):
        self *= other
        return self

    def __floordiv__(self, other):
        self //= other
        return self

    # '''コンビネーション絡みの定義
    #     ･ comb(n,k):特に前処理をせずnCkを求める
    # '''

    # def comb(self, n, k):
    #     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, k):
    #     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)


class Combination():
    def __init__(self, sz):
        self.fact = [0] * (sz + 1)
        self.rfact = [0] * (sz + 1)
        self.fact[0] = 1
        self.rfact[sz] = 1
        for i in range(1, sz + 1):
            self.fact[i] = int(self.fact[i - 1] * Modint(i))
        self.rfact[sz] = int(Modint(self.fact[sz]).inverse())
        for i in range(sz - 1, -1, -1):
            self.rfact[i] = int(self.rfact[i + 1] * Modint(i + 1))

    def fact(self, k):
        return Modint(self.fact[k])

    def rfact(self, k):
        return Modint(self.rfact[k])

    def P(self, n, k):
        if k < 0 or n < k:
            return 0
        return Modint(self.fact[n] * self.rfact[n - k])

    def C(self, n, k):
        if k < 0 or n < k:
            return 0
        return Modint(self.fact[n] * self.rfact[k] * self.rfact[n - k])

    def H(self, n, k):
        if n < 0 or k < 0:
            return 0
        elif k == 0:
            return 1
        return self.C(n + k - 1, n)


def ABC132_D():
    N, K = mi()
    res = Combination(N)
    for i in range(1, K + 1):
        print(res.C(K - 1, i - 1) * res.H(N - K - i + 1, i + 1))
# verified on 2019/07/01
# https://atcoder.jp/contests/abc132/tasks/abc132_d
# PyPy3 : 244ms https://atcoder.jp/contests/abc132/submissions/6200405


def AGC025_B():
    N, A, B, K = mi()
    res = Combination(N)
    ans = Modint(0)
    for a in range(K // A + 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)


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

Submission status: Accepted

Solution code:
MOD = 998244353
MAX = int(3e5 + 10)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    N, A, B, K = map(int, input().split())
    ans = 0
    # solve Ax + By = K
    for x in range(N+1):
        By = K - x * A
        if By >= 0 and By % B == 0 and By <= B * N:
            y = By // B
            tmp1 = FACT[N] * INV[x] * INV[N-x] % MOD
            tmp2 = FACT[N] * INV[y] * INV[N-y] % MOD
            ans = (ans + tmp1 * tmp2) % MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 998244353
MAX = int(3e5 + 1)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    N, A, B, K = map(int, input().split())
    ans = 0
    # solve Ax + By = K
    for x in range(N+1):
        By = K - x * A
        if By >= 0 and By % B == 0 and By <= B * N:
            y = By // B
            tmp1 = FACT[N] * INV[x] * INV[N-x] % MOD
            tmp2 = FACT[N] * INV[y] * INV[N-y] % MOD
            ans = (ans + tmp1 * tmp2) % MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class BinomialCoefficient:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}                # n!
        self.inverse = {i: None for i in range(1, N+1)}      # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def binom(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
N, A, B, K = map(int, input().split())
MOD = 998244353

ans = 0
bc = BinomialCoefficient(N, MOD)
for red, i in [(A*i, i) for i in range(N+1)]:
    if K < red:
        break
    j, rem = divmod(K - red, B)
    if rem == 0:
        ans += (bc.binom(N, i) * bc.binom(N, j)) % MOD
        ans = ans % MOD
print(ans)

Submission status: Accepted

Solution code:
class Combination:
    '''
    計算量：階乗・逆元テーブルの作成O(N)
            nCkを求めるO(1)
    '''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i] ,MOD - 2 ,MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        '''k!を求める'''
        return self.fact[k]

    def inverse_factorial(self, k):
        '''k!の逆元を求める'''
        return self.inv_fact[k]

    def combination(self, k, r):
        '''kCrを求める'''
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


n, a, b, k = map(int, input().split())
MOD = 998244353
comb = Combination(n, MOD)
ans = 0
for i in range(n+1):
    if not(k - a*i >= 0 and (k - a*i) % b == 0 and (k - a*i) // b <= n):
        continue
    else:
        ai = i
        bi = (k - a*i) // b
        ans += comb.combination(n, ai) * comb.combination(n, bi)
        ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N, A, B, K = map(int, input().split())
mod = 998244353
frac = [1]*(N+1)
for i in range(2,N + 1):
    frac[i] = i * frac[i-1]%mod
fraci = [None]*(N+1)
for i in range(N + 1):
    fraci[i] = pow(frac[i], mod-2, mod)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%mod

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

Submission status: Accepted

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

def pow(n, i):
    if i == 0: return 1
    elif i == 1: return n
    elif i % 2 == 0: return pow((n * n) % mod, i//2)
    else: return (pow((n * n) % mod, i//2) * n) % mod

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

ans = 0
for a in range(N+1):
    if K >= A * a:
        if (K - A * a) % B == 0:
            b = (K - A * a) // B
            apatt = (factorial[N] * revfactorial[N - a] * revfactorial[a]) % mod
            if b <= N: bpatt = (factorial[N] * revfactorial[N - b] * revfactorial[b]) % mod
            else: bpatt = 0
            ans += (apatt * bpatt) % mod
            ans %= mod
print(ans)

Submission status: Accepted

Solution code:
p=998244353
def getinv(n):
  inv = [0]*(n+1)
  #フェルマーの小定理より、i=1の時は1であることが分かる
  inv[1] = 1
  for i in range(2,n+1):
    #そのまま計算すると負になってしまうので、最後にmod pを取ることで正に戻す
    inv[i] = (-(p//i)*inv[p%i])%p
  return inv

def getCmb(n):
  #逆元を取得
  inv = getinv(n)
  #0 <= r <= n に対してnCrを求める
  nCr = [0]*(n+1)
  #r=0の時は、r-1が存在しないので与えておく
  nCr[0] = 1
  for i in range(1,n+1):
    #iで割る代わりにinv[i]をかけ、mod pを求める
    nCr[i] = (nCr[i-1]*(n-i+1)*inv[i])%p
  return nCr

def solve(n,a,b,k):
  nCr = getCmb(n)
  ans=0
  for i in range(n+1):
    #割り切れない時もあるが、その時は次の条件a*i+b*j==kで弾かれるので問題ない
    j = (k-a*i)//b
    #条件に一致するものを選ぶ。jの範囲に注意
    if a*i + b*j == k and 0<=j<=n:
      ans+= (nCr[i]*nCr[j])%p
      ans%= p
  return ans

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

Submission status: Accepted

Solution code:
n,a,b,k=map(int,input().split())
p=998244353
def getinv(n):
  inv=[0]*(n+1)
  for i in range(1,n+1):
    inv[i]=pow(i,p-2,p)
  return inv
def getnCr(n):
  inv=getinv(n)
  nCr=[0]*(n+1)
  nCr[0]=1
  for i in range(1,n+1):
    nCr[i]=(nCr[i-1]*(n-i+1)*inv[i])%p
  return nCr
def solve(n,a,b,k):
  ans=0
  nCr=getnCr(n)
  for i in range(n+1):
    if (k-a*i)<0 or (k-a*i)%b!=0:
      continue
    j=(k-a*i)//b
    if a*i+b*j==k and 0<=j<=n:
      ans+= nCr[i]*nCr[j]
      ans%=p
  return ans
print(solve(n,a,b,k))

Submission status: Accepted

Solution code:
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, N + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD

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

if A > B:
  A, B = (B, A)
Rk = min(N, K // A)

Ans = 0
for i in range(Rk + 1):
  R = i
  if (K - (A * R)) % B != 0:
    continue
  C = (K - (A * R)) // B
  if C > N:
    continue
  Rc = com.com(N, R)
  Cc = com.com(N, C)
  Ans += (Rc * Cc) % MOD

print(Ans % MOD)

Submission status: Accepted

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

F = [1, 1]
Fi = [1, 1]
I = [0, 1]
for i in range(2, N + 1):
  F.append((F[-1] * i) % MOD)
  I.append(MOD - I[MOD % i] * (MOD // i) % MOD)
  Fi.append(Fi[-1] * I[i] % MOD)

if A > B:
  A, B = (B, A)
Rk = min(N, K // A)

Ans = 0
for i in range(Rk + 1):
  R = i
  if (K - (A * R)) % B != 0:
    continue
  C = (K - (A * R)) // B
  if C > N:
    continue
  Rc = F[N] * (Fi[R] * Fi[N - R] % MOD) % MOD
  Cc = F[N] * (Fi[C] * Fi[N - C] % MOD) % MOD
  Ans += (Rc * Cc) % MOD

print(Ans % MOD)

Submission status: Accepted

Solution code:
n,a,b,k=map(int,input().split())
p=998244353
def getinv(n):
  inv=[0]*(n+1)
  inv[1]=1
  for i in range(2,n+1):
    inv[i]=(-(p//i)*inv[p%i])%p
  return inv
def getnCr(n):
  inv=getinv(n)
  nCr=[0]*(n+1)
  nCr[0]=1
  for i in range(1,n+1):
    nCr[i]=(nCr[i-1]*(n-i+1)*inv[i])%p
  return nCr
def solve(n,a,b,k):
  ans=0
  nCr=getnCr(n)
  for i in range(n+1):
    if (k-a*i)<0 or (k-a*i)%b!=0:
      continue
    j=(k-a*i)//b
    if a*i+b*j==k and 0<=j<=n:
      ans+= nCr[i]*nCr[j]
      ans%=p
  return ans
print(solve(n,a,b,k))

Submission status: Accepted

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

mod = 998244353

# combination---
# nとmodは適宜変える

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n+5):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

def nck(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0
for ca in range(n+1):
    cb = (k - a * ca) // b
    if (k - a * ca) % b != 0:
        continue
    ans += nck(n, ca) * nck(n, cb)
    ans %= mod

print(ans)

Submission status: Accepted

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

if (A+B)*N < K:
    print(0)
    exit()

M = N+5
fac = [1,1] + [0]*M
finv = [1,1] + [0]*M
inv = [0,1] + [0]*M
for i in range(2,M+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):
    rem = K - a*A
    if rem < 0: break
    b,m = divmod(rem, B)
    if m: continue
    ans += ncr(N,a) * ncr(N,b)
    ans %= MOD
print(ans)

Submission status: Accepted

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

MOD = 998244353
MAX = 3*10**5+2

fac = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
ifac = [0 for i in range(MAX)]
fac[0] = 1; fac[1] = 1
inv[1] = 1
ifac[0] = 1; ifac[1] = 1

for i in range(2, MAX):
  fac[i] = fac[i-1]*i%MOD
  inv[i] = inv[MOD%i]*(MOD-MOD//i)%MOD
  ifac[i] = ifac[i-1]*inv[i]%MOD

def nCk(n, k):
  if n<k or n<0 or k<0: return 0
  return (((fac[n]*ifac[k])%MOD)*ifac[n-k])%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+nCk(n, i)*nCk(n, b))%MOD

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