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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

import itertools
from statistics import mean
ans = 0
for i in range(1,n+1):
    l = list(itertools.combinations(x,i))
    for l_ in l:
        if mean(l_)==a:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

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

print(num)

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
x = list(map(lambda q: int(q) - a, input().split()))
num = 0
for i in range(1, 1 << n):
    s = 0
    for j in range(n):
        if 1 << j & i:
            s += x[j]
    if s == 0:
        num += 1

print(num)

Submission status: Time Limit Exceeded

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

""" 3次元DP """

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

# i(=xNリストからどこまでを選べる範囲とするか)からj(=0～N)枚選んで、選んだ値の合計をkにするような選び方の総数
dp = [[[0] * (N*X+1) for j in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 1

ans = 0
for i in range(1,N+1):
    for j in range(N+1):
        for k in range(N*X+1):
            # 求めたい合計(k)が、この周回で増えた選択肢(xN[i-1])より小さい場合、
            # 選び方の総数は増える見込みがないので前回の値をそのまま使用
            if k < xN[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            # 合計kが大きければ、増やせるかもしれないので、選んだ数と合計を減らしたところを見に行く
            # 選べる数j=0は論外だし、添え字[j-1]に良くないので条件で除外する
            elif k >= xN[i-1] and j > 0:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-xN[i-1]]
            # 選んだ数と合計から判断して、平均が条件に合うものなら答えに足す
            if i == N and j > 0 and k == j*A:
                ans += dp[i][j][k]

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

Submission status: Time Limit Exceeded

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

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

ans = 0
for i in range(1,1<<N):
    sum1 = 0
    cnt = 0
    for j in range(N):
        if i & 1<<j:
            sum1 += xN[j]
            cnt += 1
    if sum1 / cnt == A:
        ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from statistics import mean

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

count = 0
for m in range(1, n+1):
	for nums in combinations(x, m):
		if mean(nums) == a:
			count += 1

print(count)

Submission status: Time Limit Exceeded

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

x = [x_i-a for x_i in x]

count = 0
for i in range(1, 2**n):
	bin_str = bin(i)[2:].zfill(n)
	sum_num = 0
	for j, bin_c in enumerate(bin_str):
		if bin_c == "1":
			sum_num += x[j]
	if sum_num == 0:
		count += 1

print(count)

Submission status: Time Limit Exceeded

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)

if n == 1:
    if x[0] == a:
        print(1)
    else:
        print(0)
else:
    g1 = []
    g2 = []

    for i in range(2 ** (n // 2)):
        h = 0
        for j in range(n // 2):
            flag = i >> j & 1
            h += y[j] * flag
        g1.append(h)

    m = n - n // 2
    for i in range(2 ** m):
        h = 0
        for j in range(m):
            flag = i >> j & 1
            h += y[n // 2 + j] * flag
        g2.append(h)

    g2.sort()

    ans = 0
    import bisect

    for i in g1:
        left = bisect.bisect_left(g2, -i)
        right = bisect.bisect(g2, -i)
        ans += right - left

    print(ans-1)

Submission status: Time Limit Exceeded

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

def main():
    n, a = map(int, input().split())
    x_list = list(map(int, input().split()))
    ans = 0

    for i in range(1, n+1):
        arrys = list(itertools.combinations(x_list, i))
        for arry in arrys:
            if sum(arry) / len(arry) == a:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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(x, a, k):
    """
    :param x: tuple
        数列
    :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 len(x) < k:
        return 0

    ret = rec(x[1:], a, k)
    ret += rec(x[1:], a - x[0], k - 1)
    return ret
X = tuple(sorted(X))
m = (rec(X, k * A, k) for k in range(1, N + 1))
print(sum(m))

Submission status: Time Limit Exceeded

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(x, a, k):
    """
    :param x: tuple
        数列
    :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 len(x) < k:
        return 0

    ret = rec(x[1:], a, k)
    ret += rec(x[1:], a - x[0], k - 1)
    return ret

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

# 平均を出すのに選んだ個数が必要
@lru_cache()
def rec(x, a, k):
    """
    :param x: tuple
        数列
    :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 len(x) < k:
        return 0

    ret = rec(x[:-1], a, k)
    ret += rec(x[:-1], a - x[-1], k - 1)
    return ret

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as c

n,a=map(int,input().split())
l=list(map(int,input().split()))
v=0
for i in range(1,n+1):
  v+=sum([1 for j in c(l,i) if sum(j)==a*i])
print(v)

Submission status: Time Limit Exceeded

Solution code:
#部分点解法
def inpl(): return input().split()
n, a = map(int, inpl())
x = list(map(int, inpl()))
x_minus_a = list(map(lambda x: x - a, x))

cnt = 0
for i in range(1, 2 ** n):
    s = 0
    for j in range(n):
        if (2 ** j) & i != 0:
           s += x_minus_a[j] 
    if s == 0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

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

for j, k, s in product(range(1, N + 1), range(N + 1), range((N + 1) * max_x)):
    if s < x[j - 1]:
        dp[j][k][s] = dp[j - 1][k][s]
    elif k >= 1 and s >= x[j - 1]:
        dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j - 1]]

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
Xp = []
Xm = []
X0 = []
for x in X:
  if x > 0:
    Xp.append(x)
  elif x < 0:
    Xm.append(-x)
  else:
    X0.append(x)
limit = min(sum(Xp), sum(Xm))
Xp = [x for x in Xp if x <= limit]
Xm = [x for x in Xm if x <= limit]
R = [[[0, 0]], [[0, 0]]]
def c(X, k):
  Q = []
  heapq.heappush(Q, 0)
  for x in X:
    _Q = []
    while Q:
      q = heapq.heappop(Q)
      if q > limit:
        break
      heapq.heappush(_Q, q)
      heapq.heappush(_Q, q + x)
    Q = _Q
  preq = 0
  while Q:
    q = heapq.heappop(Q)
    if q > limit:
      break
    if q == preq:
      R[k][-1][1] += 1
    else:
      R[k].append([q, 1])
    preq = q
c(Xp, 0)
c(Xm, 1)
cx = 0
while R[0] and R[1]:
  if R[0][0][0] < R[1][0][0]:
    R[0] = R[0][1:]
  elif R[0][0][0] > R[1][0][0]:
    R[1] = R[1][1:]
  else:
    cx += R[0][0][1] * R[1][0][1]
    R[0] = R[0][1:]
    R[1] = R[1][1:]
print(cx * (2 ** len(X0)) - 1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
Xp = []
Xm = []
X0 = []
for x in X:
  if x > 0:
    Xp.append(x)
  elif x < 0:
    Xm.append(-x)
  else:
    X0.append(x)
limit = min(sum(Xp), sum(Xm))
Xp = [x for x in Xp if x <= limit]
Xm = [x for x in Xm if x <= limit]
R = [[0, 0] for x in range(limit + 1)]
def c(X, k):
  Q = []
  heapq.heappush(Q, 0)
  for x in X:
    _Q = []
    while Q:
      q = heapq.heappop(Q)
      if q > limit:
        break
      heapq.heappush(_Q, q)
      heapq.heappush(_Q, q + x)
    Q = _Q
  while Q:
    q = heapq.heappop(Q)
    if q > limit:
      break
    R[q][k] += 1
c(Xp, 0)
c(Xm, 1)
print(sum([r[0] * r[1] for r in R]) * (2 ** len(X0)) - 1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
X0 = [0 for x in X if x == 0]
Xp = [x for x in X if x > 0]
Xm = [-x for x in X if x < 0]
limit = min(sum(Xp), sum(Xm))
Xp = [x for x in Xp if x <= limit]
Xm = [x for x in Xm if x <= limit]
R = [[0, 0] for x in range(limit + 1)]
def c(X, k):
  Q = []
  heapq.heappush(Q, 0)
  for x in X:
    _Q = []
    while Q:
      q = heapq.heappop(Q)
      heapq.heappush(_Q, q)
      heapq.heappush(_Q, q + x)
    Q = _Q
  while Q:
    q = heapq.heappop(Q)
    if q <= limit:
      R[q][k] += 1
    else:
      break
c(Xp, 0)
c(Xm, 1)
print(sum([r[0] * r[1] for r in R]) * (2 ** len(X0)) - 1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
X0 = [0 for x in X if x == 0]
Xp = [x for x in X if x > 0]
Xm = [-x for x in X if x < 0]
limit = min(sum(Xp), sum(Xm))
Xp = [x for x in Xp if x <= limit]
Xm = [x for x in Xm if x <= limit]
R = [[0, 0] for x in range(limit + 1)]
def c(X, k):
  Q = []
  heapq.heappush(Q, 0)
  for x in X:
    _Q = []
    while Q:
      q = heapq.heappop(Q)
      heapq.heappush(_Q, q)
      if q + x <= limit:
        heapq.heappush(_Q, q + x)
    Q = _Q
  while Q:
    R[heapq.heappop(Q)][k] += 1
c(Xp, 0)
c(Xm, 1)
print(sum([r[0] * r[1] for r in R]) * (2 ** len(X0)) - 1)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
X0 = [0 for x in X if x == 0]
Xp = [x for x in X if x > 0]
Xm = [-x for x in X if x < 0]
limit = min(sum(Xp), sum(Xm))
Xp = [x for x in Xp if x <= limit]
Xm = [x for x in Xm if x <= limit]
R = [[0, 0] for x in range(limit + 1)]
def c(X, k):
  Q = [0]
  for x in X:
    Q += [q + x for q in Q if q + x <= limit]
  for q in Q:
    R[q][k] += 1
c(Xp, 0)
c(Xm, 1)
print(sum([r[0] * r[1] for r in R]) * (2 ** len(X0)) - 1)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
X0 = [0 for x in X if x == 0]
Xp = [x for x in X if x > 0]
Xm = [-x for x in X if x < 0]
limit = min(sum(Xp), sum(Xm))
Xp = [x for x in Xp if x <= limit]
Xm = [x for x in Xm if x <= limit]
R = [[0, 0] for x in range(limit + 1)]
def c(X, k):
  for i in range(2 ** len(X)):
    mask = bin(i)[2:]
    mask = [0 for m in range(len(X) - len(mask))] + [int(s) for s in mask]
    masked = sum([X[j] * mask[j] for j in range(len(X))])
    if masked <= limit:
      R[masked][k] += 1
c(Xp, 0)
c(Xm, 1)
print(sum([r[0] * r[1] for r in R]) * (2 ** len(X0)) - 1)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
X0 = [0 for x in X if x == 0]
Xp = [x for x in X if x > 0]
Xm = [-x for x in X if x < 0]
limit = min(sum(Xp), sum(Xm))
R = [[0, 0] for x in range(limit + 1)]
def c(X, k):
  for i in range(2 ** len(X)):
    mask = bin(i)[2:]
    mask = [0 for m in range(len(X) - len(mask))] + [int(s) for s in mask]
    masked = sum([X[j] * mask[j] for j in range(len(X))])
    if masked <= limit:
      R[masked][k] += 1
c(Xp, 0)
c(Xm, 1)
print(sum([r[0] * r[1] for r in R]) * (2 ** len(X0)) - 1)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
X = [int(x) for x in input().split()]
X.sort()
ans = 0
for i in range(1, 2 ** N):
  mask = bin(i)[2:]
  mask = [0 for x in range(N - len(mask))] + [int(s) for s in mask]
  if sum([X[j] * mask[j] for j in range(N)]) / sum(mask) == A:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, a = [int(_) for _ in input().split()]
x = [int(_) for _ in input().split()]

count = 0
for i in range(1, len(x)+1):
    for pick in itertools.combinations(x, i):
        if sum(list(pick)) == a * i:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

array2 = []
tmp = 0
for i in array:
    tmp += i
array2.append(tmp)
ans = 0

for pickup in range(1, n+1):
    tmp_gen = itertools.combinations(array, pickup)

    for i in tmp_gen:
        if sum(i) == a*pickup:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

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

dp[0][0][0] = 1
for limit in range(1,N+1):
    for num in range(limit+1):
        for summ in range(50*N+1):
            if summ-X[limit] < 0:
                dp[limit][num][summ] = dp[limit-1][num][summ]
            else:
                dp[limit][num][summ] = dp[limit-1][num][summ] + \
                                       dp[limit-1][num-1][summ-X[limit]]
         
ans = 0                           
for i in range(1,N+1):
    ans += dp[N][i][A*i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
ans = 0
N, A = map(int, input().split())
X1 = list(map(int, input().split()))
a = 0

def dfs(total, loop, card_num, target_mean):
    global ans
    global N
    
    if loop == N:
        if total/card_num == target_mean:
            ans += 1
        return 0
    else:
        dfs(total        , loop+1, card_num  , target_mean)
        dfs(total+X[loop], loop+1, card_num+1, target_mean)
 
X = X1.copy()
for i in range(N):
    dfs(X[0], 1, 1, A)
    X.pop(0)
    N = len(X)
print(ans)

Submission status: Time Limit Exceeded

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

dp=[[[None for i in range(n*X+1)] for h in range(n+1)] for g 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 x[j-1]>s:
                dp[j][k][s]=dp[j-1][k][s]
            elif j>=1 and k>=1 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
                
ans=0
for i in range(1,n+1):
    ans+=dp[n][i][i*a]

print(ans)

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
x = [int(i) for i in input().split()]
X = max(a, *x)
dp = [[[0 for k in range(n*X+1)] for j in range(n+1)]for i in range(n+1)] #full((n+1, n+1, n*X+1), 0)
dp[0][0][0] = 1
for j in range(n+1):
    for k in range(n+1):
        for s in range(n*X+1):
            if j == k == s == 0: continue
            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(sum([dp[n][k][k*a] for k in range(1, n+1)]))

Submission status: Time Limit Exceeded

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

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

# i番目までからj個選んで和をkにできる選び方の総数
# 選ばない状態も持ちたいから配列は1まわり大きく
dp = [[[0 for k in range(n*a+1)] for j in range(n+1)] for i in range(n+1)]

for i in range(n+1):
    for j in range(n+1):
        for k in range(n*a+1):
            # 初期条件
            if i == 0 and j == 0 and k == 0:
                dp[i][j][k] = 1

            # x_iが和を超過してしまう場合
            elif i > 0 and k < X[i-1]:
                dp[i][j][k] = dp[i-1][j][k]

            # 和を作れる場合
            # 加算する場合としない場合の両方を考える
            elif i > 0 and j > 0 and k >= X[i-1]:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

            # その他
            else:
                dp[i][j][k] = 0

# i枚選んだ時の合計がiAであればよい
ans = 0
for i in range(1, n+1):
    ans += dp[n][i][i*a]

print(ans)

Submission status: Time Limit Exceeded

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


for j in range(n):
    for k in range(n+1):
        for s in range(n*X+1):
            dp[j+1][k][s]+=dp[j][k][s]
            if x[j]+s<n*X+1:
                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: Time Limit Exceeded

Solution code:
from sys import stderr
from functools import reduce
from operator import add
def f(): return [int(i) for i in input().split()]
def debug(*x): stderr.write(reduce(add, repr(x)).strip("()\',") + '\n')

n, a = f()
x = f()
s = sum(x)

dp = [[[0 for i in range(n + 1)] for j in range(s + 1)] for k 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, s + 1):
        for k in range(1, n + 1):
            dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - x[i - 1]][k - 1]

ans = 0
k = 1
while a * k <= s and k <= n:
    ans += dp[n][a*k][k]
    k += 1
print(ans)

Submission status: Time Limit Exceeded

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

x1 = x[:N // 2]
x2 = x[N // 2:]
hoge = [(0, 0)]

for num in x1:
    sz = len(hoge)
    for i in range(sz):
        p = (hoge[i][0] + 1, hoge[i][1] + num)
        hoge.append(p)

dic = {}
for p in hoge:
    rem = A * p[0] - p[1]
    if not rem in dic:
        dic[rem] = 1
    else:
        dic[rem] += 1

hoge = [(0, 0)]

for num in x2:
    sz = len(hoge)
    for i in range(sz):
        p = (hoge[i][0] + 1, hoge[i][1] + num)
        hoge.append(p)

ans = 0
for p in hoge:
    rem = p[1] - A * p[0]
    if rem in dic:
        ans += dic[rem]

print ans - 1

Submission status: Time Limit Exceeded

Solution code:
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]
  for j in range(1, n + 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]
      else:
        dp[i][j][k] += dp[i - 1][j][k]
ans = 0
for j in range(1, n + 1):
  ans += dp[n][j][j * a]

print(ans)

Submission status: Time Limit Exceeded

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

    ans = part(N, A, X)
    print(ans)


def f(N, A, X):
    ans = 0
    print(ans)


def part(N, A, X):
    import sys
    sys.setrecursionlimit(10 ** 7)
    a = [0] * N

    def rec(i, n):
        ans = 0
        if i == n:
            s = 0
            c = 0
            #print(a)
            for j, b in enumerate(a):
                if b == 1:
                    s += X[j]
                    c += 1

            if c == 0:
                return 0
            if s / c == A:
                return 1
            else:
                return 0

        a[i] = 0
        ans += rec(i + 1, n)
        a[i] = 1
        ans += rec(i + 1, n)

        return ans

    ans = rec(0, N)
    return ans


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp= np.zeros((n+1,n*a+1),dtype=int)
dp[0][0]=1
ans=0

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

print(ans)

Submission status: Time Limit Exceeded

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

dp= np.zeros((n+1,n+1,n*a+1),dtype=int)
dp[0][0][0]=1
ans=0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
cnt = [0]
x = list(map(int, input().split()))
check = [0 for i in range(n)]


def ave(idx, k):
    if idx == n:
        s = 0
        for i in range(n):
            if check[i]:
                s += x[i]

        if s == k * a and k != 0:
            cnt[0] += 1

        return

    ave(idx+1, k)
    check[idx] = 1
    ave(idx+1, k+1)
    check[idx] = 0


def main():
    ave(0, 0)
    print(cnt[0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def larger(x, y):
	if x > y: return x
	else: return y

N, A = map(int, raw_input().split())
x = map(int, raw_input().split())
x.sort()
max = larger(x[-1], A)
dp = []

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

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

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

Submission status: Time Limit Exceeded

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

dp = [[[0 for k in range(N*A+1)] for j in range(N+1)] for l in range(N+1)]
dp[0][0][0] = 1

for p in range(N):
    for q in range(N):
        for r in range(N*A):
            dp[p+1][q][r] += dp[p][q][r]
            if r+x[p] <= N*A:
                dp[p+1][q+1][r+x[p]] += dp[p][q][r]
                
ans = 0
for k in range(1,N+1):
    ans += dp[N][k][k*A]
print(ans)

Submission status: Time Limit Exceeded

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

X = [int(i) for i in input().split()]
X = [0]+X
m = max(X+[a])
dp = [[[0]*50*(n+1) for i in range(n+1)] for j in range(n+1)]
#print(dp)


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

         

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

Submission status: Time Limit Exceeded

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

#print(n,a)
#print(x)

cnt=0
for i in range(1,n+1):
    for y in itr.combinations(x,i):
        #print(y)
        if sum(y) == i*a:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    N, A = map(int, input().split())
    X = tuple(map(int, input().split()))

    nx = max(A, max(X)) * N
    dp = np.array([[[0] * (nx + 1) for _ in [0] * (N + 1)] for _ in [0] * (N + 1)])

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

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

main()

Submission status: Time Limit Exceeded

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

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

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

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

main()

Submission status: Time Limit Exceeded

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

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

if max(X) < A:
    print(0)
else:
    Ans = 0
    for i in range(1,N+1):
        Ans += dp[N][i][A*i]
    print(Ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
b = []
def binomial(n):
    global b
    b = [None] * n
    for i in range(n):
        b[i] = [0] * n
        b[i][i] = 1
    for i in range(1, n):
        for j in range(1, i + 1):
            b[i][j] = b[i - 1][j - 1] + b[i - 1][j]
    
cache = {}

def s(x, a, k, i):
    if a < 0: return 0
    if k < 0: return 0
    if k == 0:
        if a == 0: return 1
        else: return 0
    if i > a: return 0
    if i == 51: return 0
    key = (a, k, i)
    if key in cache: return cache[key]
    c = s(x, a, k, i + 1)
    for j in range(1, x[i] + 1):
        c += b[x[i] + 1][j + 1] * s(x, a - i * j, k - j, i + 1)
    cache[key] = c
    return c

n, a = map(int, raw_input().split())
binomial(n + 2)
x = [0] * 51
for k in raw_input().split():
    x[int(k)] += 1

c = 0
for i in range(1, n + 1):
    c += s(x, a * i, i, 0)
print(c)