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 = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]

nx = n * max(max(x), a)
y = [xi - a for xi in x]
dp = [[0 for j in range(2 * nx + 1)] for i in range(n + 1)]
dp[0][nx] = 1

for i in range(n):
    for j in range(2 * nx + 1):
        if j - y[i] > 2 * nx:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = dp[i][j] + dp[i][j - y[i]]

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

Submission status: Accepted

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

nx = n * max(max(x), a)
y = [xi - a for xi in x]
dp = [[0 for j in range(2 * nx + 1)] for i in range(n + 1)]
dp[0][nx] = 1

for i in range(n):
    for j in range(2 * nx + 1):
        if not 0 <= j - y[i] <= 2 * nx:
            dp[i + 1][j] = dp[i][j]
        elif j - y[i] <= 2 * nx:
            dp[i + 1][j] = dp[i][j] + dp[i][j - y[i]]

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

Submission status: Accepted

Solution code:
import collections

n, a = map(int, input().split())
X = [int(i) - a for i in input().split()]
ans = 0
sums = collections.Counter([0, X[0]])
for i in X[1:]:
    sums2 = collections.Counter()
    for s, c in sums.items():
        sums2[s + i] += c
    sums += sums2
print(sums[0] - 1)

Submission status: Accepted

Solution code:
from collections import Counter

n,a = map(int,input().split())
input_list = [int(num)-a for num in input().split()]

ans = Counter([0,input_list[0]])
for i in input_list[1:]:
    temp = Counter()
    for key,value in ans.items():
        temp[i+key] += value
    ans += temp

print (ans[0]-1)

Submission status: Accepted

Solution code:
from collections import Counter

N, A = map(int, input().split())
input_list = [int(i) - A for i in input().split()]

ans = Counter([0, input_list[0]])

for i in input_list[1:]:
    temp = Counter()
    for key, value in ans.items():
        temp[i + key] += value
    ans += temp

print(ans[0] - 1)

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(lambda q: int(q) - a, input().split()))
X = max(max(x), a)
N = 2 * n * X
dp = [[0] * (N + 1) for i in range(n + 1)]
dp[0][n * X] = 1
for i in range(1, n + 1):
    for j in range(N + 1):
        if j - x[i - 1] < 0 or j - x[i - 1] > N:
            dp[i][j] = dp[i - 1][j]
        elif j - x[i - 1] <= N:
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - x[i - 1]]

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

Submission status: Accepted

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

Submission status: Accepted

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

from collections import Counter

total = Counter([0])
for x in X:
    mix = Counter()
    for i, cnt in total.items():
        mix[i + x] += cnt
    total += mix

print(total[0] - 1)

Submission status: Accepted

Solution code:
from collections import Counter
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
C = Counter([0])
for x in X:
  tmp = Counter()
  for i, c in C.items():
    tmp[i + x] += c
  C += tmp
print(C[0] - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

dp = [defaultdict(int) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for j in range(-N * X, N * X + 1):
        dp[i + 1][j] = dp[i][j] + dp[i][j - x[i]]
print(dp[N][0] - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

dp = [defaultdict(int) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for j in range(-N * X, N * X + 1):
        if - N * X <= j - x[i] <= N * X:
            dp[i + 1][j] = dp[i][j] + dp[i][j - x[i]]
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[N][0] - 1)

Submission status: Accepted

Solution code:
from collections import Counter

n,a = map(int, input().split())
x = [int(i) - a for i in input().split()] # 合計を0にする

total = Counter([0])

for i in x:
    tmp = Counter()
    for j, cnt in total.items():
        tmp[i+j] += cnt
    total += tmp # 各合計値のカウントを積む

print(total[0] - 1)
exit(0)

Submission status: Accepted

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

import functools
@functools.lru_cache(maxsize=None)
def f(acc, left):
    if not left: return 0
    ret = 0
    y = acc + left[0]
    ret += 1 if y == 0 else 0
    ret += f(y, left[1:])
    ret += f(acc, left[1:])
    return ret
print(f(0, tuple(X)))

Submission status: Accepted

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

""" 2次元DP """

N,A = map(int, input().split())
xN = list(map(int, input().split()))
X = max(max(xN), A)
# 全てのxから-Aすることで、合計=0,平均=0を求める形にする
yN = [int(i)-A for i in xN]

# 二つ目の添え字はマイナスを取りうるので工夫する
dp = [[0] * (2*N*X+1) for j in range(N+1)]
# 基準点を0じゃなくて真ん中(N*X)にする
dp[0][N*X] = 1

ans = 0
for i in range(1,N+1):
    for t in range(2*N*X+1):
        # 範囲外ならそのまま
        if t - yN[i-1] < 0 or t - yN[i-1] > 2*N*X:
            dp[i][t] = dp[i-1][t]
        # 範囲内なら前の値を足す
        elif 0 <= t - yN[i-1] <= 2*N*X:
            dp[i][t] = dp[i-1][t] + dp[i-1][t - yN[i-1]]
# 1枚も選ばないパターンを引く
print(dp[N][N*X]-1)

Submission status: Accepted

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

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

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

const = 50*n
dp[0][const] = 1


for i in range(n):
    for j in range(100*n + 1):
        dp[i+1][j] = dp[i][j]
        if j - y[i] >= 0 and j - y[i] <= 100*n:
            dp[i+1][j] += dp[i][j - y[i]]

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

Submission status: Accepted

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


N,A = inpl()
xx = inpl()

pos_numbers = []
neg_numbers = []
Zero = 0

for x in xx:
	tmp = x - A
	if tmp < 0:
		neg_numbers.append(-tmp)
	elif tmp == 0:
		Zero += 1
	else:
		pos_numbers.append(tmp)

pos_sum = set([0])
pos_dd = defaultdict(int)
pos_dd[0] = 1
for n in pos_numbers:
	tmp_set = set()
	tmp_list = list(pos_sum)
	tmp_list.sort(reverse=True)
	for s in tmp_list:
		tmp_set.add(s+n)
		pos_dd[s+n] += pos_dd[s]
	pos_sum = pos_sum | tmp_set


neg_sum = set([0])
neg_dd = defaultdict(int)
neg_dd[0] = 1
for n in neg_numbers:
	tmp_set = set()
	tmp_list = list(neg_sum)
	tmp_list.sort(reverse=True)
	for s in tmp_list:
		tmp_set.add(s+n)
		neg_dd[s+n] += neg_dd[s]
	neg_sum = neg_sum | tmp_set

ans = 0
for n in pos_sum:
	ans += pos_dd[n]*neg_dd[n]

ans *= 2**Zero
print(ans-1)

Submission status: Accepted

Solution code:
from collections import Counter

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

dp = [Counter()]
# [何個使ったか][sum]
dp[0][0] = 1
for i,j in enumerate(x):
	dp.append(Counter())
	for k in reversed(range(i+1)):
		for m,p in dp[k].items():
			dp[k+1][m+j] += p

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

Submission status: Accepted

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

dp = [Counter() for i in range(N+1)]
dp[0][0] = 1
for i,a in enumerate(src):
    for j in reversed(range(i+1)):
        for k,v in dp[j].items():
            dp[j+1][k+a] += v
ans = 0
for i,ctr in enumerate(dp):
    if i==0: continue
    ans += ctr[i*A]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

l = [ai - a for ai in l]

cnt = Counter([0, l[0]])

for li in l[1:]:
    tmp = Counter([])
    for k,v in cnt.items():
        tmp[k+li] += v
        
    cnt += tmp
    
print(cnt[0]-1)

Submission status: Accepted

Solution code:
from collections import Counter

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

dp = [Counter()]
# [何個使ったか][sum]
dp[0][0] = 1
for i,j in enumerate(x):
	dp.append(Counter())
	for k in reversed(range(i+1)):
		for m,n in dp[k].items():
			dp[k+1][m+j] += n

res = 0
for l in dp:
	res += l[0]
print(res-1)

Submission status: Accepted

Solution code:
n,a = map(int, input().split())
x = list(map(int, input().split()))
y = max(x)
x = [z-a for z in x]

dp = [[0]*(2*n*y+1) for _ in range(n+1)]
dp[0][n*y] = 1
for k in range(n):
    for i in range(2*n*y+1):
        res = dp[k][i]
        if i+x[k] < 0 or i+x[k] > 2*n*y:
            pass
        else:
            res += dp[k][i+x[k]]
        dp[k+1][i] = res
print(dp[-1][n*y]-1)

Submission status: Accepted

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

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

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

print(s)

Submission status: Accepted

Solution code:
def ary2(x, y, v): return [[v for _  in range(y)] for _ in range(x)]

n, a = map(int, input().split())
x = list(map(int, input().split()))
m = max(x)
dp = ary2(n + 1, n + 1, False)#(選べる枚数（範囲）0 ~ n, 選んだ枚数0 ~ n = 合計0 ~ n * max(x) : パターン数 の辞書

for i in range(n + 1):
    for j in range(n + 1):
        if j == 0:
            dp[i][j] = {0:1}
        else:
            dp[i][j] = dict()

for i in range(1, n + 1):
    for j in range(1, i + 1):
        for s in dp[i - 1][j - 1].keys():
            dp[i][j][s + x[i - 1]] = dp[i][j].get(s + x[i - 1], 0) + dp[i - 1][j - 1].get(s, 0)
        for s in dp[i - 1][j].keys():
            dp[i][j][s] = dp[i][j].get(s, 0) + dp[i - 1][j].get(s, 0)

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

print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache

N, A = map(int, input().split())
X = tuple(int(x) for x in input().split())

# 平均を出すのに選んだ個数が必要
@lru_cache(maxsize=None)
def rec(i, a, k):
    """
    :param i: int
        数列の長さ
    :param a: int
        総和
    :param k: int
        選ぶ個数
    :return: int
        通り数
        Number of patterns
    """
    if k == 0:
        if a == 0:
            return 1
        else:
            return 0

    ret = 0
    if i - 1 >= k:
        ret = rec(i - 1, a, k)
    if X[i - 1] <= a and i - 1 >= k - 1:
        ret += rec(i - 1, a - X[i - 1], k - 1)
    return ret


i = len(X)
m = (rec(i, k * A, k) for k in range(1, N + 1))
print(sum(m))

Submission status: Accepted

Solution code:
from functools import lru_cache

N, A = map(int, input().split())
X = tuple(int(x) for x in input().split())

# 平均を出すのに選んだ個数が必要
@lru_cache(maxsize=None)
def rec(i, a, k):
    """
    :param i: int 
        数列の長さ
    :param a: int
        総和
    :param k: int
        選ぶ個数
    :return: int
        通り数
        Number of patterns
    """
    if k == 0:
        if a == 0:
            return 1
        else:
            return 0

    if a < 0 or i < k:
        return 0

    ret = rec(i - 1, a, k)
    ret += rec(i - 1, a - X[i - 1], k - 1)
    return ret

i = len(X)
m = (rec(i, k * A, k) for k in range(1, N + 1))
print(sum(m))

Submission status: Accepted

Solution code:
def na(): return map(int, input().split())
n, a = na()
x = list(na())
xa = list(map(lambda f: f-a, x))
'''
dp[i][点数] = パターン数
i番目まで使用したときの点数になるパターン数
'''
dp = [dict() for _ in range(n)]
if xa[0] == 0:
    dp[0][0] = 2
else:
    dp[0][0] = 1
    dp[0][xa[0]] = 1
for i in range(1, n):
    #xa[i]を採用する / 採用しないで2つに分岐
    #すべて採用しないと点数0になるので、最後に点数0になったパターン数から1引く
    for k, v in dp[i-1].items():#k:得点, v:パターン数
        score = xa[i] + k
        dp[i][score] = dp[i].get(score, 0) + v#xa[i]を採用
        dp[i][k] = dp[i].get(k, 0) + v#xa[i]を不採用
print(dp[n-1][0] - 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Aug  5 12:20:16 2018
ABC44C
@author: maezawa
"""

def f(i, j):
    global xa
    global dp
    if i==0:
        cnt = 0
        if j==0:
            cnt += 1
        if j==xa[0]:
            cnt += 1
        return cnt
    if (i, j) in dp:
        return dp[(i,j)]
    else:
        dp[(i,j)] = f(i-1,j-xa[i]) + f(i-1,j)
        #print(i,j, dp[(i,j)])
        return dp[(i,j)]


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

xa = [x[i]-a for i in range(n)]
dp = dict([])

print(f(n-1, 0)-1)

Submission status: Accepted

Solution code:
from collections import Counter

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

cnt = Counter([0, X[0]])

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

Submission status: Accepted

Solution code:
from itertools import product

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

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

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

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

Submission status: Accepted

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

m = {}
def f(rv, k, rest):
    if k == 0:
        if rv == 0:
            return 1
        else:
            return 0
    if rv < 0 or len(rest) < k:
        return 0
    
    def r(rv, k, rest):
        fp = (rv, k, len(rest))
        if fp in m: return m[fp]
        ret = f(rv, k, rest)
        m[fp] = ret
        return ret
    ans  = r(rv          , k    , rest[1:])
    ans += r(rv - rest[0], k - 1, rest[1:])
    return ans

print(sum([f(k * A, k, sorted(X)) for k in range(1, N + 1)]))

Submission status: Accepted

Solution code:
from itertools import product

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

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

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

Submission status: Accepted

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

m = {}
def f(cv, cur, rest):
    tgt = A * len(cur)
    if len(rest) == 0:
        if cv == tgt and cv != 0:
            return 1
        else:
            return 0
    if cv > tgt and rest[0] > A:
        return 0
    
    ans = 0
    
    cc = cur.copy()
    r = rest[1:]
    sig = (cv, len(cc), tuple(r))
    if sig in m:
        ans += m[sig]
    else:
        ret = f(cv, cc, r)
        m[sig] = ret
        ans += ret

    cc.append(rest[0])
    cv += rest[0]
    sig = (cv, len(cc), tuple(r))
    if sig in m:
        ans += m[sig]
    else:
        ret = f(cv, cc, r)
        m[sig] = ret
        ans += ret
    return ans

print(f(0, [], sorted(X)))

Submission status: Accepted

Solution code:
from collections import Counter

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

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

sums = Counter([0, X[0]])

for x in X[1:]:
    c = Counter()
    for k,v in sums.items():
        c[x+k] = v
    sums += c
    
print(sums[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 for _ in range(100*N+1)] for _ in range(N+1)]
dp[0][50*N] = 1

for i in range(1,N+1):
    for summ in range(2*50*N+1):
        if 0 <= summ-X[i-1] <= 100*N:
            dp[i][summ] = dp[i-1][summ] + dp[i-1][summ-X[i-1]]
        else:
            dp[i][summ] = dp[i-1][summ]
            
print(dp[N][50*N]-1)

Submission status: Accepted

Solution code:
from collections import Counter

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

for i in range(N):
    X[i] -= A
    
sums = Counter([0,X[0]])

for i in range(1,N):
    ith_x = X[i]
    ith_hash = {}
    for key, value in sums.items():
        ith_hash[ith_x + key] = value
        
    sums += ith_hash
    
print(sums[0]-1)

Submission status: Accepted

Solution code:
import collections

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

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

sums = collections.Counter([0,X[0]])

for i in X[1:]:
    c = collections.Counter()
    for p,q in sums.items():
        c[i+p] = q
    sums += c

print(sums[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=[[None for i in range(2*n*X+1)] for h in range(n+1)]
for j in range(n+1):
    for t in range(2*n*X+1):
            if j==0 and t==n*X:
                dp[j][t]=1
            elif j>=1 and (t-y[j-1]<0 or t-y[j-1]>2*n*X):
                dp[j][t]=dp[j-1][t]
            elif j>=1 and t-y[j-1]>=0 and t-y[j-1]<=2*n*X:
                dp[j][t]=dp[j-1][t]+dp[j-1][t-y[j-1]]
            else:
                dp[j][t]=0
                
print(dp[n][n*X]-1)

Submission status: Accepted

Solution code:
n, a = list(map(int, input().split()))
x = list(map(int, input().split()))
max_x = max(max(x), a)
x = [-10**6] + [xx-a for xx in x]
dp = [[0]*(2*n*max_x+1) for _ in range(n+1)]
dp[0][n*max_x] = 1

# import numpy as np
# print(np.shape(dp))

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

# print(np.array(dp))
print(dp[n][n*max_x]-1)

Submission status: Accepted

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

max_x = max(X)
Y = []
for x in X:
    Y.append(x - A)

dp=[[0 for t in range(60*60*2)] for j in range(60)]
#dp[j番目までの変数から0枚以上選んでy_iの合計を][t-NXにする] = 総数

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



# dp=[[[0 for s in range(60*60)] for k in range(60)] for j in range(60)]
# for s in range(60*60):
#     dp[0][0][s]=0
# #dp[j番目までの変数から][k個選んで][合計がs] = になる総数
# for j in range(N+1):
#     for k in range(N+1):
#         for s in range(N*k+1):
#             if j == 0 and k == 0 and s == 0:
#                 dp[j][k][s] = 1
#             else:
#                 if j >= 1 and s < X[j-1]:
#                     dp[j][k][s] = dp[j-1][k][s]
#                 elif j >= 1 and  k >= 1 and s>=X[j-1]:
#                     dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-X[j-1]]
#                 else:
#                     dp[j][k][s] = 0

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

# import itertools
# N,A = map(int, input().split())
# X = map(int,input().split())

# ans = 0
# X = sorted(X)
# for n in range(1,N+1):
#     tmp = []
#     tmp = list(itertools.combinations(X,n))
#     tmp_sum = []

#     for i in range(len(tmp)):
#         tmp_sum.append(sum(tmp[i]))
#     ans += tmp_sum.count(A*n)
#     if tmp_sum[0] > A*n:
#         break

# print(ans)

Submission status: Accepted

Solution code:
n,a = map(int,raw_input().split())

arr = map(int,raw_input().split())
arry = []

for i in range(n):
	arry.append(arr[i]-a)


dp = [[0 for i in range((n)*50*2)] for j in range(n+1)]
dp[0][n*50] = 1

for i in range(n):
	for j in range(n*50*2):
		if 0 <= j-arry[i] and j-arry[i] < n*50*2 :
			dp[i+1][j] = dp[i][j]+dp[i][j-arry[i]]
		else :
			dp[i+1][j] = dp[i][j]

print dp[n][n*50]-1

Submission status: Accepted

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

max_x = max(x+[a])

y = [0]
for x in x:
    y.append(x-a)

dp = [[0]*(2*n*max_x+1) for i in range(n+1)]
dp[0][n+max_x] = 1

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

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

Submission status: Accepted

Solution code:
from collections import Counter

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

dp = [Counter({0:1})]

for i,a in enumerate(src):
    dp.append(Counter())
    for j in reversed(range(i+1)):
        for k,v in dp[j].items():
            dp[j+1][k+a] += v

ans = 0
for i,ctr in enumerate(dp):
    if i==0: continue
    ans += ctr[i*A]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
N, A = map(int, raw_input().split())
x = map(int, raw_input().split())

ADD = 10000
DP = [0 for i in range(N * 50 + 1 + 2 * ADD)]
 
DP[ADD] = 1

for i in range(N):
    if x[i] < A:
        for j in range(-N * 60, N * 60):
            DP[j + ADD] += DP[j + (A - x[i]) + ADD]
    else:
        for j in range(N * 60, -N * 60, -1):
            DP[j + ADD] += DP[j + (A - x[i]) + ADD]

print DP[ADD] - 1

Submission status: Accepted

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

  """
  #dp[i][j][k] ... iまででj個使ってkを作る
  #dp[i][j][k] += dp[i - 1][j - 1][k - x]
  
  xlst.insert(0, 0)
  dp =  [[[0] * (50 * n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
  for i in range(n + 1):
    dp[i][0][0] = 1
  
  
  for i in range(1, n + 1):
    x = xlst[i]
    dpi = dp[i]
    dpi_1 = dp[i - 1]
    for j in range(1, n + 1):
      dpij = dpi[j]
      dpi_1j = dpi_1[j]
      dpi_1j_1 = dpi_1[j - 1]
      for k in range(1, n * 50 + 1):
        if k >= x:
          #dp[i][j][k] += dp[i - 1][j - 1][k - x] + dp[i - 1][j][k]
          dpij[k] += dpi_1j_1[k - x] + dpi_1j[k]
        else:
          #dp[i][j][k] += dp[i - 1][j][k]
          dpij[k] += dpi_1j[k]

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

  """

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

  for x in xlst:
    for j in range(n, 0, -1):
      dpj = dp[j]
      dpj1 = dp[j - 1]
      for k in range(x, n * 50 + 1):
        dpj[k] += dpj1[k - x]

  print(sum([dp[j][j * a] for j in range(1, n + 1)]))
main()

Submission status: Accepted

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

  """
  dp[i][j][k] ... iまででj個使ってkを作る
  dp[i][j][k] += dp[i - 1][j - 1][k - x]
  """
  
  """
  xlst.insert(0, 0)
  dp =  [[[0] * (50 * n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
  for i in range(n + 1):
    dp[i][0][0] = 1
  
  
  for i in range(1, n + 1):
    x = xlst[i]
    dpi = dp[i]
    dpi_1 = dp[i - 1]
    for j in range(1, n + 1):
      dpij = dpi[j]
      dpi_1j = dpi_1[j]
      dpi_1j_1 = dpi_1[j - 1]
      for k in range(1, n * 50 + 1):
        if k >= x:
          #dp[i][j][k] += dp[i - 1][j - 1][k - x] + dp[i - 1][j][k]
          dpij[k] += dpi_1j_1[k - x] + dpi_1j[k]
        else:
          #dp[i][j][k] += dp[i - 1][j][k]
          dpij[k] += dpi_1j[k]

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

  """

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

  for x in xlst:
    for j in range(n, 0, -1):
      dpj = dp[j]
      dpj1 = dp[j - 1]
      for k in range(n * 50, x - 1, -1):
        dpj[k] += dpj1[k - x]

  print(sum([dp[j][j * a] for j in range(1, n + 1)]))
main()

Submission status: Accepted

Solution code:
def main():
  n, a = map(int, input().split())
  xlst = list(map(int, input().split()))
  #xlst.insert(0, 0)

  """
  dp[i][j][k] ... iまででj個使ってkを作る
  dp[i][j][k] += dp[i - 1][j - 1][k - x]
  """
  
  """
  dp =  [[[0] * (50 * n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
  for i in range(n + 1):
    dp[i][0][0] = 1
  
  
  for i in range(1, n + 1):
    x = xlst[i]
    dpi = dp[i]
    dpi_1 = dp[i - 1]
    for j in range(1, n + 1):
      dpij = dpi[j]
      dpi_1j = dpi_1[j]
      dpi_1j_1 = dpi_1[j - 1]
      for k in range(1, n * 50 + 1):
        if k >= x:
          #dp[i][j][k] += dp[i - 1][j - 1][k - x] + dp[i - 1][j][k]
          dpij[k] += dpi_1j_1[k - x] + dpi_1j[k]
        else:
          #dp[i][j][k] += dp[i - 1][j][k]
          dpij[k] += dpi_1j[k]

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

  """

  ans = 0
  dp = [[0] * (n * 50 + 1) for _ in range(n + 1)]
  dp[0][0] = 1
  for x in xlst:
    for j in range(n, 0, -1):
      for k in range(n * 50, x - 1, -1):
        dp[j][k] += dp[j - 1][k - x]
  for j in range(1, n + 1):
    ans += dp[j][j * a]
  print(ans)
main()

Submission status: Accepted

Solution code:
def main():
  n, a = map(int, input().split())
  xlst = list(map(int, input().split()))
  xlst.insert(0, 0)
  """
  dp[i][j][k] ... iまででj個使ってkを作る
  dp[i][j][k] += dp[i - 1][j - 1][k - x]
  """
  
  dp =  [[[0] * (50 * n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
  for i in range(n + 1):
    dp[i][0][0] = 1
  
  
  for i in range(1, n + 1):
    x = xlst[i]
    dpi = dp[i]
    dpi_1 = dp[i - 1]
    for j in range(1, n + 1):
      dpij = dpi[j]
      dpi_1j = dpi_1[j]
      dpi_1j_1 = dpi_1[j - 1]
      for k in range(1, n * 50 + 1):
        if k >= x:
          #dp[i][j][k] += dp[i - 1][j - 1][k - x] + dp[i - 1][j][k]
          dpij[k] += dpi_1j_1[k - x] + dpi_1j[k]
        else:
          #dp[i][j][k] += dp[i - 1][j][k]
          dpij[k] += dpi_1j[k]
  
  ans = 0
  for j in range(1, n + 1):
    ans += dp[n][j][j * a]
  
  print(ans)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
N, A = map(int, raw_input().split())
x = map(int, raw_input().split())

DP =[[0 for i in range(N * 50 + 1)] for j in range(N + 1)]

DP[0][0] = 1

for i in range(N):
	for j in range(N, 0, -1):
		for k in range(x[i], N * 50 + 1):
			DP[j][k] += DP[j - 1][k - x[i]]

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

print ans

Submission status: Accepted

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

dp = [Counter()]
dp[0][0] = 1
for i,a in enumerate(src):
    dp.append(Counter())
    for j in reversed(range(i+1)):
        for k,v in dp[j].items():
            dp[j+1][k+a] += v
ans = 0
for i in range(1,N+1):
    ans += dp[i][A*i]
print(ans)

Submission status: Accepted

Solution code:
def num_ways_for_sum(target, elems, start_idx, end_idx, cache):
    if start_idx > end_idx:
        if target == 0:
            return 1
        else:
            return 0

    cur_ways = 0
    cache_key = (target, start_idx, end_idx)
    if cache_key in cache:
        cur_ways = cache[cache_key]
    else:
        cur_ways += num_ways_for_sum(target + elems[start_idx], elems, start_idx + 1, end_idx, cache)
        cur_ways += num_ways_for_sum(target, elems, start_idx + 1, end_idx, cache)
        cache[cache_key] = cur_ways
    return cur_ways

if __name__ == '__main__':
    n, a = list(map(int, input().split(' ')))
    xs = list(map(int, input().split(' ')))
    diffs = []
    for x in xs:
        diffs.append(x - a)

    print(num_ways_for_sum(0, diffs, 0, len(xs) - 1, {}) - 1)

Submission status: Accepted

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

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

for k in range(1,n+1):
  kx=x[k-1]
  f+=kx
  for i in range(k,0,-1):
    for j in range(kx,a*n+1):
      dp[i][j] += dp[i-1][j-kx]
      if j > f:
        break
      
for i in range(1,n+1):
  ans+=dp[i][a*i]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N,A = map(int,input().split())
src = list(map(int,input().split()))

dp = [dd(lambda:0)]
dp[0][0] = 1
for i,a in enumerate(src):
    dp.append(dd(lambda:0))
    for j in reversed(range(i+1)):
        for k,v in dp[j].items():
            dp[j+1][k+a] += v
ans = 0
for i in range(1,N+1):
    ans += dp[i][i*A]
print(ans)

Submission status: Accepted

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

x_max = max(x)
y = [i-a for i in x]


def ave_comb():
    dp = [[0 for d in range(2*n*x_max+1)] for c in range(n+1)]
    for i in range(n+1):
        dp[i][n*x_max] = 1

    for i in range(1, n+1):
        for j in range(1, 2*n*x_max+1):
            if 0 <= j - y[i-1] <= 2 * n * x_max:
                dp[i][j] = dp[i-1][j-y[i-1]] + dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j]

    return dp[n][n*x_max] - 1


def main():
    print(ave_comb())


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def ave_comb(v_max, ave):
    dp = [[[0 for c in range(n*v_max+1)] for b in range(n+1)] for a in range(n+1)]

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

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

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

    return ans


def main():
    x_max = max(max(x), a)

    print(ave_comb(x_max, a))


if __name__ == '__main__':
    main()