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

# i番目までからｊ枚選んで合計がｋ
dp = [[[0 for _ in range(50*N + 1)] for _ in range(N+1)] for _ in range(N+1)]
# 何も選ばず平均が０
dp[0][0][0] = 1

#全てのカードについてみる
#i-1番までからj-1枚選んで、j番目にiを選択したときの合計がA*jになるかどうか
for i in range(N+1):
    #i-1番目までからj-1枚選んであるので、最大でi-1枚選んである
    for j in range(i+1):
        # ｋは合計値
        for k in range(50*j + 1):
            # i番目を選んで合計がｋになるには、i番目の値がｋより小さくなければならない
            if i >= 1 and k < X[i-1]:
                # i番目がｋより大きいから、i-1番目までで合計がｋになる組の個数と同じ
                dp[i][j][k] = dp[i-1][j][k]
            # 
            elif i >= 1 and j >= 1 and k >= X[i-1]:
                #i番目を選んで合計がｋになるとき、ｋがi番目より大きい＆i-1からj-1枚選んだ時に合計がｋ－X[i-1]と、i-1番目まででできるやつ
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k - X[i-1]]

ans = 0
for i in range(1, N+1):
    #N枚からi枚選んで合計がi*A
    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()))
x.insert(0, 0)

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

for i in range(1, n+1):
    for j in range(0, n+1):
        for k in range(0, max(x)*n+1):
            if i == 0:
                pass
            else:
                if j == 0:
                    dp[i][j][k] = dp[i-1][j][k]
                else:
                    if k < x[i]:
                        dp[i][j][k] = dp[i-1][j][k]
                    else:
                        dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-x[i]] 
                        #print(x[i])

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


#for i in range(n+1):
#    print(dp[i])

Submission status: Accepted

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

dp=[[[0]*(N*xx+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*xx+1):
      if j==k==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:
        pass
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 = [int(_) - A for _ in input().split()]

dic = {0: 1}
#print(dic.items())

for x in X:
    for i, j in list(dic.items()):
        #print(i, j)
        #print(dic)
        dic[x + i] = dic.get(x+i, 0) + j
print(dic[0] - 1)

Submission status: Accepted

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

MAXSUM = sum(X)+5
dp = [[[0 for _ in range(MAXSUM)] for _ in range(N+5)] for _ in range(N+5)]
for i in range(N):
  dp[i+1][1][X[i]] += 1
  for k in range(N):
    for j in range(MAXSUM):
      dp[i+1][k][j] += dp[i][k][j]
      if X[i]+j < MAXSUM:
        dp[i+1][k+1][X[i]+j] += dp[i][k][j]
#print(dp)
ans = 0
for i in range(N):
  if A*(i+1) < MAXSUM:
    ans += dp[N][i+1][A*(i+1)]
print(ans)

Submission status: Accepted

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

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


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

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


# i番目までのカードが選べる時にj-1枚選んでありｊ枚目にiを選ぶとき合計がA*(j)になるかどうか
# dp[i][j][k] : j-1枚選んでいてiを次に選んだ時に合計がｋになる組の数
for i in range(N+1):
    for j in range(i+1):
        for k in range(50*j + 1):
            # カードを選択するが、i番目のカードを選んでも合計がkに一致しない
            if i >= 1 and k < X[i-1]:
                # i番目を使っても合計がｋにならないなら、i-1枚目までで作った時と同じ組の数
                dp[i][j][k] = dp[i-1][j][k]
            
            # i番目のカードをj枚目に選んで合計がｋになるものがある場合。
            # k >= X[i-1] がなんとなく直感と一致しない気もするが、ｋは０～枚数＊目標平均値の範囲の値をとるのでこれでいい
            elif i >= 1 and j >= 1 and k >= X[i-1]:
                # i-1番目までで合計がｋになる個数＋ｊ-1番目までの合計がｋ-X[i]
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k - X[i-1]]


ans = 0
# N枚目までからi枚選んだ時に平均がA（合計がA*i）になる個数をi=１～Nまで見る
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()))

Y = [x - A for x in X]

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

for m in range(1, N + 1):
    for s in range(-5000, 5001):
        if s + 5000 < 10000:
            dp[m][s + 5000] += dp[m - 1][s + 5000]
            if 0 <= s - Y[m - 1] + 5000 < 10000:
                dp[m][s + 5000] += dp[m - 1][s - Y[m - 1] + 5000]

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

Submission status: Accepted

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

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

for i,x in enumerate(X):
    for j in range(i,-1,-1):
        for k,v in dp[j].items():
            dp[j+1][k+x] += v

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, A = map(int, input().split())
    x = np.array(list(map(int, input().split())))
    x -= A
    MAX_ = max(1, max(x))

    dp = np.zeros((N+1, MAX_ * N * 2), dtype=int)
    dp[0][MAX_ * N] = 1

    for i in range(N):
        dp[i+1] += dp[i]
        if x[i] > 0:
            dp[i+1][x[i]:] += dp[i][:-x[i]]
        elif x[i] < 0:
            dp[i+1][:x[i]] += dp[i][-x[i]:]
        else:
            dp[i+1] += dp[i]
    
    print(dp[N][MAX_ * N] - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
	n,a=map(int,input().split())
	y=[a-int(x) for x in input().split()]
	dp={0:1}
	for i in y:
		for k,v in list(dp.items()):
			dp[i+k]=dp.get(i+k,0)+v
	print(dp[0]-1)
if __name__=="__main__":
	main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,a,*X=map(int,open(0).read().split())
y=[a-x for x in X]
dp={0:1}
for i in y:
	for k,v in set(dp.items()):
		dp[i+k]=dp.get(i+k,0)+v
print(dp[0]-1)

Submission status: Accepted

Solution code:
n,a,*x=map(int,open(0).read().split());dp={0:1}
for i in x:
	for k,v in set(dp.items()):
		dp[i+k-a]=dp.get(i+k-a,0)+v
print(dp[0]-1)

Submission status: Accepted

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

for j in range(1,N+1):
  for k in range(j+1):
    for s in range(X*N+1):
      dp[j][k][s] = dp[j-1][k][s]
      if s >= x[j-1]:
        dp[j][k][s] += dp[j-1][k-1][s-x[j-1]]
      
for i in range(N+1):
  ans += dp[-1][i][i*A]
  if (i+1)*A > X*N:
    break
print(ans-1)

Submission status: Accepted

Solution code:
N, A = tuple(map(int, input().split()))
X = list(map(lambda x: int(x) - A, input().split()))
D = {0:0}

for item in X:
  for k,v in list(D.items()):
    D[k+item]=D.get(k+item,0)+v
  D[item]=D.get(item,0)+1

print(D[0])

Submission status: Accepted

Solution code:
N,A=map(int,input().split())
x=list(map(int,input().split()))
cnt=x.count(A)
B=[]
for i in x:
  if i != A:
    B.append(i-A)
#print(cnt,B)

plus=[0]*2501
minus=[0]*2501

for i in B:
  if i>0:
    for j in range(2500,0,-1):
      if plus[j]>0 and j+i<=2500:
        plus[j+i]+=plus[j]
    plus[i]+=1
  if i<0:
    i=-i
    for j in range(2500,0,-1):
      if minus[j]>0 and j+i<=2500:
        minus[j+i]+=minus[j]
    minus[i]+=1

#print(plus[:100])
#print(minus[:100])
    
ans=0
for i in range(2501):
  ans+=plus[i]*minus[i] if plus[i]>0 and minus[i]>0 else 0
#print(ans)
ans*=2**cnt
ans+=2**cnt-1

print(ans)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())  # N枚のカード, 平均をAにしたい

X = tuple(map(int, input().split()))  # カードリスト

# [カードの総枚数][選んだカードの枚数][今の総和]
dp = [[[0]*(50*N+1) for _ in range(N+1)] for _ in range(N+1)]

# 0枚の中から0枚選んで総和が0になるパターンは1つ
dp[0][0][0] = 1

for i in range(N):
    for j in range(N+1):
        for k in range(N*50+1):
            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 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 = [int(i) for i in input().split()]

table = [[[0]*(N*A+1) for i in range(N+1)] for j in range(N+1)]
table[0][0][0] = 1

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

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
X = list(map(lambda x: x - A, X))
maxx = max(max(X), -min(X))
#前から(i + 1)個見て、和が(j - N * maxx)のもの
dp = [[0] * (2 * N * maxx + 1) for _ in range(N + 1)]
dp[0][N * maxx] = 1
for i in range(N):
  for j in range(2 * N * maxx + 1):
    if 0 <= j + X[i] <= 2 * N * maxx:
      dp[i + 1][j + X[i]] = dp[i][j] + dp[i][j + X[i]]
    else:
      dp[i + 1][j] = dp[i][j]
print(dp[N][N * maxx] - 1)
#print(dp)
#print(X)

Submission status: Accepted

Solution code:
# ABC044C - 高橋君とカード / Tak and Cards (ARC060C)
def main():
    N, A = tuple(map(int, input().split()))
    X = tuple(map(int, input().split()))
    # dp[i][j][k] := patterns to make k with j cards from X1, X2, ..., Xi
    dp = [[[0] * (N * 50 + 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(N * 50 + 1):
                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 = sum(dp[N][i][i * A] for i in range(1, N + 1))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC044C - 高橋君とカード / Tak and Cards (ARC060C)
from collections import defaultdict


def main():
    N, A = tuple(map(int, input().split()))
    X = tuple(map(lambda x: int(x) - A, input().split()))
    D = defaultdict(int)
    D[0] = 1
    for i in X:
        for j, k in list(D.items()):
            D[i + j] += k
    print(D[0] - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC044C - 高橋君とカード / Tak and Cards (ARC060C)
def main():
    N, A = tuple(map(int, input().split()))
    X = tuple(map(lambda x: int(x) - A, input().split()))
    D = {0: 1}
    for i in X:
        for j, k in list(D.items()):
            D[i + j] = D.get(i + j, 0) + k
    ans = D[0] - 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC044C - 高橋君とカード / Tak and Cards (ARC060C)
def main():
    N, A = tuple(map(int, input().split()))
    X = tuple(map(int, input().split()))
    # dp[i][j][k] := patterns to make k with j cards from X1, X2, ..., Xi
    dp = [[[0] * (N * 50 + 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(N * 50 + 1):
                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 = sum(dp[N][i][i * A] for i in range(1, N + 1))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC044C - 高橋君とカード / Tak and Cards (ARC060C)
def main():
    N, A = tuple(map(int, input().rstrip().split()))
    X = tuple(map(int, input().rstrip().split()))
    x = max(X)
    # dp[i][j][k] := patterns to make k by j cards from X1, X2, ..., Xi
    dp = [[[0] * (N * 50 + 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(N * 50 + 1):
                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 = sum(dp[N][i][i * A] for i in range(1, N + 1))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
dp = []
for i in range(n+1):
    dp.append([[] for j in range(i+1)])
    for k in range(i+1):
        dp[i][k] = [0 for y in range(50*k)]
for i in range(n+1):
        dp[i][0].append(0)
for i in range(1,n+1):
    for j in range(1,i+1):
        if j == 1:
                dp[i][j][x[i-1]-1] += 1
        for k in range(50*(j-1)):
                dp[i][j][k+x[i-1]] += dp[i-1][j-1][k]
                dp[i][j-1][k] += dp[i-1][j-1][k]
count = 0
for j in range(1,i+1):
        for k in range(len(dp[i][j])):
                if k + 1 == j*a:
                        count += dp[n][j][k]
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,A = inpl()
aa = inpl()

dp = [[[0]*(50*N+5) for j in range(N+1)] for i in range(N)]
# dp[i][j][k] : i 枚目まで見て，j枚選んで，合計がk の通り

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


for i in range(N):
    a = aa[i]
    for j in range(1,i+2):
        for k in range(50*j+5):
            dp[i][j][k] = dp[i-1][j][k]
            if k >= a:
                dp[i][j][k] += dp[i-1][j-1][k-a]

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

print(ans-1)

Submission status: Accepted

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

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

def bias(n):
    return n + 5000

dp[0][bias(0)] = 1

for i in range(N):
    for s in range(-5000, 5000):
        dp[i + 1][bias(s)] += dp[i][bias(s)]
        dp[i + 1][bias(s + Y[i])] += dp[i][bias(s)]

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

Submission status: Accepted

Solution code:
N,A=map(int,input().split())
X=list(map(int,input().split()))
dp=[[0]*5001 for _ in range(N+1)]
dp[0][2500]=1
for i in range(N):
    for j in range(5001):
        if dp[i][j]>0:
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j+X[i]-A]+=dp[i][j]
print(dp[N][2500]-1)

Submission status: Accepted

Solution code:

n, a = [ int(v) for v in input().split() ]
num_list = [ int(v) for v in input().split() ]
max_num = max(num_list)
field = [ [ 0 for i in range(5000) ] for i in range(n+1) ]
field[0][0] = 1

b = num_list[0]
for i in num_list:
    for j in range(n,0,-1):
        for k in range(5000):
            if k >= i:
                field[j][k] += field[j-1][k-i]



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

Submission status: Accepted

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

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

Submission status: Accepted

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

plus = []
minus = []
num_zero = 0
for i in range(N):
    xi_A = x[i] - A
    if xi_A > 0:
        plus.append(xi_A)
    elif xi_A < 0:
        minus.append(xi_A)
    else:
        num_zero += 1

dp_plus = [[0 for _ in range(2501)] for _ in range(len(plus) + 1)]
dp_minus = [[0 for _ in range(2501)] for _ in range(len(minus) + 1)]
dp_plus[0][0] = 1
dp_minus[0][0] = 1
for i in range(1, len(plus) + 1):
    for j in range(2501):
        dp_plus[i][j] += dp_plus[i-1][j]
        if j + plus[i-1] <= 2500:
            dp_plus[i][j + plus[i-1]] += dp_plus[i-1][j]
for i in range(1, len(minus) + 1):
    for j in range(2501):
        dp_minus[i][j] += dp_minus[i-1][j]
        if j - minus[i - 1] <= 2500:
            dp_minus[i][j - minus[i-1]] += dp_minus[i-1][j]

ans = 0
for i in range(2501):
    ans += dp_plus[-1][i] * dp_minus[-1][i] * (2 ** num_zero)
print(ans - 1)

Submission status: Accepted

Solution code:
# dp[j][k][s]: x_1...x_jのうちk枚選んで和をsにする選び方
# dp[j-1][k][s](x_jを選ばない) + dp[j-1][k-1][s-x_j](x_jを選ぶ)
# ans = sum(dp[j][k][k*A] j:1->N k:1->j)

import sys
write = sys.stdout.write

N, A = map(int,input().split())
x = list(map(int,input().split()))
x.insert(0,0)
ssize = N*A+1
jsize = N+1
dp = [[[0 for s in range(ssize)] for k in range(jsize)] for j in range(jsize)]
for j in range(jsize):
    for k in range(jsize):
        for s in range(ssize):
            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif j >= 1 and s - x[j] < 0:
                dp[j][k][s] = dp[j-1][k][s]
            elif j >= 1 and k >= 1 and s - x[j] >= 0:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j]]
            else:
                dp[j][k][s] = 0
sum = 0
for k in range(1, N+1):
    sum += dp[N][k][k*A]
print(str(sum))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(lambda x:int(x),input().split()))
memo=[[0 for _ in [0]*(50*i)] for i in range(1,N+1)]
for i in range(N):
    a=A[i]
    for j in range(i,0,-1):
        for k in range(50*j):
            memo[j][k+a]+=memo[j-1][k]
    memo[0][a-1]+=1
cnt=0
for i in range(N):
    cnt+=memo[i][(i+1)*K-1]
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros((N + 1, 2 * NX + 1), dtype=int)

dp[0][NX] = 1

for j in range(1, N + 1):
    y = X[j] - A
    for t in range(2 * NX + 1):
        if 0 <= t - y < 2 * NX:
            dp[j][t] = dp[j - 1][t] + dp[j - 1][t - y]
        else:
            dp[j][t] = dp[j - 1][t]

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

ma = max(X)

dp = [[[0 for s in range(ma*N+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(i+1) :
        for s in range(ma*N+1) :
            if (k >= 1) and (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) :
    if k*A > ma*N :
        break
    ans += dp[N][k][k*A]

print(ans)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
*X, = map(int, input().split())
MAX = max(max(X), A) * N
X = [x - A for x in X]

dp = {i: {j: 0 for j in range(2*MAX+1)} for i in range(N+1)}
dp[0][MAX] = 1
for i in range(1, N+1):
    for j in range(2*MAX+1):
        t = j - X[i-1]
        dp[i][j] = dp[i-1][j] + (dp[i-1][t] if 0 <= t <= 2*MAX else 0)
print(dp[N][MAX]-1)

Submission status: Accepted

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

# dp[i][k][j]
# i枚の中から、k枚選んで、和がj
dp = [[[0 for j in range(2501)]for k in range(n+1)] for i in range(n+1)]

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

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

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 = [int(a) for a in input().split()]
PO = [x-A for x in X if x > A]
NE = [A-x for x in X if x < A]
ZE = N - len(PO) - len(NE)

Y = [1] + [0] * 3000
Z = [1] + [0] * 3000

for i in PO:
    for j in range(2800)[::-1]:
        Y[i+j] += Y[j]
for i in NE:
    for j in range(2800)[::-1]:
        Z[i+j] += Z[j]

ans = -1
for i in range(len(Y)):
    ans += Y[i] * Z[i] * (2**ZE)
print(ans)

Submission status: Accepted

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

memo = {0:1}
for x in X:
    for k, v in list(memo.items()):
        memo[x + k] = memo.get(x + k, 0) + v

print(memo[0] - 1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
n, a = map(int, sys.stdin.readline().split())
x = list(map(int, sys.stdin.readline().split()))
dp = [[[0 for s in range(n*50 +1)] for k in range(n+1)] for j in range(n+1)]
from pprint import pprint
# pprint(dp)

for k in range(n+1):
    for s in range(n*50+1):
        dp[0][k][s] = 0

dp[0][0][0] = 1
for j in range(1,n+1):
    for k in range(n+1):
        for s in range(n*50+1):
            # print(j, k, s)
            if 1 <= j and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif 1 <= j and 1 <= k and x[j-1] <= s:
                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 k in range(1,n+1):
    sum += dp[n][k][k*a]
print(sum)

Submission status: Accepted

Solution code:
from collections import defaultdict
import copy
x=[]
d=defaultdict(int)
n,a=map(int,input().split())
dp=[[0]*n*51 for _ in range(n)]
for i in input().split():
    x.append(int(i)-a)
for i in x:
    tmp=copy.copy(d)
    for j in tmp:
        d[j+i]+=tmp[j]
    d[i]+=1
ans=d[0]
print(ans)

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
X=[int(i) for i in input().split()]
DP=[[[0 for i in range(50*n+1)] for i 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(i+1):
    for s in range(50*j+1):
      DP[i][j][s]=DP[i-1][j][s]+DP[i-1][j-1][s-X[i-1]]
ans=0
for j in range(1,n+1):
  ans+=DP[n][j][j*a]
print(ans)

Submission status: Accepted

Solution code:
n, a =map(int, input().split())
x=list(map(int, input().split()))
x=[i-a for i in x]
memo=[[-1]*6000 for i in range(60)]
def dp(k, value):
    if k==n:
        if value==0:
            return 1
        else:
            return 0
    if memo[k][value]>=0:
        return memo[k][value]
    memo[k][value]=dp(k+1, value+x[k])+dp(k+1, value)
    return memo[k][value]
print(dp(0, 0)-1)

Submission status: Accepted

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

Submission status: Accepted

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


def make_matrix():
    dp = [
        [
            [0] * ((n + 1) * max(max(xlist), a)) for _ in range(n + 1)
        ] for _ in range(n + 1)
    ]



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

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

#   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

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

    for j in range(n + 1):
        for k in range(n + 1):
            for s in range((n + 1) * max(xlist)):
                if 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]]

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

    print(int(methods))


if __name__ == '__main__':
    submit()

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


def full(shape, value):
    if not shape:
        return value
    return [full(shape[1:], value) for _ in range(shape[0])]

minus_cnt = 0
plus_cnt = 0
for v in x:
    if v < 0:
        minus_cnt -= v
    elif v > 0:
        plus_cnt += v

dp = full((n + 1, minus_cnt + plus_cnt + 5, n + 1), None)
def dfs(k, s=0, depth=n - 1): # ret -> pattern count
    if dp[k][s][depth] is not None:
        return dp[k][s][depth]
    if k == 0:
        if s == 0:
            result = 1
        else:
            result = 0
        dp[k][s][depth] = result
        return result
    if depth == -1:
        dp[k][s][depth] = 0
        return 0
    result = dfs(k - 1, s + x[depth], depth - 1) + dfs(k, s, depth - 1)
    dp[k][s][depth] = result
    return result

result = 0
for i in range(1, n + 1):
    result += dfs(i)
print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
X=list(map(int,input().split()))
m=max(X)
Y=map(lambda x:x-a,X)
DP=[[0]*(2*m*n+1) for _ in range(n+1)]
DP[0][m*n]=1
for i,y in enumerate(Y):
    for j in range(2*m*n+1):
        DP[i+1][j]=DP[i][j]
        if 0<=j-y<=2*m*n:
            DP[i+1][j]+=DP[i][j-y]
print(DP[n][m*n]-1)

Submission status: Accepted

Solution code:
n,a=map(int, input().split())
x=list(map(int, input().split()))
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)
#sample code.

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x=list(map(lambda x: int(x)-a, input().split()))
k=[[0]*3000 for i in range(60)]
for i in range(3000):
    k[0][i]=0
k[0][x[0]+1500]+=1
k[0][1500]+=1
for i in range(1, n):
    for j in range(3000):
        if 3000>j-x[i]>=0:
            k[i][j]=k[i-1][j-x[i]]+k[i-1][j]
        else:
            k[i][j]=k[i-1][j]
print(k[n-1][1500]-1)

Submission status: Accepted

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

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

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

for i in range(1,n+1): #x_1,x_2...x_n
  for k in range(i):   #k枚数選ぶ
    for s in range(sum(X)+1): #合計
      if dp[i-1][k][s]:
        dp[i][k+1][s+X[i-1]]+=dp[i-1][k][s] #1枚選択肢が増えた時の、そのカードを加えた結果を加算
        dp[i][k][s]+=dp[i-1][k][s]
ans=0
for i in range(1,n+1):
  for j in range(1,sum(X)+1):
    if j == i*a: #合計が平均のi倍の時に加える
      ans+=dp[n][i][j]

print(ans)

Submission status: Accepted

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

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

for i in range(1,n+1): #x_1,x_2...x_n
  for k in range(i):   #k枚数選ぶ
    for j in range(sum(X)+1): #合計
      if dp[i-1][k][j]:
        dp[i][k+1][j+X[i-1]]+=dp[i-1][k][j]
        dp[i][k][j]+=dp[i-1][k][j]
ans=0
for i in range(1,n+1):
  for j in range(1,sum(X)+1):
    if j==i*a:
      ans+=dp[n][i][j]
print(ans)

Submission status: Accepted

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

d = {0:1}  

for x in X:
    d_tmp = d.copy()
    for k in d_tmp:        
        d[k+x] = d.get(k+x,0)+d_tmp[k]
print(d[0]-1)

Submission status: Accepted

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

z = 0 
dic = {}

for x in X:
    if x==0:
        z += 1
    else:
        dic[x] = dic.get(x,0) + 1
            
line = {}
line[0] = 1

for k in dic:    
    line_k = {}
    for i in range(dic[k]+1):
        line_k[k*i] = 1      
        for j in range(dic[k],dic[k]-i,-1):
            line_k[k*i] *= j
        for j in range(1,1+i):
            line_k[k*i] //= j
    line_tmp = {}
    for k_lk in line_k:
        for k_l in line:
            line_tmp[k_lk+k_l] = line_tmp.get(k_lk+k_l,0) + line_k[k_lk] * line[k_l]
    line = line_tmp.copy()
    
print(line[0] * (2**z) -1)

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
X = [0]+list(map(int,input().split()))
dp = []
for i in range(N+1):
  K = []
  for j in range(N+1):
    J = [0]*(N*max(X)+1)
    K.append(J)
  dp.append(K)
for j in range(N+1):
  for k in range(N+1):
    for s in range(N*max(X)+1):
      if j >= 1:
        if s < X[j]:
          dp[j][k][s] = dp[j-1][k][s]
        elif s >= X[j] and k >= 1:
          dp[j][k][s] = dp[j-1][k][s]+dp[j-1][k-1][s-X[j]]
        else:
          dp[j][k][s] = 0
      else:
        if k == 0 and s == 0:
          dp[j][k][s] = 1
        else:
          dp[j][k][s] = 0
ans = 0
for i in range(1,N+1):
  if i*A <= N*max(X):
    ans += dp[N][i][i*A]
print(ans)

Submission status: Accepted

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

L = [[0 for i in range(10002)] for j in range(N)]
for i in range(N):
	L[i][5001 + x[i]] = 1

for i in range(N - 1):
	for j in range(10002):
		if L[i][j] != 0:
			L[i + 1][j] += L[i][j]
			L[i + 1][j + x[i + 1]] += L[i][j]

print(L[N - 1][5001])