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())
xlist = list(map(int, input().split()))

j = n
k = n
t = n * a



dp = [[[0 for t in range(t + 1)] for k in range(k + 1)] for j in range(j + 1)]

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

# for d in dp:
#     print(d)
# print(dp[1][1][15])

for ji in range(0, j + 1):
    for ki in range(0, k + 1):
        for ti in range(0, t + 1):
            # print('now', ji, ki, ti)
            if ji == 0 and ki == 0 and ti == 0:
                # print('branch 1')
                dp[ji][ki][ti] = 1
            elif ji >= 1 and ti < xlist[ji - 1]:
                dp[ji][ki][ti] = dp[ji - 1][ki][ti]
                # print('branch 2')
            elif ji >= 1 and ki >= 1 and ti >= xlist[ji - 1]:
                # print('branch 3', ji - 1)
                dp[ji][ki][ti] = dp[ji - 1][ki][ti] + dp[ji - 1][ki - 1][ti - xlist[ji - 1]]
            else:
                # print('branch 4')
                dp[ji][ki][ti] = 0
            # print(dp[ji][ki][ti])

count = 0
for i in range(1, k + 1):
    count += dp[j][i][i*a]

print(count)

Submission status: Time Limit Exceeded

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

j = n
k = n
t = n * a



dp = [[[0 for t in range(t + 1)] for k in range(k + 1)] for j in range(j + 1)]

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

# for d in dp:
#     print(d)
# print(dp[1][1][15])


for ki in range(0, k + 1):
    for ji in range(0, j + 1):
        for ti in range(0, t + 1):
            # print('now', ji, ki, ti)
            if ji == 0 and ki == 0 and ti == 0:
                # print('branch 1')
                dp[ji][ki][ti] = 1
            elif ji >= 1 and ti < xlist[ji - 1]:
                dp[ji][ki][ti] = dp[ji - 1][ki][ti]
                # print('branch 2')
            elif ji >= 1 and ki >= 1 and ti >= xlist[ji - 1]:
                # print('branch 3', ji - 1)
                dp[ji][ki][ti] = dp[ji - 1][ki][ti] + dp[ji - 1][ki - 1][ti - xlist[ji - 1]]
            else:
                # print('branch 4')
                dp[ji][ki][ti] = 0
            # print(dp[ji][ki][ti])

count = 0
for i in range(1, k + 1):
    count += dp[j][i][i*a]

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
l=list(map(int,input().split()))
count=0

for i in range(2**n):
    s=0
    hg=0
    for j in range(n):
        if (i>>j)&1==1:
            s=s+l[j]
            hg=hg+1
    if s==hg*a and hg!=0:
        count=count+1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
X=list(map(int,input().split()))
dp=[[[0]*52 for _ in range(2505)] for _ in range(52)]
ans=0
dp[0][0][0]=1
for i in range(n):
    for j in range(52+50*i):
        for k in range(51):
            ni=i+1
            nj=j+X[i]
            nk=k+1
            dp[ni][nj][nk]+=dp[i][j][k]
            dp[ni][j][k]+=dp[i][j][k]
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 = list(map(int,input().split()))

dp = [[[0]*(max(sum(x),N*A)+1) for k in range(N+1)] for l in range(N+1)]
# dp[i][j][k] := i番目まででj枚選んで和がkになる組み合わせの数
dp[0][0][0] = 1

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,a=map(int,input().split())
x=list(map(int,input().split()))
pd=list(itertools.product(range(2),repeat=n))
pd=pd[1:]
ans=0
for l in pd:
    c=0
    s=0
    for i in range(n):
        if l[i]==1:
            c+=1
            s+=x[i]
    if s/c==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.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: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
#i番目までのカードのうちj枚を足して数ｓのものを作る方法をリストにメモ計画法で治める
lists=list(map(int,input().split()))
x=max(max(lists),a)
anslist=[[[ 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:
                anslist[0][0][0]=1
            elif j>=1 and s<lists[j-1]:
                anslist[j][k][s]=anslist[j-1][k][s]
            elif j>=1 and k>=1 and s>=lists[j-1] :
                anslist[j][k][s]=anslist[j-1][k][s]+anslist[j-1][k-1][s-lists[j-1]]
            else:
                pass
ans=0
for i in range(1,n+1):
    ans+=anslist[n][i][i*a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
#i番目までのカードのうちj枚を足して数ｓのものを作る方法をリストにメモ計画法で治める
lists=list(map(int,input().split()))

x=max(lists)
x=max(x,a)

anslist=[[[ 0 for _ in range(n*x+1)] for _ in range(n+1)]for _ in range(n+1)]



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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n, a = map(int, input().split())
x = list(map(int, input().split()))

def rec(i, j, tmp):
  if i == n:
    if j and tmp / j == a:
      return 1
    else:
      return 0
  return rec(i+1, j+1, tmp + x[i]) + rec(i+1, j, tmp)
  
print(rec(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N,A=map(int,input().split())

card=list(map(int,input().split()))
ans=0
for i in range(2**N):
    all=0
    count=0
    for j in range(N):
        if (i>>j)&1:
            all+=card[j]
            count+=1
    if all==(A*count):
        ans+=1
            
print(ans-1)
#わからんとりとり

Submission status: Time Limit Exceeded

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

dp = [[[0]*(50*N+1) for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 1 
for j in range(1,N+1):
  for k in range(N+1):
    for s in range(50*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 k in range(1,N+1):
  ans += dp[N][k][k*A]
print(ans)

Submission status: Time Limit Exceeded

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

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

# 平均を A にしたいので、
# 先に A を引いて、平均を 0 にすることを目指す

xs = [x - A for x in xs]

count = 0

for i in range(2 ** N):
  string = "{:0" + str(N) + "b}"
  use = string.format(i)[::-1]

  ans = 0
  for i, flag in enumerate(use):
    if flag == "1":
      ans += xs[i]
    else:
      pass
  if ans == 0:
    count += 1
  
if A != 0:
  count -= 1
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
x = [int(i) for i in input().split()]
dp = [[[0 for _ in range(((n * a) + 1))] for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for j, xx in enumerate(x):
    j += 1
    for k in range(n + 1):
        for s in range((n * a) + 1):
            if (k >= 1):
                if (s >= xx):
                    dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - xx]
                else:
                    dp[j][k][s] = dp[j - 1][k][s]
            elif (s < xx):
                dp[j][k][s] = dp[j - 1][k][s]
ans = sum([dp[n][i+1][(i+1)*a] for i in range(n)])
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
x = [int(i) for i in input().split()]
dp = []
for _ in range(n + 1):
    k = []
    for _ in range(n + 1):
        k.append([0] * ((n * a) + 1))
    dp.append(k)
dp[0][0][0] = 1
for j in range(1, n + 1):
    for k in range(n + 1):
        for s in range((n * a) + 1):
            if (k >= 1):
                if (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] = dp[j - 1][k][s]
            elif (s < x[j - 1]):
                dp[j][k][s] = dp[j - 1][k][s]
ans = sum([dp[n][i+1][(i+1)*a] for i in range(n)])
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
x = [int(i) for i in input().split()]
dp = []
for _ in range(n + 1):
    k = []
    for _ in range(n + 1):
        k.append([0] * ((n * a) + 1))
    dp.append(k)
dp[0][0][0] = 1
for j in range(n + 1):
    for k in range(n + 1):
        for s in range((n * a) + 1):
            if (j >= 1) & (s < x[j - 1]):
                dp[j][k][s] = dp[j - 1][k][s]
            elif (j >= 1) & (k >= 1) & (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 i in range(n):
    ans += dp[n][i+1][(i+1)*a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
x = [int(i) for i in input().split()]
count = 0
for i in range(1, 2 ** n):
    temp = bin(i)[2:]
    temp = ("0" * (n - len(temp))) + temp
    mean_x = 0
    for j, t in enumerate(temp):
        if t == "1":
            mean_x += x[j]
    if mean_x == a * (temp.count("1")):
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    for j in range(N):
        for t in range(2501):
            dp[i + 1][j][t] += dp[i][j][t]
            dp[i + 1][j + 1][t + X[i]] += dp[i][j][t]

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()))
dp = [[[0 for _ in range(50*N + 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*N+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: Time Limit Exceeded

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
for i in range(1, N+1):
    for j in range(N+1):
        for k in range(50*N+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: Time Limit Exceeded

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

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

dp[0][0][0] = 1
for i in range(1, N+1):
    for j in range(N+1):
        for k in range(50*N+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: Time Limit Exceeded

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

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

dp[0][0][0] = 1
for i in range(1, N+1):
    for j in range(N+1):
        for k in range(50*N+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: Time Limit Exceeded

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

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

dp[0][0][0] = 1
for i in range(1, N+1):
    for j in range(N+1):
        for k in range(50*50+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: Time Limit Exceeded

Solution code:
n,a=[int(_) for _ in input().split()]
x=[int(_) for _ in input().split()]
dp=[[[0 for k in range(2551)] for j in range(51)] for i in range(n)]
dp[0][1][x[0]]=1;dp[0][0][0]=1
for i in range(n-1):
    for j in range(50):
        for k in range(2501):
            dp[i+1][j+1][k+x[i+1]] += dp[i][j][k]
            dp[i+1][j][k] += dp[i][j][k]
ans=0
for j in range(1,n+1):ans += dp[-1][j][j*a]
print(ans)

Submission status: Time Limit Exceeded

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, N + 1, NX + 1), dtype=int)

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 >= 1 and s < X[j]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif j >= 1 and k >= 1 and s >= X[j]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - X[j]]

ret = 0

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

print(ret)

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
x=sorted(list(map(int,input().split())))
for i in range(n):
    x[i]-=a
cnt=0
for i in range(2**n):
    ans=0
    for j in range(n):
        if ((i>>j)&1):
            ans+=x[j]
    if ans==0:
        cnt+=1
print(cnt-1)

Submission status: Time Limit Exceeded

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


def ans(i, A, lst):
    comb = tuple(combinations(lst, i))
    return sum(1 for i in comb if sum(i) == A)


def main():
    n, a = list(map(int, input().rstrip().split()))
    lst = tuple(map(int, input().rstrip().split()))
    cnt = 0
    for i in range(1, n + 1):
        cnt += ans(i, i * a, lst)
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

ans = 0 
for i in range(2**N): 
    total = 0
    cnt = 0
    for j in range(N):
        if (i >> j) & 1 :
            cnt += 1
            total += card_num[j]
    
    if cnt != 0 :
        if total / cnt == A :
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
x = [int(_) for _ in input().split()]
M = 2500
dp = [[[0]*(N+1) for _ in range(M+1)] for _ in range(N+1)]
dp[0][0][0] = 1

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

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

print(ans)

Submission status: Time Limit Exceeded

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

from functools import lru_cache

@lru_cache(maxsize=1000000000)
def f(j, k, s):
    if j == 0 and k == 0 and s == 0:
        return 1
    elif j > 0 and X[j - 1] > s:
        return f(j - 1, k, s)
    elif j > 0 and k - 1 >= 0 and s - X[j - 1] >= 0:
        return f(j - 1, k, s) + f(j - 1, k - 1, s - X[j - 1])
    else:
        return 0


ret = 0
for i in range(N + 1):
    r = f(N, i + 1, (i + 1) * A)
    ret += r

print(ret)

Submission status: Time Limit Exceeded

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

from functools import lru_cache

@lru_cache(maxsize=1000000)
def f(j, k, s):
    if j == 0 and k == 0 and s == 0:
        return 1
    elif j > 0 and X[j - 1] > s:
        return f(j - 1, k, s)
    elif j > 0 and k - 1 >= 0 and s - X[j - 1] >= 0:
        return f(j - 1, k, s) + f(j - 1, k - 1, s - X[j - 1])
    else:
        return 0


ret = 0
for i in range(N + 1):
    r = f(N, i + 1, (i + 1) * A)
    ret += r

print(ret)

Submission status: Time Limit Exceeded

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

M = 50

# from collections import defaultdict
# dp = defaultdict(lambda: 0)
# dp[0,0,0] = 1

from functools import lru_cache


@lru_cache(maxsize=100000)
def f(j, k, s):
    if j == 0 and k == 0 and s == 0:
        return 1
    elif j > 0 and X[j - 1] > s:
        return f(j - 1, k, s)
    elif j > 0 and k - 1 >= 0 and s - X[j - 1] >= 0:
        return f(j - 1, k, s) + f(j - 1, k - 1, s - X[j - 1])
    else:
        return 0


ret = 0
for i in range(N + 1):
    r = f(N, i + 1, (i + 1) * A)
    # print("{}, i".format(r, i))
    ret += r

print(ret)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

N, A = map(int, input().rstrip().split())

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

def isA_erase(X):
    """
    erase A in X and count items
    input
    X: input list
    output
    X: erased list
    count: erase item num
    """
    erase_count = 0
    while A in X:
        X.remove(A)
        erase_count += 1
    
    return X, erase_count

X, erase_count = isA_erase(X)
count = 0
# Xの中にあるAを除いて作ることのできるAの数
for i in range(1, N+1 - erase_count):
    cards_list = np.array(list(itertools.combinations(X, i)))
    cards_average = np.sum(cards_list, axis= -1) / i
    count += np.sum(cards_average == A)
count = count * (pow(2, erase_count) - 1) + count + (pow(2, erase_count) - 1)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,a=map(int,input().split())
X=[int(i) for i in input().split()]
DP=np.zeros((n+1,n+1,50*n+1),dtype=int)
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: Time Limit Exceeded

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

def dfs(a, b, c):
  #print("{0} {1} {2}".format(a, b, c))
  r = 0
  if c == N:
    if b > 0 and a == b*A:
      #print("{0} {1} {2} ok".format(a, b, c))
      return 1
    return 0
  r += dfs(a+x[c], b+1, c+1)
  r += dfs(a, b, c+1)
  return r

print(dfs(0, 0, 0))

Submission status: Time Limit Exceeded

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

Solution code:
n, a =map(int, input().split())
x=list(map(int, input().split()))
x=[i-a for i in x]
memo=[[-1]*100000 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: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
x_array = sorted([int(x) for x in input().split()], reverse=True)
res = 0
for i in range(2 ** n):
    bit = bin(i)
    one = bit.count("1")
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            tmp += x_array[j]
    if tmp == one*a and one != 0:
        res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np

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


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

    dp = np.zeros((n + 1, n + 1, (n + 1) * max(max(xlist), a)))

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

Solution code:

import numpy as np

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


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

    dp = np.zeros((n + 1, n + 1, (n + 1) * max(max(xlist), a)))

#   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

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

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

    print(int(methods))


if __name__ == '__main__':
    submit()

Submission status: Time Limit Exceeded

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

dp = [ [[0] * 3000 for _ in range(55)] for __ in range(55) ]
dp[0][0][0] = 1

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

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 itertools
import sys
input = sys.stdin.readline
n,a=(int(i) for i in input().split())
x=[int(i) for i in input().split()]
#print(n,a,x)

mylist=list(itertools.product(range(2), repeat=n))

cnt=0
for j in range(2**n):
    val=0
    for i in range(n):
        val+=mylist[j][i]*x[i]
    if val==a*sum(mylist[j]):
#        print(mylist[j])
        cnt+=1
print(cnt-1)

Submission status: Time Limit Exceeded

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

# import numpy as np
# dp = np.full((n + 1, n + 1, n * max(x + [a]) + 1), None).tolist()
#
def full(shape, value):
    if not shape:
        return value
    return [full(shape[1:], value) for _ in range(shape[0])]
dp = full((n + 1, n + 1, n * max(x + [a]) + 1), None)

def dfs(j=n, k=n, s=n * max(x)):
    if dp[j][k][s] is not None:
        return dp[j][k][s]
    if j == k == s == 0:
        dp[0][0][0] = 1
        return 1
    result = 0
    if j >= 1:
        if x[j - 1] > s:
            result = dfs(j - 1, k, s)
        elif k >= 1:
            result = dfs(j - 1, k, s) + dfs(j - 1, k - 1, s - x[j - 1])
    dp[j][k][s] = result
    return result

print(sum(dfs(n, k, k * a) for k in range(1, n + 1)))

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
X=list(map(int,input().split()))
def DP(i,j,k):
  if i==0:
    if j==0 and k==0:
      return 1
    else:
      return 0
  else:
    return DP(i-1,j,k)+DP(i-1,j-1,k-X[i-1])
ans=0
for i in range(1,50):
  ans+=DP(n,i,i*a)
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(2**N):
    tmp = 0 
    for j in range(N):
        if (i>>j)&1:
            tmp+=X[j]       
    if tmp==0:      
        ans += 1
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def bit(n, m):
    bit_list = list(itertools.product([i for i in range(m)], repeat=n))
    return bit_list

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

bits = bit(N,2)
res = 0

for i in bits:
    tmp = 0
    if sum(i) == 0:
        continue

    for j in range(N):
        if i[j] == 1:
            tmp += X[j]
    
    if tmp/i.count(1) == A:
        res += 1


print(res)