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: Accepted

Solution code:
from collections import defaultdict

N, A = map(int, input().split())
X = list(map(int, input().split()))
X = [x - A for x in X]

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

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

Submission status: Accepted

Solution code:
import numpy as np
 
n, a = map(int, input().split())
x = np.array(list(map(int, input().split())))
 
dp = {0:1}
for y in x-a:
    for k, v in dp.copy().items():
        dp[y+k] = dp.get(y+k, 0) + v 
print(dp[0]-1)

Submission status: Accepted

Solution code:
import numpy as np

n, a = map(int, input().split())
x = np.array(list(map(int, input().split())))

dp = {0:1}
for y in x-a:
    for k, v in dp.copy().items():
        dp[y+k] = dp.get(y+k, 0) + v

print(dp[0]-1)

Submission status: Accepted

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

dp = {0 : 1}

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

Submission status: Accepted

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

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

dp = [0]*5000###-2500~2499,idx=2500が0に対応
dp[2500] = 1

for i in range(N):
    pre = dp[:]
    for j in range(max(0,-x[i]),min(4999,4999-x[i])):
        dp[j+x[i]] += pre[j]
    #print(pre[2490:2510])
    #print(dp[2490:2510])

#print(x)
print(dp[2500]-1)

Submission status: Accepted

Solution code:
# 配列を大きめにとって配った方がすっきりかけるのかも

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

#if j == 0 and k == 0 and s == 0:
dp[0][0][0] = 1
for j in range(n):
    for k in range(n):
        for s in range(n*X):

            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: Accepted

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

Submission status: Accepted

Solution code:
N,A=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0]*2600 for j in range(N+10)] for i in range(N+10)]
dp[0][0][0]=1
for i in range(N):
    for j in range(N+1):
        for k in range(2501):
            if(dp[i][j][k]!=0):
                dp[i+1][j][k]+=dp[i][j][k]
                dp[i+1][j+1][k+x[i]]+=dp[i][j][k]
print(sum(dp[N][i][i*A] for i in range(1,N+1)))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc044/tasks/arc060_a
# ソートしてからごちゃごちゃやればどうにかなりそう(無理でした)

'''
解説満点解法1
もしもk枚選んだとき、合計がsになる通りの数がわかったら？→s=k*Aとなる場合の数の合計をすれば良い

k枚選んだとき、合計がsになる通りの数は典型的なDP！
dp(j,k,s)... X[0:j]からk枚選んで、その合計をsにするような選び方の総数
と定義すると、

更新則
dp(j+1,k,s) = X[j]を選んだ結果sになったときの通りの数 + X[j]を選ばずにsになっている通りの数 なので
すなわち
dp(j+1,k,s) = dp(j,k-1,s-X[j]) + dp(j,k,s)

あとは初期条件と境界条件と伝播条件を付け加える。
境界条件 dp(j,k,0)=0 (数枚選んで合計が0になるのはありえない)
初期条件 dp(j,0,0)=1 (ただし、0枚選んだときは1通りとなる)(s-X[j]=0のときに1通りとなってほしいという気持ちもある)
伝播条件 s-X[j]<0に関しては dp(j,k-1,s-X[j])が必ず0通りとなる(ありえないので)
'''

import sys
read = sys.stdin.readline
from itertools import product


def read_ints():
    return list(map(int, read().split()))


N, A = read_ints()
X = read_ints()
# S = sum(X)

# # 満点解法1
# dp = [[[0] * (S + 1) for _ in range(N + 1)] for _ in range(N + 1)]
# for j in range(N + 1):  # 初期条件
#     dp[j][0][0] = 1  # 1枚も選ばずに0になるのは1通り
# # 0,0,0は1でいい∵ j,1,xで1通りになりたいときに1だと都合がいい

# for j, k, s in product(range(N), range(1, N + 1), range(S + 1)):
#     dp[j + 1][k][s] = dp[j][k][s] + \
#         (0 if s - X[j] < 0 else dp[j][k - 1][s - X[j]])

# # s=k*Aとなるような通りの数の総数
# ans = 0
# for k in range(1, N + 1):  # 0個はとる通りの数はいらない
#     s = k * A
#     if s <= S:
#         ans += dp[N][k][s]

# # print(dp)
# print(ans)


'''
満点解法2
平均値の特性からXから差っ引けば、選んだカードの合計が0になれば良くなる。Y=X-Aと定義する。
→そしたらYからいくつか選んで合計tをつくる総数をdpで求めれば良い。(ナップザックDPとコインDPの中間！)

0枚以上選んだときに合計がtに成るかどうか考える

dp(j,t)...Y[:j]の中から0枚以上選んで、その合計を(t-NX)(負になる可能性もあるだけ)にするような選び方の総数
dp(j,t+NX)...Y[:j]の中から0枚以上選んで、その合計をtにするような選び方の総数 この定義のほうがいいかな

更新則
dp(j+1,t+NX) = Y[j]を選んで合計がtになる総和 + Y[j]を選ばずに合計がtになっている総和
つまり
dp(j+1,t+NX) = dp(j,t+NX - Y[j]) + dp(j,t+NX)

境界条件
dp(0,t+NX)=0  一つも考慮しない状態では必ずスコアは作れない
初期条件
dp(0,0+NX)=1 ∵ただし一つも考慮しないならば合計が0になるのは当然1通り
伝播条件
0<=t+NX-Y[j]<=2NXとなる範囲外の場合はdp(j,t+NX - Y[j])を無視 
'''

# 満点解法2
# NXは十分幅を取れていればなんでもいい
# NX = N * max(X) #今回は最低限の幅Sで代用
S = sum(X)

Y = []
for x in X:
    Y.append(x - A)
dp = [[0] * (2 * S + 1) for _ in range(N + 1)]

# 初期条件
dp[0][S] = 1

for j, t in product(range(N), range(-S, S + 1)):
    ts = t + S
    dp[j + 1][ts] = dp[j][ts]
    dp[j + 1][ts] += dp[j][ts - Y[j]] if 0 <= ts - Y[j] <= 2 * S else 0

print(dp[N][S] - 1)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc044/tasks/arc060_a
# ソートしてからごちゃごちゃやればどうにかなりそう(無理でした)

'''
解説満点解法1
もしもk枚選んだとき、合計がsになる通りの数がわかったら？→s=k*Aとなる場合の数の合計をすれば良い

k枚選んだとき、合計がsになる通りの数は典型的なDP！
dp(j,k,s)... X[0:j]からk枚選んで、その合計をsにするような選び方の総数
と定義すると、
dp(j+1,k,s) = X[j]を選んだ結果sになったときの通りの数 + X[j]を選ばずにsになっている通りの数 なので
dp(j+1,k,s) = dp(j,k-1,s-X[j]) + dp(j,k,s)

あとは初期条件と境界条件と伝播条件を付け加える。
境界条件 dp(j,k,0)=0 (数枚選んで合計が0になるのはありえない)
初期条件 dp(j,0,0)=1 (ただし、0枚選んだときは1通りとなる)(s-X[j]=0のときに1通りとなってほしいという気持ちもある)

伝播条件 s-X[j]<0に関しては dp(j-1,k-1,s-X[j])が必ず0通りとなる(ありえないので)
'''

import sys
read = sys.stdin.readline
from itertools import product


def read_ints():
    return list(map(int, read().split()))


N, A = read_ints()
X = read_ints()
S = sum(X)

# 満点解法1
dp = [[[0] * (S + 1) for _ in range(N + 1)] for _ in range(N + 1)]
for j in range(N + 1):  # 初期条件
    dp[j][0][0] = 1  # 1枚も選ばずに0になるのは1通り


for j, k, s in product(range(N), range(1, N + 1), range(S + 1)):
    dp[j + 1][k][s] = dp[j][k][s] + \
        (0 if s - X[j] < 0 else dp[j][k - 1][s - X[j]])

# s=k*Aとなるような通りの数の総数
ans = 0
for k in range(1, N + 1):  # 0個はとる通りの数はいらない
    s = k * A
    if s <= S:
        ans += dp[N][k][s]

# print(dp)
print(ans)


'''
満点解法2


'''

Submission status: Accepted

Solution code:
"""
kari1 = '4 8'
kari2 = '7 9 8 9' #5
#kari1 = '3 8'
#kari2 = '6 6 9' #0
#kari1 = '8 5'
#kari2 = '3 6 2 8 7 6 5 9' #19
#kari1 = '33 3'
#kari2 = '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' #8589934591
n, a = map(int, kari1.split())
x_a = list(map(lambda x: int(x) - a, kari2.split()))
"""
n, a = map(int, input().split())
x_a = list(map(lambda x: int(x) - a, input().split()))
dic = dict()
dic[0] = 1

for x in x_a:
    for key, value in list(dic.items()):
        dic[x + key] = value + dic.get(x + key, 0)

print(dic[0] - 1)

Submission status: Accepted

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

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

print(dp[n][n*X]-1)

Submission status: Accepted

Solution code:
from collections import Counter
n,a=map(int,input().split())
X=sorted(list(map(lambda x:int(x)-a,input().split())))
ans=Counter([0])
for x in X:
    tmp=Counter()
    for i,j in ans.items():
        tmp[i+x]+=j
    ans+=tmp
print(ans[0]-1)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,a=map(int,input().split())
x=[0]+list(map(int,input().split()))
su=sum(x)
maxi=max(x)
dp=[[[0 for k in range(maxi*n+1)] for j in range(51)] for i in range(51)]
dp[0][0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(maxi*j+1):
            if k<x[i]:
                dp[i][j][k]=dp[i-1][j][k]
            if k>=x[i] and j>=1:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-x[i]]
ans=0
for t in range(1,n+1):
    if a*t<=su:
        ans+=dp[n][t][a*t]
    else:
        break
print(ans)

Submission status: Accepted

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

m = a * n

# dp[i][j]: j 個使って合計がi
dp = [[0 for j in range(n+1)] for i in range(m+1)]
dp[0][0] = 1


for xk in x:
    # xkまで見たときを計算
    dpk = [dp[i][:] for i in range(m+1)]
    for i in range(m+1):
        if i - xk >= 0:
            for j in range(1,n+1):
                dpk[i][j] += dp[i-xk][j-1]
    dp = dpk

ans = 0

for i in range(1,m+1):
    for j in range(1,n+1):
        if i / j == a:
            ans += dp[i][j]

print(ans)

Submission status: Accepted

Solution code:
N,A=map(int,input().split())
l=list(map(int,input().split()))
d={}
def func(n,s,i):
	if n<0:
		return
	if (n,s,i) in d:
		return
	if n==0:
		if s==0:
			d[(n,s,i)]=1
		else:
			d[(n,s,i)]=0
		return
	if i>=N:
		if s==0 and n==0:
			d[(n,s,i)]=1
		else:
			d[(n,s,i)]=0

		return
	else:
		func(n-1,s-l[i],i+1)
		func(n,s,i+1)
		d[(n,s,i)]=d[(n-1,s-l[i],i+1)]+d[(n,s,i+1)]
ans=0
for j in range(1,N+1):
	func(j,j*A,0)
	ans+=d[(j,j*A,0)]
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

x.sort()
x = [i - a for i in x]
# print(x)
D = {0 : 1}
for i in x:
    for j, k in list(D.items()):
        D[i+j] = D.get(i+j, 0) + k

    # print(D)
print(D[0] - 1)

Submission status: Accepted

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

dp = [defaultdict(int) for _ in range(n+1)]
dp[0][a] += 1

for i, x_i in enumerate(x):
    for p in dp[i].keys():
        pk = p + a - x_i
        dp[i+1][pk] += dp[i][p]
        dp[i+1][p] += dp[i][p]

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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,A=MI()
    x=LI()
    M=max(x)
    
    #dp[i][j][k]はi番目まで，j枚で，和がkにできるか
    dp=[[[0]*(N*M+1) for j in range(N+1)] for _ in range(N+1)]
    dp[0][0][0]=1
    
    for i in range(N):
        for j in range(i+1):
            for k in range(N*M+1-x[i]):
                if dp[i][j][k]:
                    dp[i+1][j][k]+=dp[i][j][k]
                    dp[i+1][j+1][k+x[i]]+=dp[i][j][k]
                    

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

                
    
        
            
            
    
            
        
        
            

main()

Submission status: Accepted

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

dp = [defaultdict(int) for _ in range(n+1)]
dp[0][a] += 1

for i, x_i in enumerate(x):
    for p in dp[i].keys():
        # 入れる場合
        pk = p + a - x_i
        dp[i+1][pk] += dp[i][p]
        # 入れない場合
        dp[i+1][p] += dp[i][p]

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
N, A = map(int, input().split())
X = np.array(list(map(int, input().split())))
x = X - A
R = 5001
dp = np.zeros([N, R], np.int64)
dp[0][(R-1)//2] += 1
dp[0][(R-1)//2 + x[0]] += 1

for i in range(1,N):
	for j in range(R):
		if 0 <= j-x[i] <= R-1:
			dp[i][j] = dp[i-1][j] + dp[i-1][j-x[i]]
		else:
			dp[i][j] = dp[i-1][j]
print(dp[N-1][(R-1)//2]-1)

Submission status: Accepted

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

x.sort()
x = [i - A for i in x]
D = {0 : 1}
for i in x :
    for j, k in list(D.items()) :
        D[i+j] = D.get(i+j, 0) + k

print(D[0] - 1)

Submission status: Accepted

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

x.sort()
x = [v - A for v in x]

dp = [0] * 5001
for v in x:
    for i in range(2501) if v < 0 else range(5000, -1, -1):
        if dp[i] == 0:
            continue
        dp[i + v] += dp[i]
    dp[2500 + v] += 1
print(dp[2500])

Submission status: Accepted

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

OFS = N*xmax
dp = [[0]*(2*OFS+1) for _ in range(N)]
dp[0][OFS] += 1
dp[0][OFS+(X[0]-A)] += 1

for i in range(1, N):
  for s in range(2*OFS+1):
    t = s-(X[i]-A)
    if t < 0 or t > 2*OFS:
      dp[i][s] = dp[i-1][s]
    else:
      dp[i][s] = dp[i-1][s] + dp[i-1][t]

      
print(dp[N-1][OFS]-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,A = map(int,input().split())
a = list(map(int,input().split()))
a = [x-A for x in a]
B = A*n
dp = [[0]*B*2 for i in range(n+1)]
dp[0][B] = 1
for i in range(n):
    for j in range(B*2):
        dp[i+1][j] += dp[i][j]
        k = j+a[i]
        if k >=0 and k<B*2:
            dp[i+1][k] += dp[i][j]
print(dp[n][B]-1)

Submission status: Accepted

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

'''
辞書がめっちゃ書きやすい！ただし、3次元配列でdpやりたい時むずいかも。
x = [i-a for i in x]
dp = {0:1}
print(dp)
for item in x:
    print('--------for item:{}-----------'.format(item))
    for key, value in list(dp.items()):
        print('key:{},value:{}'.format(key,value))
        dp[item + key] = dp.get(item + key, 0) + value
        print(dp)
print(dp[0]-1)
'''

diff = [i-a for i in x]
ma = max(max(x),a)

dp = [[0 for j in range(2*n*ma+1)] for k in range(n+1)]
# 0を初期値として1からNまでやりたいので結果の箱は1+n回ループを回す準備をする。
# print(dp[1][71])
# この初期化をした時に添字はどっちがどっちみたいのはいい加減覚える。
# 0~2*n*naまでの列がn+1倍なのでそれがn+1個並んでいるイメージ。最初の添字ではn+1個並んでいるうちの一つを指定する。

dp[0][n*ma] = 1
# initialize

for l in range(0,n):
    # diff(入力の全てからaを引いたやつ)は0~n-1までしかないことに注意
    # 同様に後ろのdpの添字も注意
    for m in range(2*n*ma+1):
        if abs(m - diff[l]) > 2*n*ma:
            dp[l+1][m] = dp[l][m]
            #ループ回すまでもなく選んでも無理な時はそのまま 
        else:
            dp[l+1][m] = dp[l][m] + dp[l][m - diff[l]]
print(dp[n][n*ma]-1)



'''
countzero = len([i for i in diff if i == 0])
#print(countzero)
over = sorted([i for i in diff if i > 0])
under = sorted([i for i in diff if i < 0])
#print(over)
#print(under)
countover = [0 for i in range(50)]
countunder = [0 for i in range(50)]
for item in set(over):
    countover[item-1] = over.count(item)
for item in set(under):
    countunder[item] = under.count(item)
countunder = sorted(countunder)

valover = [countover[0]]
valunder = [countunder[0]]

for i in range(1,2500):
    plus = 0
    minus = 0
    if i%2 == 0:
        plus = countover[int(i/2)]*(countover[int(i/2)]-1)/2
        minus = countunder[int(i/2)]*(countunder[int(i/2)]-1)/2
    for j in range(int(i/2)):
        plus += countover[i]*countover[-i]
        minus += countunder[i]*countunder[-i]
    valover.append(plus)
    valunder.append(minus)

plusminus = 0
for i in range(2500):
    plusminus += valover[i]*valunder[i]

print((plusminus+1)*2**(countzero)-1)
'''

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7

N, A = MI()
X = LMI()

# dp[i][j][s] := i番目までのカードからj枚を選んで合計がsになる組み合わせの数
dp = [[[0] * 2502 for _ in range(N + 2)] for _ in range(N + 1)]
for i in range(N):
    dp[i][0][0] = 1
dp[0][1][X[0]] = 1
for i in range(1, N):
    for j in range(1, i + 2):
        for s in range(A * N + 1):
            if s - X[i] < 0:
                dp[i][j][s] = dp[i - 1][j][s]
            else:
                dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - X[i]]

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

Submission status: Accepted

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

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

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

for i in range(1, N + 1):
    for j in range(-2500, 2501):
        if 5000 >= j + 2500 - x[i - 1] >= 0:
            dp[i][j + 2500] = dp[i - 1][j + 2500 - x[i - 1]] + dp[i - 1][j + 2500]
        else:
            dp[i][j + 2500] = dp[i - 1][j + 2500]

print(dp[N][0 + 2500] - 1) # 何も選ばないものを引く

Submission status: Accepted

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

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

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

for i in range(1, N + 1):
    for j in range(-2500, 2501):
        if 5000 >= j + 2500 - x[i - 1] >= 0:
            dp[i][j + 2500] = dp[i - 1][j + 2500 - x[i - 1]] + dp[i - 1][j + 2500]
        else:
            dp[i][j + 2500] = dp[i - 1][j + 2500]

print(dp[N][0 + 2500] - 1)

Submission status: Accepted

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

Xp = [0]
Xm = [0]
Xz = 0
for x in X:
    if x-A > 0:
        Xp.append(x-A)
    elif x-A < 0:
        Xm.append(x-A)
    else:
        Xz += 1

DPp = [[0 for j in range(2501)] for i in range(len(Xp))]
DPm = [[0 for j in range(2501)] for i in range(len(Xm))]

DPp[0][0] = 1
DPm[0][0] = 1

for i in range(1,len(DPp)):
    x = Xp[i]
    for j in range(2501):
        if j >= x:
            DPp[i][j] = DPp[i-1][j] + DPp[i-1][j-x]
        else:
            DPp[i][j] = DPp[i-1][j]

for i in range(1,len(DPm)):
    x = -Xm[i]
    for j in range(2501):
        if j >= x:
            DPm[i][j] = DPm[i-1][j] + DPm[i-1][j-x]
        else:
            DPm[i][j] = DPm[i-1][j]

ans = 1

for j in range(1,2501):
    ans += DPp[len(DPp)-1][j]*DPm[len(DPm)-1][j]
ans = ans*pow(2,Xz) - 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def array(*args, initial=0):
    pre = "["*len(args)
    post = ""
    for a in args[::-1]:
        post += " for _ in range("+str(a)+")]"
    S = pre + str(initial) + post
    return eval(S)


def solve(N: int, A: int, x: "List[int]"):
    M = sum(x)
    # Nまで考慮, 使用した個数（Nまで）, 合計値
    DP = array(N+1, N+1, M+1)
    DP[0][0][0] = 1

    for i, a in enumerate(x, start=1):
        for j in range(N+1):
            for tot in range(M+1):
                DP[i][j][tot] = DP[i-1][j][tot]  # 使わない時
                if tot - a >= 0:                 # 使う時
                    DP[i][j][tot] += DP[i-1][j-1][tot-a]

    ans = 0
    for j in range(1, N+1):
        for tot in range(M+1):
            if tot / j == A:
                # if abs(tot / j-A) < 0.1:
                ans += DP[-1][j][tot]
    print(ans)
    # print(*DP[-1], sep="\n")
    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))  # 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: Accepted

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

dp = [[[0] * 3000 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):
            dp[i + 1][j + 1][k + x[i]] += dp[i][j][k]
            dp[i + 1][j][k] += dp[i][j][k]

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

print(ans)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
x = list(map(int, input().split()))
MAX_J = sum(x)
dp = [[0] * (MAX_J+1) for i in range(N+1)]
dp[0][0] = 1
for n in range(N):
    for i in range(N)[::-1]:
        for j in range(MAX_J-x[n]+1)[::-1]:
            dp[i+1][j+x[n]] += dp[i][j]
ans = 0
for i in range(1, N+1):
    if A * i <= MAX_J:
        ans += dp[i][A * i]
print(ans)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
dp = [[[0] * 3001 for i in range(51)] for j in range(51)]

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

for i in range(N):
  for j in range(N):
    for k in range(0, 2501):
      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: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,a = get_nums_l()
xxx = get_nums_l()

valMax = 2505

# dp[i][j][k] = i番目まで処理して、選択した個数がjで、合計がkのとき、平均aにできるパターン数
dp = [ [ [0]*valMax for __ in range(n+1) ] for _ in range(n+1) ]

for j in range(n+1):
    for k in range(valMax):
        dp[n][j][k] = 1 if k == j*a else 0

for i in range(n-1, -1, -1):
    for j in range(i+1):
        for k in range(valMax):
            no_pic = dp[i+1][j][k]
            pic = dp[i+1][j+1][k + xxx[i]] if k+xxx[i] < valMax else 0
            dp[i][j][k] = no_pic + pic
            # if no_pic+pic > 0:
                # log((i,j,k), no_pic, pic, no_pic+pic)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, A: int, x: "List[int]"):
    dp = [[0] * (A * N + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for xi in x:
        for k in reversed(range(1, N + 1)):
            for j in range(xi, A * N + 1):
                if j >= xi:
                    dp[k][j] += dp[k - 1][j - xi]
    print(sum(dp[i][A * i] for i in range(1, N + 1)))


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: Accepted

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

sm = sum(xx)
dp = [[0 for j in range(sm+1)] for i in range(n+1)]
dp[0][0] = 1
for x in xx:
    for i in range(1,n+1)[::-1]:
        for j in range(x,sm+1)[::-1]:
            # if dp[i-1][j-x]:
            dp[i][j] += dp[i-1][j-x]

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

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x_i = map(int, input().split())
list = list(i - a for i in x_i)
anslist = [[0 for i in range(5001)] for j in range(n + 1)]
anslist[0][2500] += 1
anslist[1][2500] += 1
anslist[1][list[0] + 2500] += 1
for id in range(n + 1):
    if id == 0 or id == 1: continue
    num = list[id - 1]
    for x in range(5001):
        anslist[id][x] += anslist[id - 1][x]
        if 0 <= x - num < 5001:
            anslist[id][x] += anslist[id - 1][x - num]
print(anslist[n][2500] - 1)

Submission status: Accepted

Solution code:
N,A=map(int,input().split())
x=list(map(int,input().split()))
ans=0
y=[0]*(len(x))
for k in range(len(x)):
    y[k]=x[k]-A
minus=0
plus=0
for k in range(N):
    if y[k]<0:
        minus-=y[k]
    if y[k]>0:
        plus+=y[k]
total=minus+plus+1
ans=[[0 for i in range(N)]for j in range(total)]
ans[y[0]+minus][0]=1
ans[minus][0]=ans[minus][0]+1
for j in range(N-1):
    for t in range(total):
        if 0<=t-y[j+1]<total:
            ans[t][j+1] =ans[t][j]+ans[t-y[j+1]][j]
        else:
            ans[t][j+1] =ans[t][j]
print(ans[minus][N-1]-1)

Submission status: Accepted

Solution code:
# C - 高橋君とカード
n,a=map(int,input().split())
x=list(map(int,input().split()))

max_num=max(n*a,sum(x))
dp=[[[0]*(max_num+1) for j in range(n+1)] for i in range(n+1)]
dp[0][0][0]=1
for i in range(n):
    for j in range(n):
        for k in range(max_num):
            if dp[i][j][k]:
                # not use
                dp[i+1][j][k] += dp[i][j][k]
                #  use
                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: Accepted

Solution code:
import numpy as np
N, A = map(int, input().split())
X = [int(c) for c in input().split()]
dp = np.zeros((51,51,2501))
dp[:,0,0] = 1
for i in range(1,N+1):
  c = X[i-1]
  for k in range(1,N+1):
    dp[i,k,:c] = dp[i-1,k,:c]
    dp[i,k,c:] = dp[i-1,k,c:]+dp[i-1,k-1,:2501-c]
ans = 0
for i in range(1,N+1):
  ans += dp[N,i,i*A]
print(int(ans))

Submission status: Accepted

Solution code:
from functools import lru_cache

N, A = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(lambda i: i - A, x))
X = max(max(x), A)

@lru_cache(maxsize=None)
def solve(j, t):
    global y
    if j == 0 and t == 0:
        return 1
    elif j >= 1 and (t < y[j - 1] - N * X or t > y[j - 1] + N * X):
        return solve(j - 1, t)
    elif j >= 1 and t >= y[j - 1] - N * X and t <= y[j - 1] + N * X:
        return solve(j - 1, t) + solve(j - 1, t - y[j - 1])
    else:
        return 0

print(solve(N, 0) - 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int, A: int, x: "List[int]"):
    ## dp[i][j][k] = i番目までのカードからjマイ選んで合計kにする選び方の総数
    dp = [[[0]*2501 for _ in range(N+1)] for _ in range(N+1)]

    for i in range(N):
        dp[i][0][0] = 1

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

    answer = 0
    for j in range(1,N+1):
        answer += dp[N][j][A*j]
    print(answer)
    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))  # 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: Accepted

Solution code:
from functools import lru_cache
N, A = map(int, input().split())
X = [int(x) for x in input().split()]
#with open("9", "w") as f:
#    print(50, 1, file=f)
#    print(*([1]*50), file=f)
assert len(X) == N
def solve0(i, n, s):
    if s < 0:
        return -1
    if N-i+1 < n:
        return -1
    if n == 0:
        if s == 0:
            return 1
        else:
            return -1
    if i == N:
        return -1
    s1 = solve(i+1, n-1,s-X[i])
    s2 = solve(i+1, n, s)
    if s1 == -1 and s2 == -1:
        return -1
    if s1 == -1:
        return s2
    if s2 == -1:
        return s1
    return s1 + s2

cache = {}
def solve(i, n, s):
    key = (i, n, s)
    a = cache.get(key, None)
    if a is None:
        a = solve0(i, n, s)
        cache[key] = a
    return a

answer = 0
for n in range(1, N+1):
    s = solve(0, n, n*A)
    if s != -1:
        answer += s
print(answer)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
dp = [[0]*2501 for _ in range(N+1)] # dp[n][k] := カードn枚で合計kにする選び方の数
dp[0][0] = 1

for i, x in enumerate(X):
  for n in range(i+1, 0, -1):
    for k in range(x, 2501):
      dp[n][k] += dp[n-1][k-x]

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

Submission status: Accepted

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

# 0~N枚 => N+1, 合計の最大値はN*50
dp = [[[0] * (N*50+50) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

# i枚目でk枚を選択、合計がk
for i in range(N) :
    for j in range(N) :
        for k in range(N*50):
            # 選択しない場合
            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):
    ans += dp[N][i][i*A]
    
print(ans)

Submission status: Accepted

Solution code:
N,A=map(int, input().split())
x=tuple(map(lambda i:int(i)-A,input().split()))
l=[0]*5001
l[0]=1
for i in x:
    f=l.copy()
    for j in range(-2500,2501):
        if l[j]:
            f[i+j]+=l[j]
    l=f.copy()
print(l[0]-1)