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:
# https://agc025.contest.atcoder.jp/tasks/agc025_b
import math


def combinations_count(n, r):
    if r == 0:
        return 1
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

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


BASE = 998244353

RED = A
GREEN = A + B
BLUE = B


candidates = []

a_count = 0
val = K
while val >= 0:
    if val % B == 0:
        b_count = val // B
        candidates.append((a_count, b_count))

    val -= A
    a_count += 1


candidates = list(filter(lambda x: x[0] * RED + x[1] * BLUE == K and x[0] <= N and x[1] <= N, candidates))

# print(candidates)


total = 0
for c in candidates:
    a_pattern = combinations_count(N, c[0])
    b_pattern = combinations_count(N, c[1])
    total += a_pattern * b_pattern

print(total % BASE)

Submission status: Time Limit Exceeded

Solution code:
import math
def combination(n, r ,b):
    return math.factorial(n)**2 // (math.factorial(n - r) * math.factorial(r) * math.factorial(n - b) * math.factorial(b))

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

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

waru = 998244353

ans = 0

r = 0

while r <= N and r*A <= K:
    b = (K - A*r) // B
    if b <= N and K == A*r + B*b:
        ans += combination(N, r, b) % waru

    r += 1

print(ans%waru)

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
        res+=combo(N,m)*combo(N,n)
        res=res%998244353
print(res)

Submission status: Time Limit Exceeded

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))

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 += combination(N, r) % waru

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

r = 1
while r <= N and r*A <= K:
    b = (K - A*r) // B
    if r <= N and b <= N and K == A*r + B*b:
        ans += combination(N, r)*combination(N,b) % waru

    r += 1

print(ans%waru)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, A, B, K] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2]), long(input_raw[3])]
    cnt = 0
    li = []
    for t in range(N + 1):
        if (K - t * A)%B == 0:
            u = (K - t * A)/B
            for y in range(t + u - N, N + 1):
                x = t - y
                z = u - y
                w = N -(x + y + z)
                if w >= 0 and x >= 0 and y >= 0 and z >= 0:
                    li.append((w, x, y, z))

                    #print w, x, y, z
                    #print x * A + y *(A + B) + z * B
    frac_N = [0 for i in range(N + 1)]
    power_N = [0 for i in range(N + 1)]
    frac_N[0] = 1
    power_N[0] = 1
    p = 998244353L
    for i in range(1, N + 1):
        frac_N[i] = (frac_N[i - 1] * i ) % p
        power_N[i] = -1

    s = 0L
    for i in range(len(li)):
        w = li[i][0]
        x = li[i][1]
        y = li[i][2]
        z = li[i][3]
        if power_N[x] == -1:
            power_N[x] = power_func(frac_N[x], p - 2, p)
        if power_N[y] == -1:
            power_N[y] = power_func(frac_N[y], p - 2, p)
        if power_N[z] == -1:
            power_N[z] = power_func(frac_N[z], p - 2, p)
        if power_N[w] == -1:
            power_N[w] = power_func(frac_N[w], p - 2, p)
        s = (s + (frac_N[N] * power_N[x] * power_N[y] * power_N[z] * power_N[w])) % p
    print s


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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
    result = 0
    for a in range(i, N + 1, B):
        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
  #          print("s", x, y, z)
            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:
 #                   print("s0", x, y, z)
                    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(100):
        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: Time Limit Exceeded

Solution code:
N,A,B,K = map(int,input().split())
if A<B: A,B = B,A
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))

mem = {}
def ncr(n,r):
    if (n,r) in mem:
        return mem[(n,r)]
    else:
        ret = mul(mul(fac[n], inv(fac[n-r])), inv(fac[r]))
        if len(mem) <= 10**5:
            mem[(n,r)] = ret
        return ret

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:
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(set(itertools.permutations([0] * (red - green) + [1] * (blue - green) + [2] * green)))
            cnt += c * p % 998244353
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, A, B, k = map(int, input().split())
count = 0
p =  998244353
import math
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
def com(r, g, b):
    return comb(n, r, p)*comb(n-r, g, p)*comb(n-r-g, b, p)
for r in range(0, n):
    for g in range(0, n):
        b =(k-A*r-(A+B)*g)/B
        if b < 0:
            break
        if b == math.floor(b):
            count = count + com(r, g, b)
        else:
            continue
print(count % 998244353)

Submission status: Time Limit Exceeded

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

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

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

if k % d != 0:
    print(0)
    exit()

ans = 0
j = -1
for i in range(min(n, k // a) + 1):
    res = k - i * a
    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:
import math
N,A,B,K = map(int,input().split())

rbpairs = [[]]

for i in range(2*N):
	for j in range(2*N):
		if i+j <= 2*N and i*A+j*B == K:
			rbpairs.append([i,j])

rbpairs.pop(0)

rgbtlists = [[]]
for i in range(len(rbpairs)):
	pair = rbpairs[i]
	#print(pair)
	for j in range(min(pair[0],pair[1])+1): #try inverse iteration
		rgbt = [pair[0]-j,j,pair[1]-j,N+j-pair[0]-pair[1]]
		#print(rgbt)
		if rgbt[3] >= 0 and rgbt[0]+rgbt[1]+rgbt[2] <= N:
			rgbtlists.append(rgbt)

rgbtlists.pop(0)

#print(rgbtlists)

def rgbtcombs(m,a,b,c,d):
	mf = math.factorial(m)
	af = math.factorial(a)
	bf = math.factorial(b)
	cf = math.factorial(c)
	df = math.factorial(d)

	combs = int (mf//(af*bf*cf*df))

	return combs

ans = 0
for i in range(len(rgbtlists)):
	ans += rgbtcombs(N,rgbtlists[i][0],rgbtlists[i][1],rgbtlists[i][2],rgbtlists[i][3])%998244353

print(ans)

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))

mem = {}
def ncr(n,r):
    if (n,r) in mem:
        return mem[(n,r)]
    else:
        ret = mul(mul(fac[n], inv(fac[n-r])), inv(fac[r]))
        if len(mem) <= 10**5:
            mem[(n,r)] = ret
        return ret

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:
#!/usr/bin/env python
import math
import fractions

MOD = 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 modinv(a, m):
    inv, _, _ = egcd(a, m)
    return inv % m

cache = [-1] * 300001
def modc(a,b,m):
    if cache[b] > 0:
        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():
    N, A, B, K = map(int, input().split())

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

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

ans = 0
for x in range(N+1):
  rest = K - A*x
  if rest >= 0 and 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 += g1[N] * g2[r] * g2[g] * g2[b] * g2[N-r-g-b] % mod
      #ans += cmb(N,r) * cmb(N-r,g) * cmb(N-r-g, b) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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



N, R, B, K = [int(i) for i in input().split()]
G = R + B

lst = []
for i in range(N + 1):
    if R * i > K:
        break
    for j in range(N + 1 - i):
        if R * i + G * j > K:
            break
        k = (K - R * i - G * j) // B
        if R * i + G * j + B * k == K:
            lst.append((i, j, k))

result = 0
for l in lst:
    result += combinations_count(N, l[0]) * combinations_count(N - l[0], l[1]) * combinations_count(N - l[0] - l[1], l[2])

print(result)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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


ran=min(N,K//(A+B))
ANS=0
#i緑j赤k青
for i in range(ran+1):
    for j in range(min(N-i,(K-(A+B)*i)//A)+1):
        if (K-(A+B)*i-A*j)%B==0:
            k=(K-(A+B)*i-A*j)//B

            if k<=N-i-j:
                ANS=(ANS+Combi(N,i)*Combi(N-i,j)*Combi(N-i-j,k))%998244353
            else:
                break
            #print([i,j,k],Combi(N,i)*Combi(N-i,j)*Combi(N-i-j,k))


print(ANS)

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))

mem = {}
def ncr(n,r):
    if (n,r) in mem:
        return mem[(n,r)]
    else:
        ret = mul(mul(fac[n], inv(fac[n-r])), inv(fac[r]))
        mem[(n,r)] = ret
        return ret

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:
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 and knum//a <= 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:
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

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)
        count=0
        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) %mod

            n_c-=1
            n_b+=1
            n_a+=1

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
L = input().split()
sp = 998244353
# approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

def binom(n,m):
	if n == m:
		return 1
	elif m == 1:
		return n
	elif m > n:
		return 0
	else:
		a = math.factorial(n)
		b = math.factorial(m)
		c = math.factorial(n - m)
		return a // (b*c)

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		sum += (binom(N,i) * binom(N,j)) % sp

print(sum)

Submission status: Time Limit Exceeded

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

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

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

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 += g1[N] * g2[r] * g2[g] * g2[b] * g2[N-r-g-b] % mod

print(ans % mod)

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=[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: 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))

P = 500
pascal = [None] * (P+1)
pascal[0] = [1,0]
for n in range(1,P+1):
    pascal[n] = [1]
    for r in range(1,n+1):
        pascal[n].append(pascal[n-1][r-1] + pascal[n-1][r])
    pascal[n].append(0)

def ncr(n,r):
    if n <= P:
        return pascal[n][r]
    else:
        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:
def fact(N):
    f = 1
    F = 998244353
    for i in range(1,N+1):
        f = (f*i)%F
    return f

if __name__ == '__main__':
    N, A, B, K = map(int, input().split())
    M = 0
    F = 998244353
    for NR in range(0,int(round(K/A))+1):
        for NB in range(0,int(round(K/B))+1):
            if((K-NR*A-NB*B>=0)and((K-NR*A-NB*B)%(A+B)==0)):
                NG = int((K-NR*A-NB*B)/(A+B))
                NX = N-NR-NB-NG
                if(NX>=0):
                    M=(M+fact(N)/(fact(NR)*fact(NG)*fact(NB)*fact(NX)))%F
    print(int(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))

P = 2500
pascal = [None] * (P+1)
pascal[0] = [1,0]
for n in range(1,P+1):
    pascal[n] = [1]
    for r in range(1,n+1):
        pascal[n].append(pascal[n-1][r-1] + pascal[n-1][r])
    pascal[n].append(0)

def ncr(n,r):
    if n <= P:
        return pascal[n][r]
    else:
        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,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
#    fac_inv.append(inv(f))

P = 1000
pascal = [None] * (P+1)
pascal[0] = [1,0]
for n in range(1,P+1):
    pascal[n] = [1]
    for r in range(1,n+1):
        pascal[n].append(pascal[n-1][r-1] + pascal[n-1][r])
    pascal[n].append(0)

def ncr(n,r):
    if n <= P:
        return pascal[n][r]
    else:
        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=[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

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)
        count=0
        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())

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

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

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

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 += cmb(N, r) * cmb(N-r, g) * cmb(N-r-g, b)

print(ans % mod)

Submission status: Time Limit Exceeded

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

# t = time.clock()
n, a, b, k = map(int, input().split())
b, a = 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()
    
# print(len(range(j, min(n, k // a) + 1, b // d)))
# print(time.clock() - t)
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:
import math

N,A,B,K=map(int,input().split())
# x: number of red blocks   (score=A)
# y: number of green blocks (score=A+B)
# z: number of blue blocks  (score=B)

def nCr(n,r):
  if r > n//2:
    r = n - r
  return math.factorial(n) //   \
         math.factorial(n-r) // \
         math.factorial(r)

def calc_pat(N,x,y,z):
  ret=1
  ret*=nCr(N,    x)
  ret*=nCr(N-x,  y)
  ret*=nCr(N-x-y,z)
  return ret

ans=0
y=0
while (A+B)*y <= K:
  x=0
  while A*x+(A+B)*y <= K:
    if (K-(A*x+(A+B)*y))%B == 0:
      z=(K-(A*x+(A+B)*y))//B
      if x + y + z <= N:
        # print('x=' + str(x) + ', y=' + str(y) + ', z=' + str(z))
        ans += calc_pat(N,x,y,z)
    x+=1
    if x + y > N: break
  y+=1
  if y > N: break
print(str(ans%998244353))

Submission status: Time Limit Exceeded

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

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

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

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

ans = 0
for 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 += cmb(N, r) * cmb(N-r, g) * cmb(N-r-g, b) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

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

Solution code:
import math

N,A,B,K = (int(i) for i in input().split())

gscore = A + B
pattern = []
sum = 0

if A < B:
   big = B
   small = A
else:
   big = A
   small = B

for j in range(N + 1):
   if gscore * j > K:
      break
   for k in range(N +1 - j):
      if gscore * j + big * k > K:
         break
      for l in range(N +1 - j - k):
         result = gscore * j + big * k + small * l
         if result > K:
            break
         if result == K:
            no = N - j - k - l
            pattern.append([j,k,l,no])

for m in range(len(pattern)):
   sum += math.factorial(N) / (math.factorial(pattern[m][0]) * math.factorial(pattern[m][1]) * math.factorial(pattern[m][2]) * math.factorial(pattern[m][3]))
   
print(int(sum))