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:
# ABC044
N, A = map(int, input().split())
X = list(map(int, input().split()))

# 2 ** 50 -> 全探索は厳しい -> DP
# dp[i][k][wa] = i枚まで見て、k枚選んだ時の合計値がwaとなるときの選び方の合計
# max wa = max(X) * N
max_wa = max(X) * N

dp = [[[0] * 2550 for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for k in range(N):
        for wa in range(2501):
            # 選ぶとき
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            # 選ばないとき
            dp[i+1][k][wa] += dp[i][k][wa]

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

print(ans)

Submission status: Runtime Error

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

# 2 ** 50 -> 全探索は厳しい -> DP
# dp[i][k][wa] = i枚まで見て、k枚選んだ時の合計値がwaとなるときの選び方の合計
# max wa = max(X) * N
max_wa = max(X) * N

dp = [[[0] * (N*A+5) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for k in range(N):
        for wa in range(max_wa):
            # 選ぶとき
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            # 選ばないとき
            dp[i+1][k][wa] += dp[i][k][wa]

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

print(ans)

Submission status: Runtime Error

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

# 2 ** 50 -> 全探索は厳しい -> DP
# dp[i][k][wa] = i枚まで見て、k枚選んだ時の合計値がwaとなるときの選び方の合計
# max wa = max(X) * N
max_wa = max(X) * N
if max_wa < A:
    print(0)
    exit()
dp = [[[0] * (max_wa+50) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for k in range(i+1):
        for wa in range(max_wa):
            # 選ぶとき
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            # 選ばないとき
            dp[i+1][k][wa] += dp[i][k][wa]

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

print(ans)

Submission status: Runtime Error

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

# 2 ** 50 -> 全探索は厳しい -> DP
# dp[i][k][wa] = i枚まで見て、k枚選んだ時の合計値がwaとなるときの選び方の合計
# max wa = max(X) * N
max_wa = max(X) * N
dp = [[[0] * (max_wa+50) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for k in range(i+1):
        for wa in range(max_wa):
            # 選ぶとき
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            # 選ばないとき
            dp[i+1][k][wa] += dp[i][k][wa]

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

print(ans)

Submission status: Runtime Error

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

# 2 ** 50 -> 全探索は厳しい -> DP
# dp[i][k][wa] = i枚まで見て、k枚選んだ時の合計値がwaとなるときの選び方の合計
# max wa = max(X) * N
max_wa = max(X) * N
dp = [[[0] * (max_wa + 5) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for k in range(i+1):
        for wa in range(max_wa):
            # 選ぶとき
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            # 選ばないとき
            dp[i+1][k][wa] += dp[i][k][wa]

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

print(ans)

Submission status: Runtime Error

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

# 2 ** 50 -> 全探索は厳しい -> DP
# dp[i][k][wa] = i枚まで見て、k枚選んだ時の合計値がwaとなるときの選び方の合計
# max wa = max(X) * N
max_wa = max(X) * N
dp = [[[0] * (max_wa + 5)) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for k in range(i+1):
        for wa in range(max_wa):
            # 選ぶとき
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            # 選ばないとき
            dp[i+1][k][wa] += dp[i][k][wa]

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

print(ans)

Submission status: Runtime Error

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

# 2 ** 50 -> 全探索は厳しい -> DP
# dp[i][k][wa] = i枚まで見て、k枚選んだ時の合計値がwaとなるときの選び方の合計
# max wa = max(X) * N
max_wa = max(X) * N
dp = [[[0] * (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 k in range(i+1):
        for wa in range(max_wa):
            # 選ぶとき
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            # 選ばないとき
            dp[i+1][k][wa] += dp[i][k][wa]

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

print(ans)

Submission status: Runtime Error

Solution code:
N, A = [int(_) for _ in input().split()]

MAX_I = 2000
memo = [[0] * MAX_I for _ in range(N + 2)]


def cnv(v):
    return v - A + (MAX_I // 2)


X = [int(_) for _ in input().split()]
for i in range(N):
    offset = X[i] - A
    # print('x', offset)

    mm = memo[i]
    for j in range(MAX_I):
        if mm[j] > 0:
            memo[i + 1][j + offset] += mm[j]
        memo[i + 1][j] += mm[j]

    memo[i + 1][cnv(X[i])] += 1

print(memo[N][MAX_I//2])

Submission status: Runtime Error

Solution code:
N, A = [int(_) for _ in input().split()]

MAX_I = 1000
memo = [[0] * MAX_I for _ in range(N + 2)]


def cnv(v):
    return v - A + (MAX_I // 2)


X = [int(_) for _ in input().split()]
for i in range(N):
    offset = X[i] - A
    # print('x', offset)

    mm = memo[i]
    for j in range(MAX_I):
        if mm[j] > 0:
            memo[i + 1][j + offset] += mm[j]
        memo[i + 1][j] += mm[j]

    memo[i + 1][cnv(X[i])] += 1

print(memo[N][MAX_I//2])

Submission status: Runtime Error

Solution code:
N, A = [int(_) for _ in input().split()]

MAX_I = 200
memo = [[0] * MAX_I for _ in range(N + 2)]


def cnv(v):
    return v - A + (MAX_I // 2)


X = [int(_) for _ in input().split()]
for i in range(N):
    offset = X[i] - A
    # print('x', offset)

    mm = memo[i]
    for j in range(MAX_I):
        if mm[j] > 0:
            # print('j+x', j + offset)
            memo[i + 1][j + offset] += mm[j]
        memo[i + 1][j] += mm[j]

    memo[i + 1][cnv(X[i])] += 1
    # print(memo[i + 1][90:110])

print(memo[i + 1][100])

Submission status: Runtime Error

Solution code:
import numpy as np
N, A = map(int, input().split())
X = list(map(int, input().split()))
sum_X = sum(X)
dp = np.zeros((N+1, N+1, sum_X+1), np.int64)
dp[0][0][0] = 1
for i in range(N):
  for j in range(N):
    for k in range(sum_X):
      if dp[i][j][k] == 0: continue
      # not used
      dp[i+1][j][k] += dp[i][j][k]
      # used
      dp[i+1][j+1][k+X[i]] += dp[i][j][k]
ans = 0
for i in range(1, N+1):
  ans += dp[N][i][i*A]
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N, A = map(int,input().split())
X = [int(x) for x in input().split()]
 
dp = np.zeros((N+1,sum(X)+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)

Submission status: Runtime Error

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

L = max(A)*N
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)

Submission status: Runtime Error

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

#aとの差を記録してリストに入れなおす
x = list(map(lambda i: i-a, x))
#print(x)

#dp初期値
dp = {0: 1}

#dpにぶち込む値をxから取り出す
for num in x:
  #dpにあるすべてのkey,valueに対して、すでにdpにkeyがi+kのデータがあればそのvalueなければ,0を返し、それ+vをdpとする。
  for k,v in list(dp.items()):
    dp[i+k]=dp.get(i+k,0)+v
    
  #print(dp)
#全部使わない選択肢だけ引いておく  
print(dp[0]-1)
#print(dp)

Submission status: Runtime Error

Solution code:
[n,a]=list(map(int,input().split()))
xlist=list(map(int,input().split()))
xlist.sort()
for i in range(n):
	ave=a*i
	dp=[-1 for j in range(ave+1)]
	dp[0]=1
	for k in xlist:
		for l in range(len(xlist)):
			if dp[l]!=-1 and l+k<=ave:
				if dp[l+k]==-1:
					dp[l+k]=0
				dp[l+k]+=dp[l]
	ans+=dp[-1]
print(ans)

Submission status: Runtime Error

Solution code:
def main()
  N,A = map(int, input().split())
  x = list(map(int, input().split()))

  for i in range(1,1 << len(x)):
      total = []
      for j in range(len(x)):
          if ((i >> j) & 1):
              total.append(x[j])
      if len(total):
          if (sum(total)/len(total)) == A:
              count += 1

  print(count)

main()

Submission status: Runtime Error

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

for i in range(1,1 << len(x)):
    total = []
    for j in range(len(x)):
        if ((i >> j) & 1):
            total.append(x[j])
    if len(total):
        if (sum(total)/len(total)) == A:
            count += 1
        
print(count)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

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

dp = [[0 for i in range(N + 1)] for j in range(50 * N + 1)] #[Sum, #Cards]
dp[0][0]=1

for i in range(N):#Focus Card [x_i]
  #Use x_i
  for j in range(N):
    for k in range(50 * N + 1):
      dp[k + X[i]][j+1] = dp[k][j]

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

total = sum(x)

# dp[i][j][k] := i枚目までからj枚取って、合計をkにする通り数
dp = [[[0] * (total+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(total+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):
     # N枚(カード総数)の中から1枚以上取った時の、j枚取って合計がj*Aの所 の合計
    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()))
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):
    ans += dp[N-1][j][A*j]

print(ans)

Submission status: Runtime Error

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

# dp[i][j][k] i枚までj枚えらんで合計k
# 答えはdp[n][1..n][a..ak]
dp = [[[0] * 2502 for _ in range(52)]
      for __ in range(52)]

dp[0][0][0] = 1
for i in range(0, n):
    for j in range(0, n + 1):
        for k in range(n * max(X) + 1):
            dp[i + 1][j][k] += dp[i][j][k]  # 選ぶ
            dp[i + 1][j + 1][k + X[i]] += dp[i][j][k]  # 選ばない

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

Submission status: Runtime Error

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

# dp[i][j][k] i枚までj枚えらんで合計k
# 答えはdp[n][1..n][a..ak]
dp = [[[0] * 3500 for _ in range(51)]
      for __ in range(51)]

dp[0][0][0] = 1
for i in range(0, n):
    for j in range(0, n + 1):
        for k in range(n * max(X) + 1):
            dp[i + 1][j][k] += dp[i][j][k]  # 選ぶ
            dp[i + 1][j + 1][k + X[i]] += dp[i][j][k]  # 選ばない

ans = 0
for i in range(1, n+1):
    for j in range(a, 2501):
        if i * a == j:
            ans += dp[n][i][j]
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
mx = max(x)*n+1

dp = [[0 for i in range(3*mx)] for j in range(n)]
dp[0][0] += 1
dp[0][x[0]] += 1

for i in range(1,n) :
    for j in range(-mx,mx):
        dp[i][j] += dp[i-1][j-x[i]]
        dp[i][j] += dp[i-1][j]
    #print(*dp[i])
print(dp[n-1][0]-1)

Submission status: Runtime Error

Solution code:
n, a = map(int, input().split())
x = [0] + list(map(int, input().split()))
nx = n*max(x)

# DP: x1からxjまでの間でk枚を選んで合計がsになる組み合わせの数
dp = [ [ [0 for s in range(nx+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(n+1):
        for s in range(nx+1):
            if x[j] > s:
                dp[j][k][s] = dp[j-1][k][s]
            elif k >= 1:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j]]
#print(dp)
ans = 0
for k in range(1, n+1):
    ans += dp[-1][k][a * k]

print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
from math import factorial
n = list(map(int, input().split()))
x = np.array(list(map(int, input().split())))

x = x - n[1]
b = len(x) - np.count_nonzero(x)
x = [i for i in x if i != 0]
x = np.sort(x)

c = 0
for i in range(1, b + 1):
    c += factorial(b) / factorial(i) / factorial(b - i)

cnt = c
for i in range(2, n[0] + 1):
    a = np.array(list(itertools.combinations(x, i)))
    if sum(a[0]) > 0:
        break
    a = np.sum(a, axis = 1)
    cnt += (c + 1) * (len(a) - np.count_nonzero(a))
            
print(int(cnt))

Submission status: Runtime Error

Solution code:
inp=input().split(" ")
N=int(inp[0])
A=int(inp[1])
x=list(map(int, input().split(" ")))
x=[0]+x
X=max(x)
dp=[[[0 for i in range(N*X+1)] for j in range(N+1)] for k 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
print(sum(dp[N][k][k*A] for k in range(1,N+1)))

Submission status: Runtime Error

Solution code:
from collections import Counter

from operator import mul
from functools import reduce
def cmb(n,r):
	if n < r:return 0
	if r == 0 or n-r == 0:return 1
	r = min(n-r,r)
	u = reduce(mul, range(n, n-r, -1))
	d = reduce(mul, range(1,r+1))
	return u//d

n,a,*x = map(int,open(0).read().split())
dp = [[0]*(n*max(x)+1)for _ in range(n+1)]
dp[0][0] = 1
lim1 = lim2 = 1
for k,v in Counter(x).items():
	for i in range(1,v+1):
		c = cmb(v,i)
		for j in range(lim1)[::-1]:
			for s in range(lim2)[::-1]:
				dp[j+i][s+k*i] += dp[j][s]*c
	lim1 += v
	lim2 += k*v
cnt = 0
for i in range(1,n+1):
	cnt += dp[i][i*a]
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

pair_memo = {}
def pair_pattern(a, b=None):
  if 0 in [a, b]:
    return 0
  
  if b in [None, 1]:
    return a
  
  if a == 1:
    return b
  
  key = f"{a},{b}"
  if key in pair_memo:
    return pair_memo[key]
  
  pair_memo[key] = pair_pattern(a - 1, b) * pair_pattern(a, b - 1) - 1
  return pair_memo[key]

def sign_special(x):
  if x >= 0:
    return 0
  else:
    return 1
    
if __name__ == "__main__":
  n, a = map(int, input().split())
  list_x = list(map(int, input().split()))
  elem = lambda : [0, 0]
  x_group_by_abs = defaultdict(elem)
  x_group_by_abs[0] = [0]

  for x in list_x:
    x_group_by_abs[abs(x - a)][sign_special(x - a)] += 1 
    
  ans = 1
  for x_g in x_group_by_abs.values():
    p = pair_pattern(*x_g)
    print(f"{x_g}: {p}")
    ans *= p + 1

  ans -= 1
  print(ans)

Submission status: Runtime Error

Solution code:
N, A = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
# mat = {}
def dp(i, x):
  if i == N:
    if len(x) and sum(x) == A * len(x):
      return 1
    else:
      return 0
  elif len(x) and (i, sum(x)/len(x)) in mat:
    return mat[(i, sum(x)/len(x))]
  ret = dp(i + 1, x) + dp(i + 1, x + [X[i]])
  # if len(x):
    # mat[i, sum(x)/len(x)] = ret
  return ret

print(dp(0, []))

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 _ in range(n*x_max+1)] for _ 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*x_max+1):
            if i == 0 and j == 0 and k == 0:
                dp[i][j][k] = 1
            elif i >= 1 and k < x[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            elif i >= 1 and j >= 1 and k >= x[i-1]:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k - x[i-1]]
            else:
                dp[i][j][k] = 0
ans = 0
for k in range(n+1):
    ans += dp[n][k][k*a]
print(ans-1)

Submission status: Runtime Error

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
y=[i-a for i in x]
y.sort()
minus=[-i for i in y if i<0]
minus.sort()
plus=[i for i in y if i>0]
zero=len([i for i in y if i==0])

ma=max(y)*n
ny=ma*2
dp=[[0]*(ny+1) for _ in range(n+1)]
for i in range(n+1):
  for j in range(ny+1):
    if i==0 and j==ma:
      dp[i][j]=1
    elif i>=1:
      sa=j-y[i-1]
      if sa<0 or sa>ny:
        dp[i][j]=dp[i-1][j]
      else:
        dp[i][j]=dp[i-1][j]+dp[i-1][sa]
print(dp[n][ma]-1)

Submission status: Runtime Error

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

dp = [[[0 for _ in range(2500+１０)] 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(2500+1):
            dp[i+1][j][k] += dp[i][j][k]
            dp[i+1][j+1][k+X[i]] += dp[i][j][k]

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

print(ans)

Submission status: Runtime Error

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

dp = [[[0 for _ in range(３０１０)] 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(2500+1):
            dp[i+1][j][k] += dp[i][j][k]
            dp[i+1][j+1][k+X[i]] += dp[i][j][k]

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

print(ans)

Submission status: Runtime Error

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

dp = [[[0 for _ in range(2500+10)] 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(2500+1):
            dp[i+1][j][k] += dp[i][j][k]
            dp[i+1][j+1][k+X[i]] += dp[i][j][k]

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

print(ans)

Submission status: Runtime Error

Solution code:
n,a=[int(i) for i in input().split()]
x=[int(i) for i in input().split()]
y=[i-a for i in x]
m=sum(x)+1
dp=[[0 for j in range(m*2+1)] for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(-m,1+m):
        if j-y[i-1]>=-m:
            dp[i][j]=dp[i-1][j]+dp[i-1][j-y[i-1]]
        else:
            dp[i][j]=dp[i-1][j]

print(dp[n][0]-1)

Submission status: Runtime Error

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

xn=[x[i]-A for i in range(len(x)) if x[i]<A]
xn.reverse()
x0=[0 for i in range(len(xn),len(x)) if x[i]==A]
xp=[x[i]-A for i in range(len(xn)+len(x0),len(x)) if x[i]>A]

sxn=[0]
sxn_n=[1]
for x in xn:
  sxn_add=[]
  sxn_n_i=[]
  for j in range(len(sxn)):
    sxn_tmp=sxn[j]+x
    for k in range(j,len(sxn)):
      if sxn[k]<=sxn_tmp or k==len(sxn)-1:
        if sxn[k]==sxn_tmp:
          sxn_n_i.append([k,sxn_n[j]])
        elif sxn[k]<sxn_tmp:
          sxn_add.append([k,sxn_tmp,sxn_n[j]])
        else:
          sxn_add.append([k+1,sxn_tmp,sxn_n[j]])
        break
  for k in range(len(sxn_add)):
    sxn.insert(k+sxn_add[k][0],sxn_add[k][1])
    sxn_n.insert(k+sxn_add[k][0],1)
  for l in sxn_n_i:
    sxp_n[l[0]]+=l[1]    

sxp=[0]
sxp_n=[1]
for x in xp:
  sxp_add=[]
  sxp_n_i=[]
  for j in range(len(sxp)):

    sxp_tmp=sxp[j]+x

    for k in range(j,len(sxp)):
      if sxp[k]>=sxp_tmp or k==len(sxp)-1:

        if sxp[k]==sxp_tmp:
          sxp_n_i.append([k,sxp_n[j]])
        elif sxp[k]>sxp_tmp:
          sxp_add.append([k,sxp_tmp,sxp_n[j]])
        else:
          sxp_add.append([k+1,sxp_tmp,sxp_n[j]])
        break

  for k in range(len(sxp_add)):
    sxp.insert(k+sxp_add[k][0],sxp_add[k][1])
    sxp_n.insert(k+sxp_add[k][0],sxp_add[k][2])
  for l in sxp_n_i:
    sxp_n[l[0]]+=l[1]



an=0
for i in range(1,len(sxp)):
  for j in range(1,len(sxn)):

    if sxp[i]==-sxn[j]:
      an+=sxp_n[i]*sxn_n[j]
      break


print(2**len(x0)-1+an*2**(len(x0)))

Submission status: Runtime Error

Solution code:
num,ave = map(int,input().split())
numx = list(map(int,input().split()))

L = len(numx)
numy = [0] * L
for i in range(L):
    numy[i] = numx[i] - ave

if abs(min(numy)) < abs(max(numy)):
    maxX = max(numy)
else:
    maxX = abs(min(numy))

dp = [[0]*(2*maxX*L+1) for _ in range(L+1)]
dp[0][maxX*L] = 1
for i in range(L):
    for j in range(2*maxX*L+1):
        if (j-numy[i]) < 0 or (j - numy[i]) > 2*maxX*L:
            dp[i+1][j] = dp[i][j]
        else
        dp[i+1][j] = dp[i][j] + dp[i][j-numy[i]]
print(dp[L][maxX*L]-1)

Submission status: Runtime Error

Solution code:
[n,a]=list(map(int,input().split()))
xlist=list(map(int,input().split()))
counter=0
wa=0
for kazu in range(1,2**(n+1))
	keisu=[]
	for i in reversed(range(0,n)):
		keisu.append(kazu//(2**i))
	for i in range(n):
		wa+=keisu[i]*xlist[i]
	kosu=keisu.count(1)
	if wa==kosu*a:
		counter+=1

print(counter)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools

def solve(N: int, A: int, x: "List[int]"):
    X = max(x)
    dp = [[[0 for _ in range(N*X+1)] for _ in range(N+1) ] for _ in range(N+1)]
    dp[0][0][0] = 1
    for n in range(N+1):
        for m in range(N+1):
            for k in range(N*X+1):
                if n >= 1 and k < x[n-1]:
                    dp[n][m][k] = dp[n-1][m][k]
                elif n >= 1 and m >= 1 and k >= x[n-1]:
                    dp[n][m][k] = dp[n-1][m][k] + dp[n-1][m-1][k-x[n-1]]
    s = 0
    for i in range(1, N+1):
        s += dp[N][i][i*A]
    print(s)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    x = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A, x)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-

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

    # dp[i][j] := 左からi+1枚目までにj枚を選んで、選んだカードの総和がkになるカードの選び方
    dp = [[[0 for _ in range(N+1)] for __ in range(N+1)] for ___ in range(50*51+1)]
    dp[0][0][0] = 1  # 何も選んでない初期値
    for i in range(0, N):
        for j in range(0, N):
            for k in range(50*50+1):
                if dp[i][j][k] != 0:
                    dp[i+1][j][k] += dp[i][j][k]  # i枚目を選ばない
                    dp[i+1][j+1][k] += dp[i][j][k-X[i]]  # i枚目を選んだ

    ans = 0
    for j in range(1, N+1):  # 1枚以上選ぶ必要がある
        ans += dp[N][j][j*A]
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
from  collections import Counter

def main():
    num, avg = map(int, input().split())
    data = list(map(int, input().split()))

    dp = [[[0 for i in range(max(num, avg) * max(data) + 1)] for j in range(num + 1)] for k in range(num + 1)]
    dp[0][0][0] = 1

    for i in range(1, num + 1):
        now_card = data[i - 1]
        for j in range(num + 1):
            for k in range(max(num, avg) * max(data) + 1):
                # print(i, j, k)
                dp[i][j][k] += dp[i - 1][j][k]
                if k - now_card >= 0 and j - 1 >= 0:
                    dp[i][j][k] += dp[i - 1][j - 1][k - now_card]
        # print(dp[i][j])

    ans = 0
    for i in range(1, num + 1):
        ans += dp[num][i][i * avg]
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

from  collections import Counter

def main():
    num, avg = map(int, input().split())
    data = list(map(int, input().split()))

    dp = [[[0 for i in range(num * max(data) + 1)] for j in range(num + 1)] for k in range(num + 1)]
    dp[0][0][0] = 1

    for i in range(1, num + 1):
        now_card = data[i - 1]
        for j in range(num + 1):
            for k in range(num * max(data) + 1):
                # print(i, j, k)
                dp[i][j][k] += dp[i - 1][j][k]
                if k - now_card >= 0 and j - 1 >= 0:
                    dp[i][j][k] += dp[i - 1][j - 1][k - now_card]
        # print(dp[i][j])

    ans = 0
    for i in range(1, num + 1):
        ans += dp[num][i][i * avg]
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-
"""解説
dp[j][k][s] := x1,...,xjから k枚選んで xiの合計をsにするような選び方の総数

[@lilium氏]
https://atcoder.jp/contests/abc044/submissions/5887235
"""

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

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

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

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

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

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
n,a=map(int,input().split())
x=list(map(lambda x:int(x)-a,input().split()))
m=min(x)*n;M=max(x)*n+1
if max(x)<0 or min(x)>0:print(0);exit()
dp=[[0]*(M-m) for _ in range(n)]
dp[0][x[0]]+=1
dp[0][0]+=1
for i in range(n-1):
    for j in range(m,M):
        dp[i+1][j+x[i+1]]+=dp[i][j]
        dp[i+1][j]+=dp[i][j]
print(dp[n-1][0]-1)

Submission status: Runtime Error

Solution code:
n,a=map(int,input().split())
x=list(map(lambda x:int(x)-a,input().split()))
m=min(x)*n;M=max(x)*n+1
if M<0 or m>0:print(0);exit()
dp=[[0]*(M-m) for _ in range(n)]
dp[0][x[0]]+=1
dp[0][0]+=1
for i in range(n-1):
    for j in range(m,M):
        dp[i+1][j+x[i+1]]+=dp[i][j]
        dp[i+1][j]+=dp[i][j]
print(dp[n-1][0]-1)

Submission status: Runtime Error

Solution code:
n,a=map(int,input().split())
x=list(map(lambda x:int(x)-a,input().split()))
m=min(x)*n;M=max(x)*n+1
dp=[[0]*(M-m) for _ in range(n)]
dp[0][x[0]]+=1
dp[0][0]+=1
for i in range(n-1):
    for j in range(m,M):
        if dp[i][j]!=0:
            if j+x[i+1] in range(m,M):dp[i+1][j+x[i+1]]+=dp[i][j]
            dp[i+1][j]+=dp[i][j]
print(dp[n-1][0]-1)

Submission status: Runtime Error

Solution code:
n,a=map(int,input().split())
x=list(map(lambda x:int(x)-a,input().split()))
m=min(x)*n;M=max(x)*n+1
dp=[[0]*(M-m) for _ in range(n)]
dp[0][x[0]]+=1
dp[0][0]+=1
for i in range(n-1):
    for j in range(m,M):
        if dp[i][j]!=0:
            dp[i+1][j+x[i+1]]+=dp[i][j]
            dp[i+1][j]+=dp[i][j]
print(dp[n-1][0]-1)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n, a = li()
x = list(li())

dp = [[[0]*(n*max(x)+1) 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(n+1):
        for k in range(n*max(x) + 1):
            dp[i][j][k] += (dp[i-1][j-1][k-x[i-1]] if (j-1 >= 0 and k-x[i-1] >= 0) else 0)\
                            + dp[i-1][j][k]

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

print(ans)

Submission status: Runtime Error

Solution code:
n, avg = map(int, input().split())
a = list(map(int, input().split()))
mxsm = sum(a) + 5

dp = [[0] * mxsm for _ in range(n + 5)]

dp[0][0] = 1
rs = 0
for x in a:
    dp2 = [[it1 for it1 in lin] for lin in dp]
    for i in range(1, n + 1):
        for j in range(x, mxsm + 1):
            if dp[i - 1][j - x]:
                dp2[i][j] += dp[i - 1][j - x]
    dp = dp2

for i in range(1, n + 1):
    rs += dp[i][avg * i]

print(rs)

Submission status: Runtime Error

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

dp = [ [ [ 0 for j in range(N+1)] for i in range(xsum+1) ] for k in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for j in range(xsum+1):
        for k in range(N):
            if j - x[i] >=0:
                dp[i+1][j][k+1] = dp[i][j-x[i]][k]
            dp[i+1][j][k] += dp[i][j][k]

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