Problem:


Score : 700 points

Problem Statement

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

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

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

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

Constraints

1 ≤ N ≤ 3×10^5

1 ≤ A,B ≤ 3×10^5

0 ≤ K ≤ 18×10^{10}

All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N A B K

Output

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

Sample Input 1

4 1 2 5

Sample Output 1

40

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

1 green, 1 blue

1 red, 2 blues

2 reds, 1 green

3 reds, 1 blue

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

Sample Input 2

2 5 6 0

Sample Output 2

1

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

Sample Input 3

90081 33447 90629 6391049189

Sample Output 3

577742975



Sample input:
4 1 2 5


Sample output:
40

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
from fractions import gcd


n, a, b, k = map(int, input().split())
a, b = max(a, b), min(a, b)
q = 998244353

n_ = n % q
d = gcd(a, b)

ans = 0
j = -1
for i in range(min(n, k // a) + 1):
    res = k - i * a
    #if res < 0:
    #    break
    if res % b == 0:
        j = i
        break

if j == -1:
    print(0)
    exit()
for i in range(j, min(n, k // a) + 1, b // d):
    res = k - i * a
    ans += (comb(n_, i % q, True) * comb(n_, (res // b) % q, True)) % q
        
print(ans)

Submission status: Time Limit Exceeded

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

cache = {}
def modc(a,b,m):
    if b in cache:
        return cache[b]
    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 diophantine(a,b,c):
    q, r = divmod(a, b)
    if r==0:
        return 0, c//b
    else:
        u, v = diophantine(b, r, c)
        return v, u-q*v

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

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)
        ans %= MOD
    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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=[1]
q=1
for i in range(1,n+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.append(q)

#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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

nmemo = [0 for i in range(n+1)]
def permutation(n):
    if nmemo[n] != 0:
        return nmemo[n]
    if n == 0:
        return 1
    nmemo[n] = n * permutation(n-1)
    return nmemo[n]


memo = []
ans = 0

for i in range(n + 1):
    knum = k - b * i
    if k < 0:
        break
    if knum % a == 0:
        if knum//a + i <= 2 * n:
            memo.append([knum // a, i])

for i in memo:
    nmin = min(i[0], i[1])
    jmin = 0
    if i[0] + i[1] > n:
        jmin = i[0] + i[1] - n
    for j in range(jmin, nmin+1):
        if (i[0] + i[1] - j) <= n:
            ans += permutation(n) // (permutation(i[0] - j) * permutation(i[1] - j)
                                      * permutation(j) * (permutation(n - (i[0] - j + i[1]))))

if k == 0:
    print(1)
else:
    print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import math
def C(n,k):
    return math.factorial(n)//math.factorial(k)//math.factorial(n-k)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, A, B, K = map(int, input().split())
red_blue = []
for i in range(N):
    if K < A * i:
        break
    if (K - A * i) % B == 0:
        red_blue.append([i, int((K - A * i) / B)])
cnt = 0
for red, blue in red_blue:
    max_green = min(red, blue)
    for green in range(max_green + 1):
        blocks = red + blue - green
        if red + blue - green <= N:
            c = len(tuple(itertools.combinations(range(N), blocks)))
            p = len(tuple(itertools.permutations(range(blocks)))) / len(tuple(itertools.permutations(range(red-green)))) / len(tuple(itertools.permutations(range(blue-green)))) / len(tuple(itertools.permutations(range(green))))
            cnt += int(c * p % 998244353)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def nCr(n, r):
    r = min(r, n - r)
    numerator = 1
    for i in range(n, n - r, -1):
        numerator *= i
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator


@mt
def slv(N, A, B, K):
    ans = 0
    for i in range(K // A + 1):
        if (K - i * A) % B == 0 and i <= N and (K - i * A) // B <= N:
            error_print(i, (K - i * A) // B)
            ans += nCr(N, i) * nCr(N, (K - i * A) // B) % 998244353

    return ans


def main():
    N, A, B, K = read_int_n()
    print(slv(N, A, B, K))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 diophantine(a,b,c):
    q, r = divmod(a, b)
    if r==0:
        return 0, c//b
    else:
        u, v = diophantine(b, r, c)
        return v, u-q*v

def indefinite_eq(n, a, b, k):
    na, nb = diophantine(a, b, k)
    lcm = LCM(a, b)
    na %= lcm // a
    nb = (k - na*a)//b
    while True:
        if 0 <= na <= n and 0 <= nb <= n:
            yield na, nb
        elif nb < 0:
            break
        na += lcm // a
        nb -= lcm // b

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: Time Limit Exceeded

Solution code:
n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

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

#以下のcom関数を用いて組み合わせを計算
def com(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

#test=2*3*com(4, 2, mod) + com(4,3,mod)
#print(test)

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
        
        n_c=min(n_a,n_b)
        n_a, n_b=n_a-min(n_a,n_b), n_b-min(n_a,n_b)

        while n_a + n_b + n_c <=n and n_c>=0 and n_b>=0 and n_a>=0:
            ans+=com(n, n_c, mod) * com(n-n_c, n_b, mod) * com(n-n_c-n_b, n_a, mod)
            n_c-=1
            n_b+=1
            n_a+=1

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:

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

ok = set()
ok2 = set()

mod = 998244353

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

fact = [1] * (3 * 100000 + 1)
for i in range(1, 3 * 100000 + 1):
    fact[i] = mul(fact[i - 1], i)

for i in range(N):
    if (K - A * i) % B == 0 and (K - A * i) // B >= 0:
        ok.add((i, (K - A * i) // B))

for i, j in ok:
    for k in range(i + 1):
        if k <= i and k <= j:
            ok2.add((i - k, k, j - k))

ans = 0
for i, j, k in ok2:
    l = N - i - j - k
    if l >= 0:
        ans = (ans + div(fact[N], mul(mul(mul(fact[i], fact[j]), fact[k]), fact[l]))) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
score = 0

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

import operator as op
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, xrange(n, n-r, -1), 1)
    denom = reduce(op.mul, xrange(1, r+1), 1)
    return numer//denom


patterns = 0
for green in xrange(n +1):
    if green * (a+ b ) > k :
        break
    for red in xrange(n -green + 1):
        for blue in xrange(n-red-green + 1):
            if k ==red * a + green * (a + b) + blue * b:
                patterns += ncr(n,red) * ncr(n-red,green) * ncr(n-red-green, blue)

print patterns % 998244353

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

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

a, b = max(a, b), min(a, b)

ans = 0

n_ = n % 998244353

for i in range(min(n, k // a) + 1):
    res = k - i * a
    if 0 <= res <= k and res % b == 0:
        ans += comb(n_, i % 998244353, True) * comb(n_, res // b % 998244353, True)
        ans %= 998244353
        
print(ans)

Submission status: Time Limit Exceeded

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

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

ans = 0
for x in range(N+1):
  rest = K - A*x
  if rest % B == 0:
    y = rest // B
    for g in range(max(0, x+y-N), min(x, y)+1):
      r = x - g
      b = y - g
      ans += (fact[N] // fact[r] // fact[g] // fact[b] // fact[N-r-g-b]) % 99824
4353

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as f

N, A, B, K = list(map(int, input().split()))
M = 998244353
fN = f(N)%M

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

#def f(n):
#    return factorial(n)#%M

#def combi(n, r):
#    return f(n)//(f(r)*f(n-r))

def add(a, b, c):
    tmp = fN
    div = f(a)*f(b)*f(c)*f(N-a-b-c)
    return (tmp//div)%M

pair = []
for i in range(N+1):
    if A*i>K:
        break
    if (K-A*i)%B==0:
        pair.append((i, (K-A*i)//B))
#print(pair)

ans = 0
for x,y in pair:
    if x>y:
        x,y = y,x
    for c in range(0, x+1):
        a = x - c
        b = y - c
        if a+b+c>N:
            continue
        #print(a,b,c)
        ans += add(a,b,c)

print(ans%M)

Submission status: Time Limit Exceeded

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

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
#fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
#    fac_inv.append(inv(f))

def ncr(n,r):
    return mul(mul(fac[n], inv(fac[n-r])), inv(fac[r]))

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    for green in range(min(a,b) + 1):
        red = a - green
        blue = b - green
        if red + green + blue > N: continue
        tmp = 1
        tmp = mul(tmp, ncr(N, red+green+blue))
        tmp = mul(tmp, ncr(red+green+blue, green+blue))
        tmp = mul(tmp, ncr(green+blue, blue))
        ans += tmp
print(ans % MOD)

Submission status: Time Limit Exceeded

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

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,4*10**5):
    f = mul(fac[n-1], n)
    fac.append(f)
    fac_inv.append(inv(f))

def ncr(n,r):
    return mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    for green in range(min(a,b) + 1):
        red = a - green
        blue = b - green
        if red + green + blue > N: continue
        tmp = 1
        tmp = mul(tmp, ncr(N, red+green+blue))
        tmp = mul(tmp, ncr(red+green+blue, green+blue))
        tmp = mul(tmp, ncr(green+blue, blue))
        ans += tmp
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

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

a, b = max(a, b), min(a, b)

ans = 0

for i in range(min(n, k // a) + 1):
    res = k - i * a
    if 0 <= res <= k and res % b == 0:
        ans += comb(n, i, True) * comb(n, res // b, True)
        ans %= 998244353
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def combo(m,n):
    ans=1
    for i in range(n+1,m+1):
        ans*=i
    for i in range(1,(m-n+1)):
        ans=ans//i
    return ans

num=input().split()
N=int(num[0])
A=int(num[1])
B=int(num[2])
K=int(num[3])
res=0
tim=min(K//A,N)

for i in range(0,tim+1):
    if (K-i*A)%B==0:
        m=i
        n=(K-i*A)//B
        if m+n>2*N:
            continue
        for j in range(0,min(m+1,n+1)):
            if m+n-j>N:
                continue
            # print(j,m-j,n-i)
            res=res+combo(N,j)*combo(N-j,m-j)*combo(N-m,n-j)
            res=res%998244353
print(res)

Submission status: Time Limit Exceeded

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=[1]
q=1
for i in range(1,n+1):
    q = q * (n-i+1) // i
    ta.append(q)



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: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from collections import Counter
from pprint import pprint as pp
import itertools
import math

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N, A, B, K = ria()
N_ = math.factorial(N)

ret = 0
for r in range(K//A+1):
  b,m = divmod(K-r*A, B)
  if m != 0:
    continue
  n = N-(r+b)
  for g in range(min(r,b)+1):
    if n >= 0:
      ret += N_ // (math.factorial(r)*math.factorial(g)*math.factorial(b)*math.factorial(n))
    r -= 1
    b -= 1
    n += 1

print(ret % 998244353)

Submission status: Time Limit Exceeded

Solution code:

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

ok = set()
ok2 = set()

mod = 998244353

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

fact = [1] * (3 * 100000 + 1)
for i in range(1, 3 * 100000 + 1):
    fact[i] = mul(fact[i - 1], i)

for i in range(N):
    if (K - A * i) % B == 0:
        ok.add((i, (K - A * i) // B))


for i, j in ok:
    for k in range(i + 1):
        if k <= i and k <= j:
            ok2.add((i - k, k, j - k))

ans = 0

for i, j, k in ok2:
    l = N - i - j - k
    if l >= 0:
        ans = (ans + div(fact[N], mul(mul(mul(fact[i], fact[j]), fact[k]), fact[l]))) % mod

print(ans)

Submission status: Time Limit Exceeded

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

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

count = 0
num_AB = -1
while True:
    num_AB += 1
    if num_AB * (A+B) > K:
        break

    left_beauty = K - num_AB * (A+B)

    num_A = -1
    while True:
        num_A += 1
        # print("left_b: {}".format(left_beauty))
        if num_A * A > left_beauty:
            break
        elif num_A > N:
            break
        else:
            left_left_beauty = left_beauty - num_A * A

            if left_left_beauty % B == 0:
                num_B = int(left_left_beauty / B)
                num_nan = N - num_AB - num_A - num_B

                all_comb = kaijo(N)/(kaijo(num_AB)*kaijo(num_A)*kaijo(num_B)*kaijo(num_nan))
                count += int(all_comb)
                # print(num_A, num_B, num_AB, num_nan)
                # print(all_comb)

# print("=====")
print(count % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import math

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

results = []
for x in range(N):
	for y in range(N):
		for z in range(N):
			if x + y + z <= N:
				result = A * (x + z) + B * (y + z)
				if result == K:
					results.append([x, y, z, N - (x + y + z)])


last = 0
facN = math.factorial(N)
for result in results:
	tmp = 1
	for i in result:
		tmp = tmp * (math.factorial(i))
	
	last = last + (facN / tmp)
print(int(last) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

N, A, B, K = map(int, input().split())
# N = int(input())
# S = input()
# N = 6
# S = 'aabbca'
# N, A, B, K = map(int, '4 1 2 5'.split())

pairs = []

for i in range(int(K/A) + 1):
    test = K - i * A
    if test % B == 0:
        b_kosu = test // B
        pairs.append([i, b_kosu])

gokei = 0
for pair in pairs:
    minimum = min(pair[0], pair[1])
    for green in range(minimum + 1):
        kosu_gokei = pair[0] + pair[1] - green
        if kosu_gokei <= N:
            # print(pair[0] - green, pair[1] - green, green, N - kosu_gokei)
            gokei += (factorial(N) // factorial(green) // factorial(pair[0] - green) // factorial(pair[1] - green) // factorial(N - (kosu_gokei)))

print(gokei % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def nCr(n, r):
    r = min(n-r,r)
    if(r == 0): return 1
    over, under = 1, 1
    for i in range(n, n-r, -1):
        over *= i
    for i in range(1, r+1):
        under *= i
    return over//under

n, a, b, k = map(int, input().split())
ls= []
ans = 0
for x in range(n+1):
    for y in range(n-x+1):
        z = k - a*x - b*y
        if(z >= 0 and z%(a+b)==0):
            z = z//(a+b)
            ls.append([x, y, z])
for l in ls:
    m = n
    x = 1
    for i in range(3):
        x *= nCr(m, l[i])
        m -= l[i]
    ans = (ans + x)%998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
S = []
def selectG(key):
    for i in range(int(key / g) + 1):
        if i > N:
            braek
        selectR(key - g * i, i)
        
def selectR(key, G):
    for i in range(int(key / r) + 1):
        if i + G > N:
            break
        selectB(key - r * i, G, i)

def selectB(key, G, R):
    if key % b == 0:
        S.append([G, R, int(key / b)])

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

N, A, B, K = map(int, input().split())
r = A
g = A + B
b = B
if r > b:
    r, b = b, r

n = N
selectG(K)
count = 0
cnt = 1
for i in S:
    for j in i:
        cnt *= combinations_count(n, j)
        n -= j
    n = N
    count += cnt
    cnt = 1
    
print(count % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def combo(m,n):
    ans=1
    for i in range(n+1,m+1):
        ans*=i
    for i in range(1,(m-n+1)):
        ans=ans//i
    return ans


num=input().split()
N=int(num[0])
A=int(num[1])
B=int(num[2])
K=int(num[3])
res=0
tim=K//A
# print(combo(4,3))
for i in range(0,tim+1):
    if (K-i*A)%B==0:
        m=i
        n=(K-i*A)//B
        for j in range(0,min(m+1,n+1)):
            if m+n-j>N:
                continue
            # print(j,m-j,n-i)
            res=res+combo(N,j)*combo(N-j,m-j)*combo(N-m,n-j)
            res=res%998244353
print(res)

Submission status: Time Limit Exceeded

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
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 = (math.factorial(n)// math.factorial(n-i)//math.factorial(i))*(math.factorial(n)// math.factorial(n-j)//math.factorial(j))
#            print(i,j,pp)
            answer += pp
            answer = answer % 998244353
    else:
        continue

print(answer)

Submission status: Time Limit Exceeded

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 < 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: Time Limit Exceeded

Solution code:
import numpy as np
import math

N,A,B,K=input().split(' ')

N=int(N)
A=int(A)
B=int(B)
K=int(K)

a=np.arange(N+1)
b=np.arange(N+1)
c=np.arange(N+1)

a_score=a*A
b_score=b*B
c_score=c*(A+B)

arr=[]
for i in range(N+1):
	for j in range(N+1-i):
		for k in range(N+1-i-j):
			if a_score[i]+b_score[j]+c_score[k]==K:
				arr.append([i,j,k])

def combination(n,k):
	return math.factorial(n)/(math.factorial(k)*math.factorial(n-k))

num=0
for i in range(np.shape(arr)[0]):
	num1=1
	n=0
	for j in range(np.shape(arr)[1]):
		num1=num1*combination(N-n,arr[i][j])
		n=n+arr[i][j]
	num=num+num1
print(int(num)%998244353)

Submission status: Time Limit Exceeded

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

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

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

P = 998244353

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


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

def comb(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: Time Limit Exceeded

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(li[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: Accepted

Solution code:
def nCr(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

mod = 998244353 #出力の制限
size = 10**6 # size >= n
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


N, A, B, K = map(int,input().split())
ans = 0
for k in range(N + 1):
    if A * k > K:
        break
    if (K - A * k) % B != 0:
        continue
    l = (K - A * k) // B
    ans += nCr(N,k,mod) * nCr(N,l,mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
mod = 998244353
N,A,B,K = map(int,input().split())
def cmb(n,k):
    return fac[n]*inv_fac[n-k]*inv_fac[k] % mod
fac = [1]
for i in range(1,N+1):
    fac.append(fac[-1]*i % mod)
inv_fac = [pow(fac[N],mod-2,mod)]
for i in range(1,N+1)[::-1]:
    inv_fac.append(inv_fac[-1]*i % mod)
inv_fac = inv_fac[::-1]

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

Submission status: Accepted

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

fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,n+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

def nPr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[n-r]%mod


ans = 0
for i in range(n+1):
    if i*a > k:
        break
    d = k-i*a
    if d%b or d//b > n:
        continue
    ans += nCr(n,i,mod)*nCr(n,d//b,mod)%mod
    ans %= mod
print(ans)

Submission status: Accepted

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

MOD = 998244353
N = n + 10
fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD
        
ans = 0
for i in range(n + 1):
    j = (kk - a * i)
    if j % b != 0:
        continue
    ans += nCk(n, i) * nCk(n, j // b)
    ans %= MOD
    
print(ans)

Submission status: Accepted

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

MOD = 998244353
factorials = [1]
inv_facts = [1]
for i in range(1, N+1):
    factorials.append(factorials[-1] * i % MOD)
    inv_facts.append(inv_facts[-1] * pow(i, MOD-2, MOD) % MOD)

def combi(n, k):
    ret = factorials[n]
    ret *= inv_facts[k]
    ret %= MOD
    ret *= inv_facts[n-k]
    ret %= MOD
    return ret

ans = 0
for a in range(N+1):
    rest = K - (A * a)
    if rest < 0:
        break
    if rest % B == 0:
        b = rest // B
        if b <= N:
            tmp = combi(N, a) * combi(N, b) % MOD
            ans += tmp
            ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

#nCrをmodで割った余りを求める。Nに最大値を入れて使用。
N = 3*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
def cmb(n,r,mod=998244353):
    if r<0 or r>n :
        return 0
    r = min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod
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 main():
    ans = 0
    n,a,b,k = map(int,ipt().split())
    for xa in range(n+1):
        if (k-a*xa)%b == 0:
            xb = (k-a*xa)//b
            if 0 <= xb <= n:
                ans += cmb(n,xa)*cmb(n,xb)

    print(ans%mod)

    return None

if __name__ == '__main__':
    main()