Problem:
 Score : 300 points    Problem Statement Tak has N cards. On the i -th (1 \leq i \leq N) card is written an integer x_i .
He is selecting one or more cards from these N cards, so that the average of the integers written on the selected cards is exactly A .
In how many ways can he make his selection?      Constraints  1 \leq N \leq 50  1 \leq A \leq 50  1 \leq x_i \leq 50  N,\,A,\,x_i are integers.       Partial Score  200 points will be awarded for passing the test set satisfying 1 \leq N \leq 16 .         Input The input is given from Standard Input in the following format:  N  A  x_1  x_2  ...  x_N       Output Print the number of ways to select cards such that the average of the written integers is exactly A .        Sample Input 1 4 8
7 9 8 9      Sample Output 1 5   The following are the 5 ways to select cards such that the average is 8 :  Select the 3 -rd card.  Select the 1 -st and 2 -nd cards.  Select the 1 -st and 4 -th cards.  Select the 1 -st, 2 -nd and 3 -rd cards.  Select the 1 -st, 3 -rd and 4 -th cards.          Sample Input 2 3 8
6 6 9      Sample Output 2 0       Sample Input 3 8 5
3 6 2 8 7 6 5 9      Sample Output 3 19       Sample Input 4 33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3      Sample Output 4 8589934591   The answer may not fit into a 32 -bit integer.

Solution (Python):
import sys
from collections import defaultdict

n, a, *x = map(int, sys.stdin.read().split())

def main():
    for i in range(n):
        x[i] -= a
    
    c = defaultdict(int)
    c[0] = 1
    for i in x:
        nex = c.copy()
        for val, cnt in c.items():
            nex[val+i] += cnt
        c = nex
    ans = c[0] - 1
    return ans

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

Solution (Python):
import sys
from collections import defaultdict

n, a, *x = map(int, sys.stdin.read().split())

def main():
    for i in range(n):
        x[i] -= a
    
    c = defaultdict(int)
    c[0] = 1
    for i in x:
        for val, cnt in tuple(c.items()):
            c[val+i] += cnt
    ans = c[0] - 1
    return ans

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

Solution (Python):
import sys

n, a, *x = map(int, sys.stdin.read().split())

def main():
    for i in range(n):
        x[i] -= a
    x.sort()

    res = [[0] * 99*n for _ in range(n+1)]
    
    res[0][49*n] = 1
    for i in range(n):
        for j in range(99*n):
            res[i+1][j] += res[i][j]
            cur = x[i]
            if cur >= 0:
                if j >= cur:
                    res[i+1][j] += res[i][j-cur]
            else:
                if j - cur <= 99 * n - 1:
                    res[i+1][j] += res[i][j-cur]
    
    ans = res[n][49*n] - 1
    return ans
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys

n, a, *x = map(int, sys.stdin.read().split())

def main():
    ma = a * n
    res = [[[0] * (ma + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    res[0][0][0] = 1
    for i in range(n):
        cur = x[i]
        for j in range(i+2):
            for k in range(ma + 1):
                res[i+1][j][k] += res[i][j][k]
                if k >= cur:
                    res[i+1][j][k] += res[i][j-1][k-cur]
    
    ans = 0
    for j in range(1, n+1):
        ans += res[n][j][j*a]

    return ans

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

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, a = list(map(int, readline().split()))
    x = list(map(int, readline().split()))
    for i in range(n):
        x[i] -= a
    ls = [0] * 5010
    ls[2500] = 1
    for v in x:
        if v == 0:
            for i in range(5010):
                ls[i+v] += ls[i]
        elif v > 0:
            for i in range(5009 - v, -1, -1):
                ls[i+v] += ls[i]
        elif v < 0:
            for i in range(5009 + v):
                ls[i+v] += ls[i]
    print(ls[2500] - 1)


if __name__ == '__main__':
    solve()

Solution (Python):
N, A = map(int, input().split())
x = list(map(int, input().split()))


dp = [[[0] * (A * N + 1) for k in range(N + 1)] for j in range(N)]

dp[0][0][0] = 1
if x[0] <= A * N:
    dp[0][1][x[0]] = 1

for j in range(N - 1):
    for k in range(N + 1):
        for s in range(A * N + 1):
            if k == 0 and s == 0:
                dp[j + 1][k][s] = 1
            elif k > j + 2:
                dp[j + 1][k][s] = 0
            elif s >= x[j + 1] and k >= 1:
                dp[j + 1][k][s] = dp[j][k][s] + dp[j][k - 1][s - x[j + 1]]
            else:
                dp[j + 1][k][s] = dp[j][k][s]

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

print(res)

Solution (Python):
import numpy as np

N, A = map(int,input().split())
X = [int(x) for x in input().split()]
 
dp = np.zeros((N+1,N*A+1),dtype=np.int64)
dp[0,0] = 1
 
for x in X:
    dp[1:,x:] += dp[:-1,:-x].copy()
  
ans = 0
for n in range(1,N+1):
    ans += dp[n,n*A]

print(ans)

Solution (Python):


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

x = list(map(int, input().split()))
 



x = list(map(lambda i: i-a, x))

 


dp = {0: 1}


for i in x:
    
    
    
    
    
    
    for k,v in list(dp.items()):
        dp[i+k]=dp.get(i+k,0)+v
    
    


print(dp[0]-1)

Solution (Python):
N, A = map(int, input().split())
*x, = map(int, input().split())
l = N * A + 1


dp = [[[0] * l for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1
for n in range(0, N + 1):
    for m in range(N):
        for s in range(0, l):
            dp[n][m + 1][s] += dp[n][m][s]
            if s >= x[m]:
                dp[n][m + 1][s] += dp[n - 1][m][s - x[m]]

print(sum([dp[n][N][n * A] for n in range(1, N + 1)]))

Solution (Python):
n,a=map(int,input().split())
x=list(map(int,input().split()))
s=max(sum(x)+1,n*a+1)
dp=[[s*[0]for _ in range(n+1)]for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  for j in range(i+1):
    for k in range(s):
      dp[i][j][k]=dp[i-1][j][k]
      if j!=0 and k>=x[i-1]:dp[i][j][k]+=dp[i-1][j-1][k-x[i-1]]
ans=0
for j in range(1,n+1):ans+=dp[-1][j][j*a]
print(ans)

Solution (Python):
def main():
    N, A = (int(i) for i in input().split())
    X = [int(i) for i in input().split()]
    dp = [[[0 for s in range(N*A + 1)] for k in range(N + 1)]
          for j in range(N + 1)]
    dp[0][0][0] = 1
    for j in range(1, N+1):
        for k in range(0, N+1):
            for s in range(N*A + 1):
                dp[j][k][s] = dp[j-1][k][s]
                if k >= 1 and s - X[j-1] >= 0:
                    dp[j][k][s] += dp[j-1][k-1][s-X[j-1]]
    ans = 0
    for k in range(1, N+1):
        ans += dp[N][k][k*A]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,A = map(int,input().split())
x = list(map(int,input().split()))

temp = x + [A]

X = max(temp)

m = N * X

dp = [[[0 for s in range(m+1)] for k in range(N+1)] for j in range(N+1)]

dp[0][0][0] = 1

res = 0

for j in range(N):
    for k in range(N):
        for s in range(m):
            if dp[j][k][s]:
                dp[j+1][k][s] += dp[j][k][s]
                dp[j+1][k+1][s+x[j]] += dp[j][k][s]

for k in range(1,N+1):
    res += dp[N][k][k*A]

print(res)

Solution (Python):
import sys
n, a  = [int(i) for i in sys.stdin.readline().split()]
x_ls = [int(i) - a for i in sys.stdin.readline().split()]

memo_ls = [[0 for i in range(2 * 50 * 50 + 1)] for j in range(n+1)]
memo_ls[0][50*50] = 1
for i, x in enumerate(x_ls, 1):
    for j in range(2*50*50+1):
        memo_ls[i][j] =  memo_ls[i-1][j]
        if 0 <= j - x <= 2*50*50:
            memo_ls[i][j] += memo_ls[i - 1][j - x]
print(memo_ls[-1][50*50] - 1)

Solution (Python):
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))

d = {0: 1}

for cur in X:
  for k, v in list(d.items()):
    d[cur + k] = d.get(cur + k, 0) + v
    
print(d[0]-1)

Solution (Python):
N, A = map(int, input().split())
X = list(map(int, input().split()))
s = [{} for i in range(N+1)]
s[0][0] = 1

for i in range(N):
  cur = X[i]
  for j in range(N, 0, -1):
    for k, v in s[j-1].items():
      s[j][cur + k] = s[j].get(cur + k, 0) + v

ans = 0
for i in range(1, N+1):
  ans += s[i].get(i*A, 0)
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

L = 50*50
dp = [[0 for _ in range(L+1)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    a = A[i]
    for j in reversed(range(N)):
        for l in range(L+1):
            if l < a: continue
            dp[j+1][l] += dp[j][l-a]

ans = 0
for j in range(N):
    ans += dp[j+1][(j+1)*K]
print(ans)

Solution (Python):
import numpy as np
hi = np.zeros((5000,60),np.int64)
hi[0,0]=1
n,a = map(int, input().split())
li = [int(it) for it in input().split()]
for i in li:
    hi_ = hi.copy()
    hi[i:-1,1:]+=hi_[:-1-i,:-1]
s = 0
for i in range(n):
  s+=hi[(i+1)*a,i+1]
print (s)

Solution (Python):
n, a = map(int, input().split())
X = list(map(int, input().split()))
dp = [ [[0]*(n*a+1) for j in range(i+1)] for i in range(n+1) ]
for i in range(n+1):
  dp[i][0][0] = 1
for i in range(n):
  for j in range(i+1):
    for k in range(n*a+1):
      if X[i] > k:
        if i > j:
          dp[i+1][j+1][k] = dp[i][j+1][k]
      else:
        if i > j:
          dp[i+1][j+1][k] = dp[i][j+1][k] + dp[i][j][k-X[i]]
        else:
          dp[i+1][j+1][k] = dp[i][j][k-X[i]]
ans = 0
for i in range(1, n+1):
  ans += dp[n][i][a*i]
print(ans)

Solution (Python):
n,a=map(int,input().split())
X=list(map(int,input().split()))

def card(n,a):
	dp=[[[0]*(n*a+1) for i in range(n+1)] for j in range(n+1)]
	dp[0][0][0]=1
	
	for i in range(n):
		for j in range(n):
			for k in range(n*a+1):
				if k<X[i]:
					dp[i+1][j][k]=dp[i][j][k]
				else:
					dp[i+1][j+1][k]=dp[i][j+1][k]+dp[i][j][k-X[i]]
	
	r=0
	for i in range(1,n+1):
		r+=dp[n][i][i*a]
		
	return r
		
print(card(n,a))

Solution (Python):
n, a = map(int, input().split())
x = list(map(int, input().split()))


x = list(map(lambda i: i-a, x))



dp = {0: 1}


for num in x:
  
  for k,v in list(dp.items()):
    dp[num+k]=dp.get(num+k,0)+v
    
  

print(dp[0]-1)

Solution (Python):
N,A = map(int, input().split())
X = [int(x) for x in input().split()]

M = sum(X)
dp = [[[0]*(N+1) for _ in range(M+1)] for _ in range(N+1)]
    
for i in range(N+1):
    dp[i][0][0] = 1
    
for i in range(N):
    for j in range(M+1):
        for k in range(1, N+1):
            if j >= X[i]:
                dp[i+1][j][k] = dp[i][j][k] + dp[i][j-X[i]][k-1]
            else:
                dp[i+1][j][k] = dp[i][j][k]
        
ans = 0
for k in range(1, N+1):
    if k*A <= M:
        ans += dp[N][k*A][k]
            
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,a=map(int,input().split())
    X=list(map(int,input().split()))
    M=sum(X)
    dp=[[0]*(M+1) for _ in range(n+1)]
    dp[0][0]=1

    from itertools import product
    for x in X:
        ndp=[y[:] for y in dp]
        for i,m in product(range(n),range(M+1)):
            if(m+x<=M):
                ndp[i+1][m+x]+=dp[i][m]
        dp=ndp

    ans=0
    for i in range(1,n+1):
        if(i*a<=M):
            ans+=dp[i][i*a]
    print(ans)
resolve()

Solution (Python):
n, a = map(int, input().split())
x = list(map(int, input().split()))


max_num = max(max(x), a)
dp = [[[0 for _ in range(max_num * n + 1)]
       for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for j in range(1, n+1):
    for k in range(j+1):
        for s in range(max_num * k + 1):
            if s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif k >= 1 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]

ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]
print(ans)

Solution (Python):
def main():
    n,a = map(int,input().split())
    x = [int(x) for x in input().split()]
    dp= [[[0 for _ in range(2501)] for _ in range(n+1)] for _ in range(n)]

    dp[0][0][0] = 1
    dp[0][1][x[0]] = 1

    for i in range(1,n):
        for j in range(n+1):
            for k in range(2501):
                if k<x[i]:
                    dp[i][j][k] = dp[i-1][j][k]
                else:
                    dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-x[i]]
    ans = 0
    for i in range(1,n+1):
        ans += dp[-1][i][a*i]
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
 
n, k = map(int, input().split())
x = [int(i) for i in input().split()]
x = [i-k for i in x]
dic = defaultdict(int)

dic[0]=1
for i in x:
    for k,v in list(dic.items()):
        dic[k+i]+=v
print(dic[0]-1)

Solution (Python):

import sys, math, itertools, heapq, collections, bisect, fractions
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = count = 0

def counting(A):
    memo=[0]*2501
    memo[0]=1
    n=len(A)
    for ai in A:
        for i in range(2500,0,-1):
            if i-ai<0:continue
            memo[i]+=memo[i-ai]
    return memo


    

n,X=map(int,input().split())
A,B=[],[]
lis=list(map(int,input().split()))
for li in lis:
    li-=X
    if li<0:
        B.append(-li)
    elif li==0:
        count+=1
    else:
        A.append(li)
count=2**count
A.sort();B.sort()
A=counting(A)
B=counting(B)
for i in range(1,len(A)):
    ans+=A[i]*B[i]*count
ans+=count-1

print(ans)

Solution (Python):
n,a=map(int,input().split())
x=list(map(int,input().split()))

for i in range(n):
    x[i]-=a
    
dp=[0]*(2*n*50+2)
dp[0]=1
for i in range(n):
    h=dp[:]
    for j in range(-(n-1)*50,(n-1)*50+1):
        h[j]+=dp[j-x[i]]
    dp=h
print(dp[0]-1)

Solution (Python):
n,a = map(int,input().split())
x = [int(i) for i in input().split()]

sum_x = sum(x)

dp = [[[0 for i in range(n+1)]for j in range(sum_x+1)]for k in range(n+1)]

dp[0][0][0] = 1

for i in range(n):
    for j in range(n):
        for k in range(sum_x+1):
            dp[i+1][k][j] += dp[i][k][j]
            if k + x[i] > sum_x:
                continue
            dp[i+1][k+x[i]][j+1] += dp[i][k][j]
            
ans = 0

for i in range(n):
    if a*(i+1) > sum_x:
        break
    ans += dp[n][a*(i+1)][i+1]

print(ans)

Solution (Python):
n, a = map(int, input().split())
x = list(map(int, input().split()))
x = list(map(lambda i: i-a, x))
dp = {0: 1}

for i in x:
  for k,v in list(dp.items()):
    dp[i+k]=dp.get(i+k,0)+v
print(dp[0]-1)

Solution (Python):
from collections import Counter

N, A = map(int, input().split())
X = list(map(int, input().split()))

X2 = [0]*N

for i in range(N):
    X2[i] = X[i] - A

C = Counter([0, X2[0]])

for x in X2[1:]:
    C2 = Counter()
    for s, c in C.items():
        C2[s+x] += c
    C += C2

print(C[0]-1)

Solution (Python):
n,a=map(int,input().split())
lists=list(map(int,input().split()))

for i in range(n):
    lists[i]-=a
answer=0
dp=[[0 for i in range(5001)] for _ in range(51)]



for i in range(n+1):
    for j in range(4951):
        if i>=1 and j>=lists[i-1]:
            dp[i][j]=dp[i-1][j-lists[i-1]]+dp[i-1][j]
        if i>=1 and j<lists[i-1]:
            dp[i][j]=dp[i-1][j]
        else:
            if j==2500 and i==0:
                dp[i][j]=1
            elif j!=2500 and i==0:
                dp[i][j]=0
print(dp[n][2500]-1)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

offset = 3000

n, a = [int(item) for item in input().split()]
x = [int(item) - a for item in input().split()]

dp = [0] * 6000
dp[0 + offset] = 1

for item in x:
    if item < 0:
        for i in range(6000):
            if dp[i] == 0:
                continue 
            dp[i + item] += dp[i]
    else:
        for i in range(6000 - 1, -1, -1):
            if dp[i] == 0:
                continue 
            dp[i + item] += dp[i]
print(dp[offset] - 1)

Solution (Python):
N, A = map(int,input().split())
X = list(map(int,input().split()))
dp = [[[0 for i in range(N*50+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 1
for i in range(1,N+1):
    x = X[i-1]
    for j in range(1,N+1):
        for k in range(N*50+1):
            if k < x:
                dp[i][j][k] = dp[i-1][j][k]
                
            elif j > i:
                dp[i][j][k] = 0
                
            else: 
                dp[i][j][k] += dp[i-1][j][k] + dp[i-1][j-1][k-x]
ans = 0
for i in range(1,N+1):
    ans += dp[N][i][A*i]
print(ans)

Solution (Python):
def examC():
    N, A = LI()
    x = LI()
    maxNX = max(x)*N
    dp = [[[0]*(maxNX+1) for _ in range(N+1)]for _ in range(N+1)]
    dp[0][0][0] = 1
    for i in range(1,N+1):
        cur = x[i-1]
        for l in range(N+1):
            for j in range(maxNX + 1):
                dp[l][i][j] += dp[l][i - 1][j]
        for l in range(1,N + 1):
            for j in range(cur, maxNX + 1):
                dp[l][i][j] += dp[l-1][i - 1][j - cur]

    ans = int(0)
    for i in range(1,min(maxNX//A+1,N+1)):
        ans += dp[i][N][i*A]
    print(ans)


import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

Solution (Python):

import sys
input = sys.stdin.readline


N,A = map(int,input().split())
X = [0] + list(map(int,input().split()))


dp = [[[0 for _ in range(50*N+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for n in range(N+1):
    for k in range(n+1):
        for d in range(50*k+1):
            
            if d < X[n]:
                dp[n][k][d] = dp[n-1][k][d]
            
            else:
                
                if k >= 1:
                    dp[n][k][d] = dp[n-1][k][d] + dp[n-1][k-1][d-X[n]]

ans = 0
for i in range(1,N+1):
    
    ans += dp[N][i][A*i]

print(ans)

Solution (Python):
N, A = map(int, input().split())
x = list(map(int, input().split()))

max_of_a = N * A


dp = [[[0] * (max_of_a + 1) for _ in range(N+1)]for _ in range(N+1)]
dp[0][0][0] = 1


for i in range(N+1):
    for j in range(N+1):
        for k in range(max_of_a + 1):
            if i >= 1 and x[i-1] > k:
                dp[i][j][k] = dp[i-1][j][k]
            elif i >= 1 and j >= 1 and x[i-1] <= k:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k - x[i-1]]

ans = 0
for j in range(1, N+1):
    
    ans += dp[N][j][j*A]
print(ans)

Solution (Python):
N,A = map(int,input().split())
x = list(map(int,input().split()))
X = sum(x)

dp = [[[0 for k in range(X+1)] for j in range(N+1)] for i in range(N)]

for i in range(N):
    for j in range(i+1):
        dp[i][1][x[j]] += 1

for i in range(N-1):
    for j in range(1,i+2):
        for k in range(X+1):
            if 1 <= k-x[i+1] <= X:
                dp[i+1][j+1][k] = dp[i][j+1][k] + dp[i][j][k-x[i+1]]
            else:
                dp[i+1][j+1][k] = dp[i][j+1][k]

ans = 0
for j in range(1,N+1):
    if 1 <= A*j <= X:
        ans += dp[N-1][j][A*j]

print(ans)

Solution (Python):
def main():
    N, A, *x = map(int, open(0).read().split())
    MAX_A_x = max(A, max(x))
    x = [xi - A for xi in x]
    
    
    
    dp = [[0] * (2 * N * MAX_A_x + 1) for i in range(N + 1)]
    dp[0][N * MAX_A_x] = 1
    for i in range(1, N + 1):
        for j in range(2 * N * MAX_A_x + 1):
            if j - x[i - 1] < 0 or 2 * N * MAX_A_x < j - x[i - 1]:
                dp[i][j] = dp[i - 1][j]
            elif 0 <= j - x[i - 1] <= 2 * N * MAX_A_x:
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - x[i - 1]]
            else:
                dp[i][j] = 0
    print(dp[N][N * MAX_A_x] - 1)
    return


main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()

A = [a-K for a in LIST()]

MAX = N * K * 2

dp = list2d(N+1, MAX+1, 0)

dp[0][N*K] = 1
for i in range(N):
    a = A[i]
    for k in range(MAX+1):
        dp[i+1][k] += dp[i][k]
        if 0 <= k+a <= MAX:
            dp[i+1][k+a] += dp[i][k]

print(dp[N][N*K]-1)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

MAX = N * K

dp = list3d(N+1, N+1, MAX+1, 0)
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(i+1):
        for k in range(MAX+1):
            dp[i+1][j][k] += dp[i][j][k]
            if j+1 <= N and k+a <= MAX:
                dp[i+1][j+1][k+a] += dp[i][j][k]
ans = 0
for j in range(1, N+1):
    
    ans += dp[N][j][j*K]
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

total = sum(A)

dp = list3d(N+1, N+1, total+1, 0)
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(N+1):
        for k in range(total+1):
            dp[i+1][j][k] += dp[i][j][k]
            if j+1 <= N and k+a <= total:
                dp[i+1][j+1][k+a] += dp[i][j][k]
ans = 0
for j in range(1, N+1):
    if j*K <= total:
        
        ans += dp[N][j][j*K]
print(ans)

Solution (Python):
def solve():
    def recur(i, n, total):
        

        if not TABLE[i][n][total] == -1:
            return TABLE[i][n][total]

        if not i < N:
            if n > 0 and total == A * n:
                TABLE[i][n][total] = 1
                return TABLE[i][n][total]

            TABLE[i][n][total] = 0
            return TABLE[i][n][total]

        ans1 = recur(i + 1, n, total)
        ans2 = recur(i + 1, n + 1, total + XS[i])

        

        TABLE[i][n][total] = ans1 + ans2
        return TABLE[i][n][total]

    N, A = tuple(map(int, input().split()))
    XS = tuple(map(int, input().split()))

    TABLE = []
    for _ in range(N + 1):
        lines = [[-1 for x in range(N * 50 + 1)] for y in range(N + 1)]
        TABLE.append(lines)

    return recur(0, 0, 0)


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

Solution (Python):
def solve():
    def recur(i, n, total):
        

        if not TABLE[i][n][total] == -1:
            
            return TABLE[i][n][total]

        if not i < N:
            if n > 0 and total == A * n:
                return 1
            return 0

        ans1 = recur(i + 1, n, total)
        ans2 = recur(i + 1, n + 1, total + XS[i])

        

        TABLE[i][n][total] = ans1 + ans2
        return TABLE[i][n][total]

    N, A = tuple(map(int, input().split()))
    XS = tuple(map(int, input().split()))

    TABLE = []
    for _ in range(N + 1):
        lines = [[-1 for x in range(N * 50 + 1)] for y in range(N + 1)]
        TABLE.append(lines)

    return recur(0, 0, 0)


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

Solution (Python):
def solve():
    def recur(i, n, total):
        

        if not TABLE[i][n][total] == -1:
            
            return TABLE[i][n][total]

        if not i < N:
            if n > 0 and total == A * n:
                return 1
            return 0

        ans1 = recur(i + 1, n, total)
        ans2 = recur(i + 1, n + 1, total + XS[i])

        

        TABLE[i][n][total] = ans1 + ans2
        return TABLE[i][n][total]

    N, A = tuple(map(int, input().split()))
    XS = tuple(map(int, input().split()))

    TABLE = []
    for _ in range(N + 1):
        lines = [[-1 for x in range(N * 50 + 1)] for y in range(N + 1)]
        TABLE.append(lines)

    return recur(0, 0, 0)


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

Solution (Python):

import sys


def solve(N: int, A: int, x: "List[int]"):
    x = [x[i]-A for i in range(N)]
    dp = [[0]*2500 for _ in range(N+1)]
    dp[0][1250] = 1

    for j in range(1,N+1):
        for t in range(2500):
            if t-x[j-1]>=0 and t-x[j-1]<2500:
                dp[j][t] = dp[j-1][t] + dp[j-1][t-x[j-1]]
            else:
                dp[j][t] = dp[j-1][t]
    print(dp[N][1250]-1)
    
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = int(next(tokens))  
    x = [int(next(tokens)) for _ in range(N)]  
    solve(N, A, x)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np


def main(n, a, x):
    X = max(a, max(x))
    NX = X * n
    NX2 = 2 * NX
    dp = np.zeros(shape=(n + 1, NX2 + 1), dtype=int)
    dp[0][NX] = 1
    for j in range(1, len(dp)):
        for t in range(len(dp[j])):
            xj = x[j - 1]
            yj = xj - a
            if 0 <= t - yj <= NX2:
                dp[j][t] = dp[j - 1][t] + dp[j - 1][t - yj]
            else:
                dp[j][t] = dp[j - 1][t]
    return dp[n][NX] - 1


if __name__ == '__main__':
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
    print(main(N, A, X))

Solution (Python):
import numpy as np


def main(n, a, x):
    SUM_MAX = max(a, max(x)) * n + 1
    dp = np.zeros(shape=(n + 1, n + 1, SUM_MAX), dtype=int)

    dp[0][0][0] = 1
    for j in range(1, n + 1):
        for k in range(j + 1):
            dp[j][k][0:x[j - 1]] = dp[j - 1][k][0:x[j - 1]]
            if k >= 1:
                dp[j][k][x[j - 1]:] = dp[j - 1][k][x[j - 1]:] + dp[j - 1][k - 1][:SUM_MAX - x[j - 1]]

    patterns = 0
    for k in range(1, n + 1):
        ka = k * a
        patterns += dp[n][k][ka]
    return patterns


if __name__ == '__main__':
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
    print(main(N, A, X))

Solution (Python):
n,a = list(map(int,input().split()))
x = list(map(int,input().split()))

def Count(n,k,a):
	s = sum(x)
	dp=[[[0 for l in range(s+1)] for j in range(k+1)] for i in range(n+1)]
	dp[0][0][0]=1
	Sum=0
	for i in range(n):
		for j in range(k+1):
			for l in range(s+1):
				if l < x[i]:
					dp[i+1][j][l] = dp[i][j][l]
				if j >=1 and l >= x[i]:
					dp[i+1][j][l] = dp[i][j][l] + dp[i][j-1][l-x[i]]
				if j <= i+1 and l ==j*a and j >= 1:
					if dp[i+1][j][l]>=1:	
						Sum += dp[i+1][j][l]-dp[i][j][l]
	return Sum

print(Count(n,n,a))

Solution (Python):
def main():
    n, a = map(int, input().split())
    x = list(map(int, input().split()))

    mx = max(x + [a])

    for i in range(n):
        x[i] -= a

    sm = 2 * n * mx

    dp = [[0] * (sm + 1) for _ in range(n + 1)]

    dp[0][n*mx] = 1

    for i, e in enumerate(x, 1):
        for j in range(sm + 1):
            if 0 <= j - e <= sm:
                dp[i][j] = dp[i-1][j] + dp[i-1][j-e]
            else:
                dp[i][j] = dp[i-1][j]

    ans = dp[n][n*mx] - 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline


def main():
    n, a = map(int, input().split())
    x = tuple(map(int, input().split()))

    sm_mx = sum(x)

    dp = [[[0] * (sm_mx + 1) for _ in range(n + 1)] for _ in range(n + 1)]

    dp[0][0][0] = 1

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sum(x[:i]) + 1):
                if sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]

    ans = 0
    for i in range(1, n + 1):
        if i > sm_mx / a:
            break
        ans += dp[n][i][i*a]

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


import numpy as np

N, A = map(int, input().split())
x = np.array(list(map(int, input().split())))

x_diff = x - np.array(A)
X = max(A, max(x))

dp = np.zeros((N+2, 2*N*X+2)) 
dp = dp.tolist()
dp[0][N*X] = 1

for i in range(N):
    for j in range(2*N*X+1):
        if j < x_diff[i] or x_diff[i] < j - 2*N*X: 
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = dp[i][j] + dp[i][j-x_diff[i]]
            
print(int(dp[N][N*X] - 1))

Solution (Python):



import math

N, A = map(int, input().split())
x = list(map(int, input().split()))


def partial_sum(a,A):
    n = len(a)
    dp = [[0]*(A+2) for _ in range(n+2)] 
    dp[0][0] = 1
    
    for i in range(n):
        for j in range(A+1):
            if j >= a[i]:
                dp[i+1][j] = dp[i][j-a[i]] + dp[i][j]
            else:
                dp[i+1][j] = dp[i][j]
                
    return dp[n][A]

x_diff = [a - A for a in x] 
x_diff_negative = [-a for a in x_diff if a < 0]
x_diff_positive = [a for a in x_diff if a > 0]

ans = 0
for i in range(1, min(sum(x_diff_negative), sum(x_diff_positive)) + 1):
    ans += partial_sum(x_diff_negative,i) * partial_sum(x_diff_positive,i) 


n_pattern_0 = 0
n_0 = x_diff.count(0)
if n_0 > 0:
    for i in range(1, n_0+1):
        n_pattern_0 += math.factorial(n_0) // (math.factorial(n_0-i) * math.factorial(i))



ans += (ans+1) * n_pattern_0
    
print(ans)

Solution (Python):

n,k = map(int,input().split())
A = list(map(int,input().split()))
dic1 = {(0,0):1}
for i in range(n):
    dic2 = {(0,0):0}
    for (total,num),amount in dic1.items():
        if (total,num) in dic2:
            dic2[(total,num)] += amount
        else:
            dic2[(total,num)] = amount
        if (total+A[i],num+1) in dic2:
            dic2[(total+A[i],num+1)] += amount
        else:
            dic2[(total+A[i],num+1)] = amount
    
    dic1 = dic2

ans = 0
for i in range(1,n+1):
    if (i*k,i) in dic1:
        ans += dic1[(i*k,i)]

print(ans)

Solution (Python):
n,x=map(int,input().split())
l=[int(i) for i in input().split()]
dp = [[[0 for k in range(55)] for j in range(3000)] for i in range(55)]

for i in range(n+1):
    dp[i][0][0]=1 
sm=sum(l)
for i in range(1,n+1):
    for j in range(sm+5):
        for k in range(1,n+1):
            curr=l[i-1]
            if curr<=j:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-curr][k-1]
            else:
                dp[i][j][k]=dp[i-1][j][k]

ans=0 
for k in range(1,n+1):
    ans+=dp[n][k*x][k]
print(ans)

Solution (Python):
n, a = map(int, input().split())
x = list(map(lambda x: int(x) - a, input().split()))
d = {0: 1}
for i in x:
    for j, k in list(d.items()):
        d[i + j] = d.get(i + j, 0) + k
ans = d[0] - 1
print(ans)