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: Runtime Error

Solution code:
from math import factorial


def combinations(a, b, c, d):
    bunshi = factorial(a + b + c + d)
    bunbo = (factorial(a) * factorial(b) * factorial(c) * factorial(d))
    # print(bunshi/bunbo)
    return int((bunshi/bunbo) % 998244353)


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

coef = []
if A > B:
    for coef_A in range(0, int(K / A) + 1):
        if (K - A * coef_A) % B == 0:
            coef_B = int((K - A * coef_A) / B)
            if coef_A + coef_B <= N:
                coef.append((coef_A, coef_B))
else:
    for coef_B in range(0, int(K / B) + 1):
        if (K - B * coef_B) % A == 0:
            coef_A = int((K - B * coef_B) / A)
            if coef_A + coef_B <= N:
                coef.append((coef_A, coef_B))
# print(coef)

num_color = []

cum = 0

for coef_A, coef_B in coef:
    for num_G in range(min(coef_A, coef_B) + 1):
        num_R = coef_A - num_G
        num_B = coef_B - num_G
        # num_color.append((num_R, num_G, num_B, N-(num_R+num_G+num_B)))
        # print(num_R, num_G, num_B, N-(num_R+num_G+num_B))
        cum += combinations(num_R, num_G, num_B, N - (num_R + num_G + num_B))

print(cum)

Submission status: Runtime Error

Solution code:
def main():
    N,A,B,K = map(int, raw_input().split())

    inf=float("inf")
    dp=[[inf for j in range(N+1)] for i in range(K+1)]
    dp[0][0]=1
    #for i in range(K+1):
    #    dp[i][0] = 0

    def access(i,j):
        if i < 0 or j < 0:
            return 0
        if dp[i][j] != inf:
            return dp[i][j]
        else:
            dp1 = access(i-A,j-1)
            dp2 = access(i-B,j-1)
            dp3 = access(i-A-B, j-1)
            dp4 = access(i,j-1)
            #dp[i][j] = dp[i-A][j-1] + dp[i-B][j-1] + dp[i][j-1]
            dp[i][j] = (dp1 + dp2 + dp3 + dp4) % 998244353

    for i in range(K+1):
        for j in range(N+1):
            access(i,j)
    print(dp[K][N])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

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


def solve0(N, A, B, K):
    result = 0
    for r in range(0, N + 1):
        for g in range(0, N + 1 - r):
            for b in range(0, N + 1 - r - g):
                if A * r + (A + B) * g + B * b == K:
                    result += 0
    return result

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

#from collections import defaultdict
#xs = defaultdict(int)

L = 300000

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) % M
    return result 

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

Submission status: Runtime Error

Solution code:
from math import factorial


def combinations(a, b, c, d):
    bunshi = factorial(a + b + c + d)
    bunbo = (factorial(a) * factorial(b) * factorial(c) * factorial(d))
    # print(bunshi/bunbo)
    return int((bunshi/bunbo) % 998244353)


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

coef = []

for coef_A in range(0, int(K / A) + 1):
    if A * coef_A > K:
        break
    if (K - A * coef_A) % B == 0:
        coef_B = int((K - A * coef_A) / B)
        if coef_A + coef_B <= N:
            coef.append((coef_A, coef_B))

# print(coef)

num_color = []

cum = 0

for coef_A, coef_B in coef:
    for num_G in range(min(coef_A, coef_B) + 1):
        num_R = coef_A - num_G
        num_B = coef_B - num_G
        # num_color.append((num_R, num_G, num_B, N-(num_R+num_G+num_B)))
        # print(num_R, num_G, num_B, N-(num_R+num_G+num_B))
        cum += combinations(num_R, num_G, num_B, N - (num_R + num_G + num_B))

print(cum)

Submission status: Runtime Error

Solution code:
from scipy.special import perm, comb
li = input().split()
N=int(li[0])
A=int(li[1])
B=int(li[2])
K=int(li[3])
count=0
for i in range (N+1):
    for k in range(N+1):
        if((A+B)*N-A*i-B*k==K):
            ca=comb(N, i, exact=True)
            cb=comb(N,k,exact=True)
            count=count+ca*cb
print(count%998244353)

Submission status: Runtime Error

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 = n // 2 + 1
    r = 1
    d = 1
    for k in range(1,b+1):
        r = r * (n-k+1) % mod
        d = d * k % mod
        nm[k] = r * inv(d) % mod

def nCr(n, b):
    if b > n - b:
        b = n - b
    return nm[b]

def main():
    n,a,b,k = LI()
    r = 0
    nCr_(n)
    for i in range(n+1):
        ai = a * i
        bi = k - ai
        if bi < 0 or 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: Runtime Error

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

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

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//math.gcd(a, b)

def indefinite_eq(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

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

print(ans)

Submission status: Runtime Error

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

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

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 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, q, gcd_val) = egcd(a, m)
    return inv % m

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

def indefinite_eq(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

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

print(ans)

Submission status: Runtime Error

Solution code:
MOD = 998244353

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

A,B = sorted((A,B))

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

# tabulate combinations



# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


memo = [0]*(N+1)
memo[0] = memo[N] = 1
for k in range(1,N//2+1):
  v = memo[k-1]*(N-k+1)*modinv(k,MOD)
  v %= MOD
  memo[k] = memo[N-k] = v

cnt = 0

for b in range((max(0,K-N*A)-1)//B+1, (K-1)//B+1):
  a = (K-b*B)//A
  if a*A+b*B == K:
    cnt += memo[a]*memo[b]
    cnt %= MOD

print(cnt)

Submission status: Runtime Error

Solution code:
N, A, B, K = map(int, input().split())
RED = A
GREEN = A + B
BLUE = B
count = 0
li = [1]
for i in range(1, N+1):
    li.append(list_fact[i-1] * i)
for i in range(N+1):
    for j in range(N-i+1):
        for k in range(N-i-j+1):
            if (RED*i + GREEN*j + BLUE*k == K):
                count += li[N]/(li[N-i-j-k]*li[i]*li[j]*li[k])
print(int(count) % 998244353)

Submission status: Runtime Error

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

LARGE = 998244353
INVS = [0]*(N+1)
for i in range(1, N+1):
    INVS[i] = pow(i, LARGE-2, LARGE)
NCKL = [1]*(N+1)
for i in range(1, N+1):
    NCKL[i] = (NCKL[i-1] * (N+1-i) * INVS[i]) % LARGE

res = 0
for i in range(N+1):
    if (K - A*i) % B == 0:
        j = (K - A*i) // B
        res += (NCKL[i] * NCKL[j]) % LARGE
print(res % LARGE)

Submission status: Runtime Error

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

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

ans = 0
for a in range(N+1):
    if (K - a*A) >= 0 and (K - a*A) % B == 0:
        b = (K - a*A) // B
        ans += rev[a]*rev[N-a] * rev[b]*rev[N-b]
        ans %= MOD
ans *= fact[N]*fact[N]
ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 998244353;

ll ncr[300005];
ll fact[300005];
ll inv[300005];

ll ex(ll a, ll b)
{
	if (b == 0) return 1;
	ll r = ex(a, b>>1);
	r *= r; r %= MOD;
	if (b&1) r = (r*a)%MOD;
	return r;
}

int main()
{
	ll n, a, b, k, ans = 0;
	cin >> n >> a >> b >> k;

	fact[0] = 1; inv[0] = 1;
	for (ll i = 1;i <= n;i++)
	{
		fact[i] = fact[i-1]*i; fact[i] %= MOD;
		inv[i] = ex(fact[i], MOD-2);
	}
	for (ll i = 0;i <= n;i++)
	{
		ncr[i] = fact[n]*inv[i];
		ncr[i] %= MOD;
		ncr[i] *= inv[n-i];
		ncr[i] %= MOD;
	}

	for (ll i = 0;i <= n;i++)
	{
		ll rem = k-i*a;
		if (rem >= 0 && rem%b == 0)
		{
			ans += ncr[i]*ncr[rem/b];
			ans %= MOD;
		}
	}
	cout << ans << endl;
	return 0;
}