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.



Sample input:
4 8
7 9 8 9


Sample output:
5

Submission status: Runtime Error

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, A = nl()
X = nl()

dp = []
for i in range(N+1):
    r = []
    for j in range(N+1):
        r.append([0 for k in range(N*max(X)+1)])
    dp.append(r)

dp[0][0][0] = 1
for i in range(1, N+1):
    for j in range(0, N+1):
        for k in range(N*max(X)+1):
            if k < X[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            elif j > 0 and k >= X[i-1]:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

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

Submission status: Runtime Error

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, A = nl()
X = nl()

dp = []
for i in range(N+1):
    r = []
    for j in range(N+1):
        r.append([0 for k in range(N*max(X)+1)])
    dp.append(r)

dp[0][0][0] = 1
for i in range(1, N+1):
    for j in range(0, N+1):
        for k in range(N*max(X)+1):
            if k < X[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            elif j > 0:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

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

Submission status: Runtime Error

Solution code:
import numpy as np
N, A = map(int, input().split())
x = list(map(int, input().split()))

X = max(x)
if X < A:
    X = A

def check(j, k, s):
    if dp[j][k][s] != -1:
        return dp[j][k][s]
    if j == 0 and k == 0 and s == 0:
        dp[j][k][s] = 1
        return 1
    if j >= 1 and s < x[j-1]:
        a = check(j-1, k ,s)
        dp[j][k][s] = a
        return a
    if j >= 1 and k >= 1 and s >= x[j-1]:
        a = check(j-1, k, s) + check(j-1, k-1, s-x[j-1])
        dp[j][k][s] = a
        return a
    dp[j][k][s] = 0
    return 0
        
dp = [[[-1] * (N*X+1) for _ in range(N+1)] for _ in range(N + 1)]
# dp = np.array(dp)
# print (dp)
# for j in range(N+1):
#     for k in range(N+1):
#         for s in range(N*X + 1):
#             print (j, k, s)
#             dp[j][k][s] = check(j, k, s)

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

print (ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N, A = map(int, input().split())
x = list(map(int, input().split()))

X = max(x)
if X < A:
    X = A

def check(j, k, s):
    if dp[j][k][s] != -1:
        return dp[j][k][s]
    if j == 0 and k == 0 and s == 0:
        dp[j][k][s] = 1
        return 1
    if j >= 1 and s < x[j-1]:
        a = check(j-1, k ,s)
        dp[j][k][s] = a
        return a
    if j >= 1 and k >= 1 and s >= x[j-1]:
        a = check(j-1, k, s) + check(j-1, k-1, s-x[j-1])
        dp[j][k][s] = a
        return a
    dp[j][k][s] = 0
    return 0
        
dp = [[[-1] * (10 * N+1) for _ in range(10 * N+1)] for _ in range(10 * N*X + 1)]
dp = np.array(dp)
# print (dp)
# for j in range(N+1):
#     for k in range(N+1):
#         for s in range(N*X + 1):
#             print (j, k, s)
#             dp[j][k][s] = check(j, k, s)

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

print (ans)

Submission status: Runtime Error

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
for i in range(N):
    X[i] -= A

dp = defaultdict(int)
dp[0] = 1

for x in X:
    
    for j, c in list(dp.items()):
        dp[j + x] += c

print(dp[0]-1)

Submission status: Runtime Error

Solution code:

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

dp = [[[0 for i in range(2800)]for j in range(50)]for k in range(50)]

# dp[i][j][k] → i枚のうちj枚を選んで 和が kになる組み合わせ
dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for k in range(2501):
            if dp[i][j][k] != 0:
                dp[i+1][j][k] += dp[i][j][k]    #i枚目を選ばなかった世界線
                dp[i + 1][j + 1][k + nums[i]]  += dp[i][j][k]          #i枚目を選んだ世界線


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

Submission status: Runtime Error

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
dp = [[[0 for s in range(n * 50)] for k in range(n + 1)] for j in range(n + 1)]
for j in range(n + 1):
    for k in range(n + 1):
        for s in range(n * 50):
            if (j == 0) and (k == 0) and (s == 0):
                dp[j][k][s] = 1
            elif (j > 0) and (s < x[j - 1]):
                dp[j][k][s] = dp[j - 1][k][s]
            elif (j > 0) and (k > 0) 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[j][k][k * a]
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import product
N, A = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)

dp = [[[0 for s in range(x_max * (N + 1))] for n in range(N + 1)] for i in range(N + 1)]
dp[0][0][0] = 1

for i, n, s in product(range(1, N + 1), range(N + 1), range(x_max * (N + 1))):
    if s < x[i - 1]:
        dp[i][n][s] = dp[i - 1][n][s]
    elif 0 < n and x[i - 1] <= s:
        dp[i][n][s] = dp[i - 1][n][s] + dp[i - 1][n - 1][s - x[i - 1]]

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

Submission status: Runtime Error

Solution code:
from itertools import product
N, A = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)

dp = [[[0 for s in range(x_max * N + 1)] for n in range(N + 1)] for i in range(N + 1)]
dp[0][0][0] = 1

for i, n, s in product(range(1, N + 1), range(N + 1), range(x_max * N + 1)):
    if s < x[i - 1]:
        dp[i][n][s] = dp[i - 1][n][s]
    elif 0 < n and x[i - 1] <= s:
        dp[i][n][s] = dp[i - 1][n][s] + dp[i - 1][n - 1][s - x[i - 1]]

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

Submission status: Runtime Error

Solution code:
n, a = map(int, input().split())
xs = list(map(int, input().split()))

dp = [[0]*2501] * 51
for x in xs:
  dp[1][x] = 1
for i in range(2,n+1):
  for j in range(1,2501):
    for x in xs[i-1:]
      dp[i][j] = dp[i-1][j-x]

ans = 0
for ys in dp:
  ans += ys[n*a]
  
print(ans)

Submission status: Runtime Error

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)
x_sum = sum(x)
if x_max < a:
    print(0)
else:
    dp = [[[0 for k in range(x_sum + 1)] for j in range(n + 1)] for i in range(n + 1)]
    dp[0][0][0] = 1
    for i in range(1, n + 1):
        for j in range(n + 1):
            for k in range(x[i - 1]):
                dp[i][j][k] = dp[i - 1][j][k]
            if j > 0:
                for k in range(x[i - 1], x_sum + 1):
                    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[-1][j][j * a]
    print(ans)

Submission status: Runtime Error

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)
dp = [[[0 for k in range(n * x_max + 1)] for j in range(n + 1)] for i in range(n + 1)]
dp[0][0][0] = 1
for i in range(1, n + 1):
    for j in range(n + 1):
        for k in range(x[i - 1]):
            dp[i][j][k] = dp[i - 1][j][k]
        if j > 0:
            for k in range(x[i - 1], n * x_max + 1):
                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[-1][j][j * a]
print(ans)

Submission status: Runtime Error

Solution code:
def main():
  n,a,*x=map(int,open(0).read().split())
  x=[0]+x
  dp=[[[0]*(50*n+1)for j in range(n+1)]for i in range(n+1)]
  dp[0][0][0]=1
  for i in range(1,n+1):
    dp[i][0]=dp[i-1][0]
    for j in range(1,n+1):
      for k in range(1,50*n+1):
        dp[i][j][k]=dp[i-1][j][k]
        if k-x[i]>=0:
          dp[i][j][k]+=dp[i-1][j-1][k-x[i]]
  ans=0
  for i in range(1,n+1):
    j=i*a
    if j<50*n+2:
      ans+=dp[-1][i][j]
  print(ans)
def __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
n,a=map(int,input().split())
arr=list(map(int,input().split()))
l=sum(arr)
dp=[[[0]*(l+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  xi=arr[i-1]
  for j in range(0,i+1):
    for k in range(0,l+1):
      if k<xi:
        dp[i][j][k]=dp[i-1][j][k]
      elif j>=1:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-xi]
ans=0
for i in range(1,n+1):
  ans+=dp[n][i][i*a]
print(ans)

Submission status: Runtime Error

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

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

tmp_max = max(x)
tmp_max = max(tmp_max, A)

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

for j in range(N + 1):
  for k in range(j + 1):
    for s in range(tmp_max * k + 1):
      if j >= 1 and s < x[j - 1]:
        dp[j][k][s] = dp[j - 1][k][s]
      elif j >= 1 and 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)

Submission status: Runtime Error

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

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

tmp_max = max(x)
tmp_max = max(tmp_max, A)

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

for j in range(N + 1):
  for k in range(j + 1):
    for s in range(tmp_max * K + 1):
      if j >= 1 and s < x[j - 1]:
        dp[j][k][s] = dp[j - 1][k][s]
      elif j >= 1 and 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)

Submission status: Runtime Error

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

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

tmp_max = max(x)
tmp_max = max(tmp_max, A)

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

for j in range(n + 1):
  for k in range(j + 1):
    for s in range(tmp_max * K + 1):
      if j >= 1 and s < x[j - 1]:
        dp[j][k][s] = dp[j - 1][k][s]
      elif j >= 1 and 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)

Submission status: Runtime Error

Solution code:

import numpy as np

def read_input():
    n, a = map(int, input().split())
    xlist = list(map(int, input().split()))
    return n, a, xlist


def submit():
    n, a, xlist = read_input()

    if a > max(xlist):
        print(0)

    dp = np.zeros((n + 1, n + 1, (n + 1) * max(xlist)))

#   dp[j][k][s] : j枚目までのカードでk枚選び、合計sにする方法の数
#         (1) dp[0][0][0] : 1枚も選ばずに合計0にする方法は1種類
#               j = k = s = 0のとき
#         (2) dp[j][k][s] = dp[j - 1][k][s] if xj > s : j枚目のカードがsより大きいとき、sを作りようがないのでj-1枚目までの手法と一緒
#               j > 0, xj > sのとき
#         (3) dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - xj]
#               : xj <= sのとき、j-1枚目まででsを作る方法と、j-1枚目まででs-xjをつくり、j枚目を選んでk枚にする
#               j > 0, k > 0, s >= xjのとき
#         (4) dp上記以外は無理なので0

    for j in range(n + 1):
        for k in range(n + 1):
            for s in range((n + 1) * max(xlist)):
                if j == k == s == 0:
                    dp[j][k][s] = 1
                elif j > 0 and xlist[j - 1] > s:
                    dp[j][k][s] = dp[j - 1][k][s]
                elif j > 0 and k > 0 and xlist[j - 1] <= s:
                    dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - xlist[j - 1]]
                else:
                    dp[j][k][s] = 0

    methods = 0
    for i in range(1, n + 1):
        methods += dp[n][i][i * a]

    print(int(methods))


if __name__ == '__main__':
    submit()

Submission status: Runtime Error

Solution code:
def solve():
  n,a = (int(i) for i in input().split())
  x = list(int(i) for i in input().split())
  tp = max(x)
  dp = [[[0 for i in range(n*tp +1)] for j in range(n+1)] for k in range(n+1)]
  query = a*n
  dp[0][0][0] = 1
  for i in range(1,n+1):
    for j in range(n+1):
      for k in range(n*tp +1):
        #選ばない
        dp[i][j][k] = dp[i-1][j][k]
        if x[i-1] <= k and j > 0:
         dp[i][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(dp)
  print(ans)
  
  
  
  
  
  
solve()

Submission status: Runtime Error

Solution code:
import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    s = int(input())

    return ans


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

Submission status: Runtime Error

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
X=sum(x)
dp=[[[0]*(X+1)for j in range(n+1)]for i in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  xi=x[i-1]
  for j in range(n+1):
      for h in range(X+1):
        if h<xi:dp[i][j][h]=dp[i-1][j][h]
        if xi<=h and j>=1:dp[i][j][h]=dp[i-1][j][h]+dp[i-1][j-1][h-xi]
ans=0
for j in range(1,n+1):ans+=dp[n][j][j*a]
print(ans)

Submission status: Runtime Error

Solution code:
#x枚目まででy枚選んで合計がzになる場合の数dp[x][y][z]
N,A=map(int,input().split())
x=[int(i) for i in input().split()]
dp=[[[0]*(A*N+1) for i in range(N+1)]for k in range(N+2)]
ans=0
dp[0][0][0]=1
for made,i in enumerate(dp):
    if made>N:break
    for maisu,j in enumerate(i):
        for wa,k in enumerate(j):
            if k and made<=N:#made枚目までにmaisu枚選んでwaになる場合の数
                dp[made+1][maisu][wa]+=k
                newwa=wa+x[made-1]
                if newwa<=A*N:
                    dp[made+1][maisu+1][newwa]+=k
for mai in range(1,N+1):
    a=dp[N][mai][mai*A]
    if a:
        ans+=a
print(ans)

Submission status: Runtime Error

Solution code:
#x枚目まででy枚選んで合計がzになる場合の数dp[x][y][z]
N,A=map(int,input().split())
x=[int(i) for i in input().split()]
dp=[[[0]*(A*50) for i in range(N+2)]for k in range(N+2)]
ans=0
dp[0][0][0]=1
for made,i in enumerate(dp):
    if made>N:break
    for maisu,j in enumerate(i):
        for wa,k in enumerate(j):
            if k:#made枚目までにmaisu枚選んでwaになる場合の数
                dp[made+1][maisu][wa]+=k
                dp[made+1][maisu+1][wa+x[made-1]]+=k
for mai in range(1,N+1):
    a=dp[N][mai][mai*A]
    if a:
        ans+=a
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N,A=map(lambda x:int(x),input().split())

x=[int(i) for i in input().split()]
dp=np.zeros((N+1,N+1,sum(x)+1))

def solve(j,k,s):
  if k==0 and j==0 and s==0:
    return 1
  elif j>=1 and s<x[j-1] :
    dp[j,k,s]=solve(j-1,k,s)
    return dp[j,k,s]
  elif j>=1 and k>=1 and s>=x[j-1]:
    dp[j,k,s]=solve(j-1,k,s)+solve(j-1,k-1,s-x[j-1]) 
    return dp[j,k,s]
  else:
    return 0

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

Submission status: Runtime Error

Solution code:
n,a=map(int,input().split())
x=list(map(int,input()))
stack=[0]*5001
stack[2500-a]=1
ans=0
for i in x:
  i-=a
for i in x:
  ans+=stack[2500-i+a]
  stack2=[i for i in stack]
  for j in range(5001):
    if 0<=j+i<=5000:
      stack2[j+i]+=stack[j]
  stack=[i for i in stack2]
print(stack[2500])

Submission status: Runtime Error

Solution code:
from sys import stdin
input = stdin.readline

N, A = [int(x) for x in input().rstrip().split()]
x = [int(x) for x in input().rstrip().split()]

X = max(max(x), A)
# dp = [[[0]*(N*X+1) for _ in range(N+1)] for _ in range(N+1)]
# for j in range(N+1):
# 	for k in range(N+1):
# 		for s in range(N*X+1):
# 			if j == 0 and k == 0 and s == 0:
# 				dp[j][k][s] = 1
# 			elif j >= 1 and s < x[j-1]: # 探索先が総和より大きい
# 				dp[j][k][s] = dp[j-1][k][s]
# 			elif j >= 1 and 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]]
# 			else:
# 				dp[j][k][s] = 0
# sum = 0
# for i in range(1, N+1):
# 	sum += dp[N][i][i*A]
# print(sum)

dp = [[0]*(2*N*X+1) for _ in range(N+1)]
y = [0] * len(x)
for i in range(len(x)):
	y[i] = x[i]-A

for j in range(N+1):
	for t in range(2*N*X+1):
		if j == 0 and t == N*X:
			dp[j][t] = 1
		elif j >= 1 and (t-y[j-1] < 0 or t-y[j-1] > 2*N*X):
			dp[j][t] = dp[j-1][t]
		elif dp[j-1][t] + dp[j-1][t-y[j-1]]:
			dp[j][t] = dp[j-1][t] + dp[j-1][t-y[j-1]]
		else:
			dp[j][t] = 0
print(dp[N][N*X]-1)

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = [np.array([[0]*(N*A+1) for _ in range(N+1)])]
#dp[0]: [0, 0]～[N, N*A]

for x in X:
  new_dp = dp[-1]
  new_dp[1:, x:] += dp[-1][0:N, 0:N*A+1-x]
  new_dp[1, x] += 1
  
  dp.append(new_dp)
#print(dp[-1])
  
print(sum([dp[-1][i, i*A] for i in range(1, N+1)]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = [np.array([[0]*(N*A+1) for _ in range(N+1)])]
#dp[0]: [0, 0]～[N, N*A]

for x in X:
  new_dp = dp[-1]
  new_dp[1:, x:] += dp[-1][0:N, 0:N*A+1-x]
  new_dp[1, x] += 1
  
  dp.append(new_dp)
print(dp[-1])
  
print(sum([dp[-1][i, i*A] for i in range(1, N+1)]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = [np.array([[0]*(N*A+1) for _ in range(N+1)])]
#dp[0]: [0, 0]～[N, N*A]

for x in X:
  new_dp = dp[-1]
  new_dp[1:, x:] += dp[-1][0:N, 0:N*A+1-x]
  new_dp[1, x] += 1
  
  dp.append(new_dp)
#print(dp[-1])
  
print(sum([dp[-1][i][i*A] for i in range(1, N+1)]))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.ndimage.interpolation import shift

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

dp = [np.array([[0]*(N*A+1) for _ in range(N+1)])]
#dp[0]: [0][0]～[N][N*A]

for x in X:
  new_dp = dp[-1] + shift(dp[-1], [1, x], cval=0)
  new_dp[1][x] += 1
  
  dp.append(new_dp)
#print(dp[-1])
  
print(sum([dp[-1][i][i*A] for i in range(1, N+1)]))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.ndimage.interpolation import shift

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

dp = [np.array([[0]*(N*A+1) for _ in range(N)])]

for i in range(N):
  new_dp = dp[-1]+ shift(dp[-1], [1, X[i]], cval=0)
  new_dp[0][X[i]]=new_dp[0][X[i]]+1
  
  dp.append(new_dp)
#print(dp[-1])
  
print(sum([dp[-1][i-1][i*A] for i in range(1,N+1)]))

Submission status: Runtime Error

Solution code:
n,a = map(int,input().split())
dp = [[0]*2000 for _ in range(n+1)]
dp[0][1000] = 1
x = list(map(int,input().split()))
for i in range(n):
  x[i] -= a
for i in range(1,n+1):
  for j in range(2001):
    dp[i][j] = dp[i-1][j] + dp[i-1][j-x[i-1]]
print(dp[n][1000])

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>

using namespace std;

unsigned long long dp[51][51][2501];

int main(int argc, char const *argv[])
{
    int N, A;
    cin>>N>>A;

    vector<int> x(N+1);
    for(int i=0; i<N; i++) {
        cin >> x[i+1];
    }

    dp[0][0][0] = 1;
    for(int j=1; j<=N; j++) {
        for(int k=0; k<=N; k++) {
            for(int s=0; s<=k*A; s++) {
                dp[j][k][s] += dp[j-1][k][s];
                if(s >= x[j])
                    dp[j][k][s] += dp[j-1][k-1][s-x[j]];
            }
        }
    }
    unsigned long long ans = 0;
    for(int k=1; k<=N; k++)
        ans += dp[N][k][k*A];
    cout << ans << endl;

    return 0;
}

Submission status: Runtime Error

Solution code:
def zeros(*dim):
    import copy
    if len(dim)==0:
        return 0
    else:
        d = dim[0]
        a = zeros(*dim[1:])
        return [copy.deepcopy(a) for _ in range(d)]


def solve(a, A):
    a = sorted(a)
    N = len(a)
    S = sum(a)
    dp = zeros(N+1, N+1, S+1)

    a.insert(0, float("inf"))  # add dummy at the head

    dp[0][0][0] = 1
    for j in range(1, N+1):
        for k in range(0, N+1):
            for s in range(0, S+1):
                dp[j][k][s] += dp[j-1][k][s]
                if s >= a[j]:
                    dp[j][k][s] += dp[j-1][k-1][s-a[j]]
    ans = 0
    for k in range(1, N+1):
        ans += dp[N][k][k*A]
    return ans


def main():
    N, A = map(int,input().split())
    a = [int(x) for x in input().split()]
    print(solve(a,A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    #入力
    n, a = map(int,input().split())
    x = [0] + list(map(int,input().split()))

    sum_max = (n)*(max(x))+1

    #dp[i][j][k]:x1-xiからj枚選んで、合計をkにする選び方の数
    dp = [[[0]*sum_max 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(sum_max):
                #xi>kのとき
                if x[i]>k:
                    dp[i][j][k] = dp[i-1][j][k]
                elif k>=1 and x[i-1]<=k:
                    #xi<=kのとき
                    dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-x[i]]

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

X = [int(x) - A for x in input().split()]
dp = [[0 for _ in range(100*N+1)] for _ in range(N+1)]
dp[0][50*N] = 1

for i in range(N):
  for j in range(50, 100*N+1-50):
    dp[i+1][j] = dp[i][j] + dp[i][j - X[i]]
print(dp[N][50*N] - 1)

Submission status: Runtime Error

Solution code:
N, A = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(lambda n:n-A, x))

X = max(x)
dp = [[0 for i in range(2*X*N + 1)] for j in range(N + 1)]

for i in range(1, N + 1):
    dp[i][y[i - 1] + N*X] += 1
    for j in range(len(dp[0])):
        dp[i][j] += dp[i - 1][j]
        if dp[i - 1][j] > 0:
            dp[i][j + y[i - 1]] += dp[i - 1][j]

print(dp[N][N*X])

Submission status: Runtime Error

Solution code:
import collections as c
n,a=map(int,input().split())
X=[int(x)-a for x in input().split()]
C=c.Counter([0])
for x in X:
  itiji=Counter()
  for i,c in C.items():
    itiji[i+x]+=c
  C+=itiji
print(C[0]-1)

Submission status: Runtime Error

Solution code:
n,a=map(int,input().split())
*x,=map(int,input().split())
b=max(x)
dp=[[[0]*(n*b+1) for i in range(n+1)] for _ in range(n+1)]

for i in range(n+1):
    for j in range(n+1):
        for k in range(n*b+1):
            if i==0 and j==0 and k==0:
                dp[i][j][k]=1
            elif i and k<x[i-1]:
                dp[i][j][k]=dp[i-1][j][k]
            elif i and j and k>=x[i-1]:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N, A;
    cin >> N >> A;
    vector<int> cards(N);
    int maxX = -1*(1<<30);
    for(int i=0; i<N; ++i){
        cin >> cards[i];
        maxX = max(maxX, cards[i]);
        cards[i] -= A;
    }
    const int M = N * maxX;
    vector<vector<long long> > DP(N+1, vector<long long>(2*M+1, 0));
    DP[0][M] = 1;
    for(int i=1; i<=N; ++i){
        for(int j=0; j<2*M+1; ++j){
            DP[i][j] += DP[i-1][j];
            if(j-cards[i-1]>=0 and j-cards[i-1]<=2*M){
                DP[i][j] += DP[i-1][j-cards[i-1]];
            }
        }
    }
    cout << DP[N][M] -1 << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
N,A=map(int,input().split())
x=input().split()
for i in range(N):
    x[i]=int(x[i])
ans=0
y=[0 for i in range(N)]
def check(ans,y):
    ave=0
    for i in range(N):
        ave+=x[i]*y[i]
    if sum(y)!=0:
        ave=ave/sum(y)
    if sum(y)==0:
        ave=0
    if ave==A:ans+=1
    return ans

def branch(ans,now,pre,y):
    if now==0 and pre==-1:
        if y[now]==0:
            y[now]=1
            now+=1
            pre=1
            ans,now,pre=branch(ans,now,pre,y)
        elif y[now]==1:
            return ans,now,pre

    elif now==N-1:
        ans,now,pre=last(ans,now,pre,y)
        ans,now,pre=branch(ans,now,pre,y)
    
    elif now!=0 and pre==-1:
        if y[now]==0:
            y[now]=1
            pre=1
            now+=1
            ans,now,pre=branch(ans,now,pre,y)
        elif y[now]==1:
            y[now]=0
            now-=1
            ans,now,pre=branch(ans,now,pre,y)
    elif pre==1 and now!=N-1:
        now+=1
        ans,now,pre=branch(ans,now,pre,y)
    return ans,now,pre

def last(ans,now,pre,y):
    y[-1]=0
    ans = check(ans,y)
    y[-1]=1
    ans = check(ans,y)
    y[-1]=0
    pre=-1
    now-=1
    return ans,now,pre
now=0
pre=1
ans,now,pre=branch(ans,now,pre,y)
print(ans)

Submission status: Runtime Error

Solution code:
N,A = map(int,input().split())
x = [0] + list(map(int,input().split()))
X = max(x)
dp = [[[0]*(N*X+1) for k in range(N+1)] for j in range(N+1)]

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

Submission status: Runtime Error

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
M = max(x)

dp = [[[0]*(n*M+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for j in range(n):
    for k in range(n+1):
        for s in range(n*M+1):
            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]
 
ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]
print(ans)

Submission status: Runtime Error

Solution code:
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
maxn = max(max(X), A)
 
dp = [[0 for _ in range(2 * N * maxn + 1)] for _ in range(N + 1)]
dp[0][N * maxn] = 1
 
for i in range(N):
    for k in range(2 * N * maxn + 1):
        dp[i + 1][k] = dp[i][k]
        if 0 <= k - X[i] <= 2 * N * maxn:
            dp[i + 1][k] += dp[i][k - X[i]]
 
print(dp[N][N * maxn] - 1)
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
maxn = max(max(X), A)

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

for i in range(N):
    for k in range(2 * N * maxn + 1):
        dp[i + 1][k] = dp[i][k]
        if 0 <= k - X[i] <= 2 * N * maxn:
            dp[i + 1][k] += dp[i][k - X[i]]

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

Submission status: Runtime Error

Solution code:
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
maxn = max(max(X), A)
 
dp = [[0 for _ in range(2 * N * maxn + 1)] for _ in range(N + 1)]
dp[0][N * maxn] = 1
 
for i in range(N):
    for k in range(2 * N * maxn + 1):
        dp[i + 1][k] = dp[i][k]
        if 0 <= k - X[i] <= 2 * N * maxn:
            dp[i + 1][k] += dp[i][k - X[i]]
 
print(dp[N][N * maxn] - 1)
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
maxn = max(max(X), A)

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

for i in range(N):
    for k in range(2 * N * maxn + 1):
        dp[i + 1][k] = dp[i][k]
        if 0 <= k - X[i] < 2 * N * maxn:
            dp[i + 1][k] += dp[i][k - X[i]]

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

for i in range(N):
    for j in range(N):
        for k in range(max(X) * N + 1):
            dp[i + 1][j][k] += dp[i][j][k]
            if k >= X[i]:
                dp[i + 1][j + 1][k] += dp[i][j][k - X[i]]

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

print(ans)

Submission status: Runtime Error

Solution code:
import collections

# input
n, a = map(int, input().split())
X = [int(i) - a for i in input().split()]

S = collections.Counter([0, X[0]])
# Xから1枚以上選んで作ることが可能な和:作り方の場合の数
# 1枚も選ばない＝0:1通り
# X[0]のみ選ぶ＝X[0]:1通り

for i in X[1:]: # 選べるカードを増やしていく (X[0] ~ X[i] から選ぶ)
    S_temp = collections.Counter()
    for s, c in S.items():
        S_temp[s + i] += c # X[0] ~ X[i - 1] で作れる和に X[i] を足す
    sums += sums2

print(S[0] - 1) # 1枚も選ばないのはルール違反

Submission status: Runtime Error

Solution code:
import math
from itertools import combinations


def solve(N, A, Xs):
    diffs = [x - A for x in Xs]
    minus = [d for d in diffs if d < 0]
    minuses = {}
    plus = [d for d in diffs if d > 0]
    pluses = {}
    zero = [d for d in diffs if d == 0]

    for n in range(1, len(minus) + 1):
        for ns in combinations(minus, n):
            s = sum(ns)
            minuses.setdefault(s, 0)
            minuses[s] += 1

    for n in range(1, len(plus) + 1):
        for ns in combinations(plus, n):
            s = sum(ns)
            pluses.setdefault(s, 0)
            pluses[s] += 1

    def nCr(n, r):
        f = math.factorial
        return f(n) // f(r) // f(n - r)

    z = sum([nCr(len(zero), r) for r in range(len(zero))])
    c = 0
    for m in minuses:
        c += pluses[-m] * (z + 1)
    c += z
    return c


if __name__ == "__main__":
    N, A = map(int, input().split(" "))
    Xs = map(int, input().split(" "))
    print(solve(N, A, Xs))