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: Wrong Answer

Solution code:
import numpy as np

mod = 998244353


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


def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def lcm(a, b):
    """
    最小公倍数
    """
    return a * b / gcd(a,b)


# def main_old():
#     N, A, B, K = lii()
#     dp = np.zeros([N+1, K+1])
#     dp[:, 0] = 1
#     for n in range(1, N+1):
#         for k in range(K+1):
#             c = dp[n-1][k]
#             if k - A >= 0: c += dp[n-1][k-A]
#             if k - B >= 0: c += dp[n-1][k-B]
#             if k - (A+B) >= 0: c += dp[n-1][k-(A+B)]
#             dp[n][k] = c
#
#     print(int(dp[N][K]) % mod)


def solve_eucl(A, B, K, N):
    for _x in range(N):
        if (K - A * _x) % B == 0:
            x = _x
            y = (K - A * _x) // B
            return x, y


def comb(n, x):
    ans = 1
    x = min(x, n-x)
    for i in range(1, x+1):
        ans = (ans * (n - i + 1) // i) % mod
    return int(ans)


def comb_table(n):
    t = [1]
    c = 1
    for x in range(1, n // 2 + 1):
        c = c * (n - x + 1) // x
        c = c % mod
        t.append(c)

    return t


def modinv(a, m):
    orgm = m
    x, lastx, y, lasty = 0, 1, 1, 0
    while m:
        a, (quotient, m) = m, divmod(a, m)
        x, lastx = lastx - quotient * x, x
        y, lasty = lasty - quotient * y, y
    if a != 1:
        raise ValueError
    return lastx % orgm


def fastcombmod(m, n):
    nn = min(n, m - n)
    num = 1
    div = 1
    for i in range(nn):
        num *= m - i
        if num > mod:
            num %= mod
        div *= i + 1
        if div > mod:
            div %= mod
    return (num * modinv(div, mod)) % mod

# def comb_mult(N, A, B, C):
#     a = int(comb(N, A)) % mod
#     b = int(comb(N-A, B)) % mod
#     c = int(comb(N-A-B, C)) % mod
#     return (a * b * c) % mod


def main():
    N, A, B, K = lii()
    if K == 0: return 1

    d = gcd(gcd(A, B), K)
    if d > 1:
        A = A // d
        B = B // d
        K = K // d

    x, y = solve_eucl(A, B, K, N)

    # ct = comb_table(N)
    # ct = [fastcombmod(N, p) for p in range(N)]

    C = int(lcm(A, B))
    ans = 0
    p = x
    while True:
        q = (K - A * p) // B
        if q <= 0:
            break

        # ans = (ans + ct[min(p, N-p)] * ct[min(q, N-q)]) % mod
        ans = (ans + fastcombmod(N, p) * fastcombmod(N, q)) % mod
        p += C // A
        if p > N:
            break

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
from math import ceil, factorial
N, A, B, K = map(int, input().split())
M = 998244353

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

Y = set()
for n, m in X:
    for g in range(0, min(n, m) + 1):
        r = n - g
        b = m - g
        if r + g + b <= N:
            Y.add((r, g, b))

ans = 0
for r, g, b in Y:
    t = N - r - g - b
    val = factorial(N) // factorial(r) // factorial(g) // factorial(b) // factorial(N-r-g-b)
    ans = (ans + val) % M
print(ans)

Submission status: Wrong Answer

Solution code:
N, A, B, K = [int(_) for _ in input().split()]

def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

L = 300000+1
M = 998244353

Fm = {}
inverseFm = {}
x = 1
for i in range(L):
    Fm[i] = x
    x = x * (i + 1) % M

def inverseFm(x, cache={}):
    if x in cache:
        return cache[x]
    result = pow(Fm[x], M - 2, M)
    cache[x] = result
    return result

def C(n, r):
    result = Fm[n] * inverseFm(r) * inverseFm(n - r) % M
    return result

def solve(N, A, B, K):
    g = gcd(gcd(A, B), K)
    A, B, K = A//g, B//g, K//g
    if A > B:
        A, B = B, A
    l = A * B // gcd(A, B)
    x = K
    for i in range(min(N + 1, l)):
        if x % B == 0:
            break
        x -= A
    else:
        return 0
    # print(i, N+1, l)
    result = 0
    for a in range(i, N + 1, l):
        b = (K - A * a) // B
        for x in range(max(0, a-b), min(N-b+1, a+1)):
            y = a - x
            z = b - y
            d = Fm[N] * inverseFm(x) * inverseFm(y) * inverseFm(z) * inverseFm(N - x - y - z) % M
            result = (result + d) % M
    return result 

def solve0(N, A, B, K):
    result = 0
    for x in range(0, N + 1):
        for y in range(0, N + 1 - x):
            for z in range(0, N + 1 - x - y):
                if A * x + (A + B) * y + B * z == K:
                    d = Fm[N] * inverseFm(x) * inverseFm(y) * inverseFm(z) * inverseFm(N - x - y - z) % M
                    result = (result + d) % M
    return result                   


def check():
    import random
    for i in range(10):
        N = random.randint(1, 20)
        A = random.randint(1, 20)
        B = random.randint(1, 20)
        K = random.randint(1, 20)
        r = solve(N, A, B, K)
        r0 = solve0(N, A, B, K)
        if r != r0:
            print(N, A, B, K, r, r0)

#check()
print(solve(N, A, B, K))
#print(solve0(N, A, B, K))

Submission status: Wrong Answer

Solution code:
import numpy as np
# import math

mod = 998244353

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


def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def lcm(a, b):
    """
    最小公倍数
    """
    return a * b / gcd(a,b)


# def main_old():
#     N, A, B, K = lii()
#     dp = np.zeros([N+1, K+1])
#     dp[:, 0] = 1
#     for n in range(1, N+1):
#         for k in range(K+1):
#             c = dp[n-1][k]
#             if k - A >= 0: c += dp[n-1][k-A]
#             if k - B >= 0: c += dp[n-1][k-B]
#             if k - (A+B) >= 0: c += dp[n-1][k-(A+B)]
#             dp[n][k] = c
#
#     print(int(dp[N][K]) % mod)


def solve_eucl(A, B, K, N):
    for _x in range(N):
        if (K - A * _x) % B == 0:
            x = _x
            y = (K - A * _x) // B
            return x, y


def comb(n, x):
    ans = 1
    x = min(x, n-x)
    for i in range(1, x+1):
        ans = (ans * (n - i + 1) // i) % mod
    return int(ans)


# def comb_mult(N, A, B, C):
#     a = int(comb(N, A)) % mod
#     b = int(comb(N-A, B)) % mod
#     c = int(comb(N-A-B, C)) % mod
#     return (a * b * c) % mod


def main():
    N, A, B, K = lii()
    if K == 0: return 1

    d = gcd(gcd(A, B), K)
    if d > 1:
        A = A // d
        B = B // d
        K = K // d

    x, y = solve_eucl(A, B, K, N)

    C = int(lcm(A, B))
    ans = 0
    p = x
    while True:
        q = (K - A * p) // B
        if q <= 0:
            break

        ans = (ans + comb(N, p) * comb(N, q)) % mod
        p += C // A
        if p > N:
            break

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
#
import sys
import math
import numpy as np
import itertools

n, a, b, k = (int(i) for i in input().split())  

answer =0
ta=[0]*(n+1)
ta[0]=1
q=1
m = (n+1) // 2
for i in range(1,m+1):
    q = (q * (n-i+1) ) % 998244353 
    j = 998244353-2
    ii = i
    while j > 0:
        if j % 2 == 1:
            q = (q * ii) % 998244353
        ii = (ii * ii) % 998244353
        j = j // 2
    ta[i]=q
for i in range(m+1,n+1):
    ta[i]= ta[n-i]
print(ta)
for i in range(0,n+1):
    if (k-i*a) % b ==0: 
        j= (k-i*a) // b
        if j <= n and j >= 0 :
            pp = (ta[i])*(ta[j])
#            print(i,j,pp)
            answer += pp
            answer = answer % 998244353
    else:
        continue

print(answer)

Submission status: Wrong Answer

Solution code:
import math
def combination(n, r):
    if n==0 or r ==0:
        return 1
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def comb_rgb(n, r, g, b):

    return math.factorial(n) // (math.factorial(r) * math.factorial(g) * math.factorial(b) *math.factorial(N-r-g-b)) % 998244353

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

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

waru = 998244353

ans = 0
r = 0
g = 0

if K%A == 0 and K//A <= N:
    r = K//A
    ans += comb_rgb(N, r,0,0)

if K%B == 0 and K//B <= N:
    b = K//B
    ans += comb_rgb(N,0,0,b)

r = 1
while r <= N and r*A <= K:
    b = (K - A*r) // B

    if r + b <= N and K == A*r + B*b:

        g = 0
#        print(r,g,b)
        ans += comb_rgb(N, r, g, b)
        for g in range(1,min(r,b)+1):
#            print(r,g,b)
            ans += comb_rgb(N, r-g, g, b-g)

    r += 1

print(ans%waru)

Submission status: Wrong Answer

Solution code:
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return f, invs


def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1

    while c1 != 0:
        m = c0 % c1
        q = c0 // c1

        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)

    return c0, a0, b0


def calc(n, x, y, f, invs, MOD):
    min_g = max(0, x + y - n)
    max_g = min(x, y)
    if min_g > max_g:
        return 0
    r, b = x - min_g, y - min_g
    t = n - (r + min_g + b)
    ans = 0
    for i in range(max_g - min_g + 1):
        tmp = f
        tmp *= invs[r - i] * invs[b - i]
        tmp %= MOD
        tmp *= invs[min_g + i] * invs[t + i]
        tmp %= MOD
        ans += tmp
        ans %= MOD

    return ans


def solve(n, a, b, k):
    if a < b:
        a, b = b, a
    c, x, y = ex_euclid(a, b)
    ac, bc = a // c, b // c
    d, m = divmod(k, c)
    if m != 0:
        return 0
    x, y = x * d, y * d
    if x < 0:
        f = ((x % bc) - x) // bc
        x += bc * f
        y -= ac * f
    if y > n:
        f = (y - n - 1) // ac + 1
        x += bc * f
        y -= ac * f

    MOD = 998244353
    f, invs = prepare(n, MOD)
    ans = 0
    while x <= n and y >= 0:
        ans += calc(n, x, y, f, invs, MOD)
        x += bc
        y -= ac
    return ans


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

print(solve(n, a, b, k))

Submission status: Wrong Answer

Solution code:
mod=998244353
N,A,B,K=map(int,input().split())
 
#繰り返し二乗法
def great_power(x, y):
    if   y == 0:
      return 1
    elif y == 1:
      return x % mod
    elif y % 2 == 0:
      return great_power(x, y//2)**2 % mod
    else:
      return great_power(x, y//2)**2 * x % mod

#階乗計算
factorial=[1]
for i in range(1,N+1):
    factorial.append(factorial[i-1]*i %mod)

#逆元計算
inverse=[0]*(N+1)
inverse[N] = great_power(factorial[N], mod-2)
for i in range(N-1, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod

#combination計算
def nCr(n,r):
  if n==r or n<r:
    return 1
  return factorial[n] * inverse[r] * inverse[n-r] % mod

def solve(a,b,c):
  res=nCr(N,a+b+c)
  res2=factorial[a+b+c] * inverse[a]*inverse[b]*inverse[c]
  return (res*res2)%mod

ans=[]
for i in range(N+1):
  if (K-A*i)%B==0 and i+(K-A*i)//B <=N:
    ans.append((i,(K-A*i)//B))

out=0
for x,y in ans:
  for i in range(min(x,y)+1):
    red,green,blue=x-i,i,y-i
    if red+green+blue <=N:
      out+=solve(red,green,blue)
print(out%mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import accumulate, islice


def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return f, invs


def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1

    while c1 != 0:
        m = c0 % c1
        q = c0 // c1

        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)

    return c0, a0, b0


def calc(n, x, y, div):
    min_g = max(0, x + y - n)
    max_g = min(x, y)
    if min_g > max_g:
        return 0
    r, b = x - min_g, y - min_g
    t = n - (r + min_g + b)
    for i in range(max_g - min_g + 1):
        key = tuple(sorted([r - i, b - i, min_g + i, t + i]))
        div[key] += 1


def solve(n, a, b, k):
    if a < b:
        a, b = b, a
    c, x, y = ex_euclid(a, b)
    ac, bc = a // c, b // c
    d, m = divmod(k, c)
    if m != 0:
        return 0
    x, y = x * d, y * d
    if x < 0:
        f = ((x % bc) - x) // bc
        x += bc * f
        y -= ac * f
    if y > n:
        f = (y - n - 1) // ac + 1
        x += bc * f
        y -= ac * f
    div = defaultdict(int)
    while x <= n and y >= 0:
        calc(n, x, y, div)
        x += bc
        y -= ac

    # print(div)

    MOD = 998244353
    f, invs = prepare(n, MOD)
    ans = 0
    for (r, g, b, t), cnt in div.items():
        tmp = f
        tmp *= invs[r]
        tmp *= invs[g]
        tmp %= MOD
        tmp *= invs[b]
        tmp *= invs[t]
        tmp %= MOD
        ans += tmp * cnt
        ans %= MOD
    return ans


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

print(solve(n, a, b, k))

Submission status: Wrong Answer

Solution code:
N,A,B,K=map(int,input().split())
count =0
shinA=A
shinB=B
firstcontact=True
B=max(shinA,shinB)
A=min(shinA,shinB)

if (A+B)*N<K:
    print(0)
    exit()
for i in range(N+1):
    if (A+B)*i >K:
        break
    
    for j in range(N-i+1):
        if (A+B)*i+B*j >K:
            break
        firstcontact=True
        for k in range(N-i-j+1):
            if A*k+B*j+(A+B)*i+0*(N-i-j-k)==K:
                count+=1
                count=count%998244353
            if A*k+B*j+(A+B)*i+0*(N-i-j-k)>K:
                break
            if firstcontact==True and i+j !=0:
                k=K//((B*j+(A+B)*i)*A)-1
                firstcontact=False
print(count)

Submission status: Wrong Answer

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

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]# }}}

def local_input():
    from pcm.utils import set_stdin
    import sys
    if len(sys.argv) == 1:
        set_stdin(os.path.dirname(__file__) + '/test/' + 'sample-3.in')

def solve():
    global F
    N,A,B,K = map(int, input().split())
    M = 998244353

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

    res = 0
    for p in range(N):
        D = K - (p*A)
        if D%B != 0:
            continue
        q = D//B
        if p + q > 2*N:
            continue
        G = min(p, q)
        for g in range(G+1):
            r = p-g
            b = q-g
            w = N - (r+g+b)
            if w >= 0:
                res += F[N]//(F[r]*F[g]*F[b]*F[w])
    print(res)


if __name__ == "__main__":# {{{
    try:
        local_input()
    except:
        pass
    solve()
# vim: set foldmethod=marker:}}}

Submission status: Wrong Answer

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

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

Y = set()
for n, m in X:
    for g in range(0, min(n, m) + 1):
        r = n - g
        b = m - g
        if r + g + b <= N:
            Y.add((r, g, b))

count = 0
for r, g, b in Y:
    count += factorial(N) // factorial(r) // factorial(g) // factorial(b) // factorial(N-r-g-b)

print(count % 998244353)

Submission status: Wrong Answer

Solution code:
N, A, B, K = [int(_) for _ in input().split()]

def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

L = 300000+1
M = 998244353

Fm = {}
inverseFm = {}
x = 1
for i in range(L):
    Fm[i] = x
    x = x * (i + 1) % M

def inverseFm(x, cache={}):
    if x in cache:
        return cache[x]
    result = pow(Fm[x], M - 2, M)
    cache[x] = result
    return result

def C(n, r):
    result = Fm[n] * inverseFm(r) * inverseFm(n - r) % M
    return result

def solve(N, A, B, K):
    x = K
    for i in range(N + 1):
        if x % B == 0:
            break
        x -= A
    else:
        return 0
    l = A * B // gcd(A, B)
    result = 0
    for a in range(i, N + 1, l):
        b = (K - A * a) // B
        for x in range(max(0, a-b), min(N-b+1, a+1)):
            y = a - x
            z = b - y
            d = Fm[N] * inverseFm(x) * inverseFm(y) * inverseFm(z) * inverseFm(N - x - y - z) % M
            result = (result + d) % M
    return result 

print(solve(N, A, B, K))

Submission status: Wrong Answer

Solution code:
N,A,B,K=map(int,input().split())
count =0
shinA=A
shinB=B
B=max(shinA,shinB)
A=min(shinA,shinB)

if (A+B)*N<K:
    print(0)
    exit()
for i in range(N+1):
    if (A+B)*i >K:
        break
    for j in range(N-i+1):
        if (A+B)*i+B*j >K:
            break
        for k in range(N-i-j+1):
            if A*k+B*j+(A+B)*i+0*(N-i-j-k)==K:
                count+=1
                count=count%998244353
            if A*k+B*j+(A+B)*i+0*(N-i-j-k)>K:
                break
print(count)

Submission status: Wrong Answer

Solution code:
n,a,b,k = map(int, input().split())
c = a+b
cnt = 0
for i in range(n+1):
    if c*i  > k:
        print(cnt%998244353)
        exit()
    for j in range(n-i+1):
        if c*i + b*j > k:
            break
        for m in range(n-i-j+1):
            if c*i + b*j + a*m > k:
                break
            if c*i + b*j + a*m == k:
                cnt += 1
print(cnt%998244353)

Submission status: Wrong Answer

Solution code:
N,A,B,K=map(int,input().split())
count =0
if (A+B)*N<K:
    print(0)
    exit()
for i in range(N+1):
    if (A+B)*i >K:
        break
    for j in range(N-i+1):
        if (A+B)*i+B*j >K:
            break
        for k in range(N-i-j+1):
            if A*k+B*j+(A+B)*i+0*(N-i-j-k)==K:
                count+=1
                count=count%998244353
            if A*k+B*j+(A+B)*i+0*(N-i-j-k)>K:
                break
print(count)

Submission status: Wrong Answer

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

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

Y = set()
for n, m in X:
    for g in range(0, min(n, m) + 1):
        r = n - g
        b = m - g
        Y.add((r, g, b))

count = 0
for r, g, b in Y:
    count += factorial(N) // (factorial(r) * factorial(g) * factorial(b) * factorial(N-r-g-b))

print(count % 998244353)

Submission status: Wrong Answer

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

for i in range(N+1):
    if (A+B)*i >K:
        break
    for j in range(N-i+1):
        if (A+B)*i+B*j >K:
            break
        for k in range(N-i-j+1):
            if A*k+B*j+(A+B)*i+0*(N-i-j-k)==K:
                count+=1
                count=count%998244353
            if A*k+B*j+(A+B)*i+0*(N-i-j-k)>K:
                break
print(count)

Submission status: Wrong Answer

Solution code:
N, A, B, K = [int(_) for _ in input().split()]

def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

L = 300000+1
M = 998244353

Fm = {}
inverseFm = {}
x = 1
for i in range(L):
    Fm[i] = x
    x = x * (i + 1) % M

def inverseFm(x, cache={}):
    if x in cache:
        return cache[x]
    result = pow(Fm[x], M - 2, M)
    cache[x] = result
    return result

def C(n, r):
    result = Fm[n] * inverseFm(r) * inverseFm(n - r) % M
    return result

def solve(N, A, B, K):
    for i in range(N + 1):
        x = K - A * i
        if x % B == 0:
            break
    else:
        return 0
    l = A * B // gcd(A, B)
    result = 0
    for a in range(i, N + 1, l):
        b = (K - A * a) // B
        for x in range(0, a + 1):
            y = a - x
            z = b - y
            if z >= 0 and x + y + z <= N:
                result = (result + C(N, x) * C(N - x, y) * C(N - x - y, z)) % M
    return result 

print(solve(N, A, B, K))

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

import math

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

l = []
for a in range(0, 300000//A):
    if a * A > K:
        break
    for b in range(0, 300000//B):
        if a * A + b * B > K:
            break
        if (K - a * A - b * B) % (A + B) == 0:
            c = (K - a * A - b * B) // (A + B)
            if a + b != 0 and b + c != 0 and c + a != 0:
                l.append((a, b, c))
            elif a + b + c == 0:
                l.append((0, 0, 0))


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

ans = 0
for pattern in l:
    tmp = 1
    j = 0
    for i in range(3):
        tmp *= combinations_count(N-j, pattern[i])
        j += pattern[i]
    ans += tmp
print(ans)

Submission status: Wrong Answer

Solution code:
N, A, B, K = map(int, input().split())
count = 0
for r in range(N):
    for g in range(N-r):
        for b in range(N-r-g):
            if A*(r+g) + B*(b+g) == K:
                count+= 1
            else:
                pass
print(count%998244353)

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
	if a > b:
		n,m = a,b
	else:
		n,m = b,a
	while m > 0:
		t = n % m
		n = m
		m = t
	return n

def gcd_3(a,b,c):
	return gcd(gcd(a,b),c)

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル

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

N,A,B,K = map(int,input().split())
g = gcd_3(A,B,K)
A = A // g
B = B // g
K = K // g
mod = 998244353 #出力の制限
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 )

ans = 0
n0,m0=-1,-1
for i in range(K//A + 1):
	if (K - A*i) % B == 0:
		n0,m0 = i, (K - A*i)//B
		break
k = 0
while k*B + n0 <= N and m0 - k*A >= 0:
	n,m = k*B + n0, m0 - k*A
	for green in range(min(n,m)+1):
		red = n - green
		blue = m - green
		if (red + green + blue) * g > N:
			continue
		ans = (ans + cmb(N,red,mod) * cmb(N-red,blue,mod) * cmb(N-red-blue,green,mod)) % mod
	k += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import math
import fractions

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
  
def modinv(a, m):
    inv, _, _ = egcd(a, m)
    return inv % m

def modc(a,b,m):
    c = 1
    for i in range(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c

def LCM(a, b):
    return a*b//fractions.gcd(a, b)

def indefinite_eq(n, a, b, k):
    na, nb = (-1, -1)
    for i in range(k//a+1):
        if (k-a*i)%b == 0:
            na = i
            nb = (k-a*i)//b
            break
    
    lcm = LCM(a, b)
    while True:
        if 0 <= na <= n and 0 <= nb <= n:    
            yield na, nb
            na += lcm // a
            nb -= lcm // b
        else: 
            break

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

    ans = 0
    for na, nb in indefinite_eq(N, A, B, K):
        ans +=  modc(N, na, MOD) * modc(N, nb, MOD) % MOD
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,A,B,K=map(int,input().split())
count =0
for i in range(N+1):
    for j in range(N-i+1):
        for k in range(N-i-j+1):
            if A*i+B*j+(A+B)*k+0*(N-i-j-k)==K:
                count+=1
                
print(count)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def inv(x):
    return pow(x, mod - 2, mod)

nm = {}
def nCr(n, b):
    if b > n - b:
        b = n - b
    if b in nm:
        return nm[b]
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    nm[b] = r * inv(d) % mod
    return nm[b]

def main():
    n,a,b,k = LI()
    r = 0
    for i in range(n+1):
        ai = a * i
        bi = k - ai
        if bi % b > 0 or bi // b > n:
            continue
        bb = bi // b
        r += nCr(n,i) * nCr(n,bb)
        r %= mod

    return r


print(main())

Submission status: Wrong Answer

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
MM = 10**6

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

def inv(x):
  return pow(x, P-2, P)

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

setrecursionlimit(100000)

N, A, B, K = reads()

result = 0
for x in range(N+1):
  if (K - A * x) % B != 0:
    continue
  y = (K - A * x) // B
  if not (0 <= y <= N):
    continue
  result = (result + comb(N, x) * comb(N, y)) % P

print(result)

Submission status: Wrong Answer

Solution code:
N,A,B,K=map(int,input().split())
P=998244353
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(1,N+1):
    Fact[i]=(i*Fact[i-1])%P
    Finv[i]=(Finv[i-1]*inv(i))%P
def NC(k):
    tmp=(Finv[k]*Finv[N-k])%P
    return (Fact[N]*tmp)%P
ans=0
for s in range(N+1):
    t=(K-s*A)//B
    if s*A+t*B==K and 0<=t<=N:
        ans+=(NC(s)*NC(t))%P
print(ans)

Submission status: Wrong Answer

Solution code:
n,a,b,k = map(int, input().split())
c = a+b
cnt = 0
for i in range(n+1):
    if a*i  > k:
        print(cnt%998244353)
        exit()
    for j in range(n-i+1):
        if a*i + b*j > k:
            break
        for m in range(n-i-j+1):
            if a*i + b*j + c*m > k:
                break
            if a*i + b*j + c*m == k:
                cnt += 1
print(cnt%998244353)

Submission status: Wrong Answer

Solution code:
N,A,B,K=map(int,input().split())
P=998244353
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(1,N+1):
    Fact[i]=(i*Fact[i-1])%P
    Finv[i]=(Finv[i-1]*inv(i))%P
ans=0
def NC(k):
    tmp=(Finv[k]*Finv[N-k])%P
    return (Fact[N]*tmp)%P
for x in range(N+1):
    y=(K-x*A)//B
    if x*A+y*B==K and 0<=y<=N:
        ans+=(NC(x)*NC(y))%P
print(ans)

Submission status: Wrong Answer

Solution code:
N,A,B,K=map(int,input().split())
P=998244353
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(1,N+1):
    Fact[i]=(i*Fact[i-1])%P
    Finv[i]=(Finv[i-1]*inv(i))%P
ans=0
def NC(k):
    tmp=(Finv[k]*Finv[N-k])%P
    return (Fact[N]*tmp)%P
for x in range(N):
    y=(K-x*A)//B
    if x*A+y*B==K and 0<=y<=N:
        ans+=(NC(x)*NC(y))%P
print(ans)