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()))
X=max(max(x),a)
dp=[[[0]*(n*X+1)for j in range(n+1)]for i in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  xi=x[i-1]
  for j in range(n+1):
      for h in range(j*X+1):
        if h<xi:dp[i][j][h]=dp[i-1][j][h]
        if xi<=h and j>=1:dp[i][j][h]=dp[i-1][j][h]+dp[i-1][j-1][h-xi]
ans=0
for j in range(1,n+1):ans+=dp[n][j][j*a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations


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

ans = 0
for select_num in range(1, N+1):
    select_comb = list(combinations(list_x, select_num))
    # print(select_comb)
    for comb in select_comb:
        # print(comb)
        comb_ave = sum(comb) // len(comb)
        comb_mod = sum(comb) % len(comb)
        # print(comb_ave)
        if comb_ave == A and comb_mod == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,A = map(int,input().split())
B = list(map(int,input().split()))
nums = 0
for i in range(1 << len(B)):
    output = []
    for j in range(len(B)):
        if ((i >> j) & 1) == 1:
            output.append(B[j])
    if len(output)!=0:
        if sum(output)/len(output)==A:
            nums+=1
print(nums)

Submission status: Time Limit Exceeded

Solution code:
def tak_and_cards(N: int, A: int, x: list) -> int:
    count = 0
    for b in range(1, 1 << N):
        n, s = 0, 0
        for i in range(N):
            if (b >> i) & 1 == 0:
                continue
            n += 1
            s += x[i]

        if s == n * A:
            count += 1
    return count


if __name__ == "__main__":
    N, A = map(int, input().split())
    x = [int(s) for s in input().split()]
    ans = tak_and_cards(N, A, x)
    print(ans)

Submission status: Time Limit Exceeded

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

def solve(cur,sum,c):
  if cur==N:
    if sum==c*A:
      return 1
    else:
      return 0
  res=solve(cur+1,sum,c)+solve(cur+1,sum+x[cur],c+1)
  return res

print(solve(0,0,0)-1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

counter = 0
for i in range(1, n + 1):
    for c in combinations(li_x, i):
        # print(c)
        if sum(c) == a * i:
            counter += 1

print(counter)

Submission status: Time Limit Exceeded

Solution code:
#C問題  
N,A=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
NMAX=2**N
count=0
for i in range(NMAX):
    b=bin(i)
    b=b.lstrip("0b")
    blen=len(b)
    roop=N-blen
    for j in range(roop):
        b="0"+b
    
    blist=list(b)
    bN=blist.count("1")
    check=0
    for k in range(N):
        if blist[k] == "0":
            pass
        else:
            check+=x[k]
    
    if check == A*bN:
        count+=1
print(count-1)

Submission status: Time Limit Exceeded

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

def Combi(n, r):
	return int(factorial[n] / factorial[r] / factorial[n-r])
N, A = [int(x) for x in input().rstrip().split()]
x = [int(x) for x in input().rstrip().split()]
# num = [0]*51
# for i in x:
# 	num[i] += 1
# print(2**num[A]-1)
# factorial = [1]
# for i in range(1, 51):
# 	factorial.append(factorial[i-1] * i)
# for i in range(1, A):
X = max(max(x), A)
dp = [[[0]*(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 < 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
sum = 0
for i in range(N+1):
	sum += dp[N][i][i*A]
print(sum-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,a=map(int,input().split())
X=list(map(int,input().split()))
cnt=0
for i in range(1,n+1):
    A=itertools.combinations(X,i)
    for x in A:
        if sum(x)==a*i:
            cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

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

ans = 0
for a in product([0, 1], repeat=N):
    sum = 0
    for i, y in enumerate(a):
        if y == 1:
            sum += x[i]
    if sum == A*a.count(1):
        ans += 1
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

def solve():
    # print(N, A)
    # print(Xs)

    count = 0
    for n in range(1, N + 1):
        # print(list(itertools.combinations(Xs, n)))
        combs = list(itertools.combinations(Xs, n))
        for comb in combs:
            if sum(comb) / len(comb) == A:
                count += 1

    return count

res = solve()
print(res)

Submission status: Time Limit Exceeded

Solution code:
I = lambda: map(int, input().split())
N, A = I()
x = list(I())
 
from collections import deque
import copy
memo = []
checked = []
q = deque()
q.append([False]*N)
 
while q:
    indexs = q.popleft()
    if indexs in checked:
        continue
    checked.append(indexs)
    sum_x = 0
    for i, bit in enumerate(indexs):
        if bit:
            sum_x += x[i]
 
    if indexs.count(True) > 0 and sum_x / indexs.count(True) - A == 0:
        if indexs not in memo:
            memo.append(indexs)
 
    for i in range(N):
        a = copy.deepcopy(indexs)
        a[i] = not(a[i])
        if a not in checked:
            q.append(a)
 
print(len(memo))

Submission status: Time Limit Exceeded

Solution code:
S = input() + " " + input()
#S = """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"""

N, A, *X = list(map(int, S.split()))
c = 0
for n in range(1, 1 << N):
	tl = [x*(n&1<<i!=0) for i, x in enumerate(X)]
	c += sum(tl)/str(bin(n)).count("1")==A
print(c)

Submission status: Time Limit Exceeded

Solution code:
# coding: UTF-8
import numpy as np

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

dp = np.zeros((N+1, N+1, N*A+1))

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


s = sum(dp[N][i][i*A] for i in range(1, N+1))
print(int(s))

Submission status: Time Limit Exceeded

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

ans = [[0,0]] 

for i in range(n):
    ans2 = []
    for x in ans:
        ans2.append([x[0]+X[i],x[1]+1])
        ans2.append([x[0],x[1]])
    ans = ans2

cnt = 0
for a in ans:
    if a[1] == 0:
        continue
    elif a[0]/a[1] == v:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import functools


def zeros(*dim):
    import copy
    if len(dim)==0:
        return 0
    else:
        d = dim[0]
        a = zeros(*dim[1:])
        return [copy.deepcopy(a) for _ in range(d)]


def idx(i, j, k, dims):
    return i + j*dims[0] + k*dims[0]*dims[1]


def solve(a, A):
    a = sorted(a)
    N = len(a)
    S = sum(a)
    dims = (N+1, N+1, 2500+1)
    dp = [0] * functools.reduce(lambda x,y:x*y, dims, 1)
    a.insert(0, float("inf"))  # add dummy at the head

    dp[0] = 1
    mm = max(max(a[1:]), A)
    for j in range(1,N+1):
        for k in range(N+1):
            for s in range(mm*k+1):
                dp[idx(j,k,s,dims)] += dp[idx(j-1,k,s,dims)]
                if s >= a[j]:
                    dp[idx(j,k,s,dims)] += dp[idx(j-1,k-1,s-a[j],dims)]
    ans = 0
    for k in range(1, N+1):
        ans += dp[idx(N,k,k*A,dims)]
    return ans


def main():
    N, A = map(int,input().split())
    a = [int(x) for x in input().split()]
    print(solve(a,A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import functools


def zeros(*dim):
    import copy
    if len(dim)==0:
        return 0
    else:
        d = dim[0]
        a = zeros(*dim[1:])
        return [copy.deepcopy(a) for _ in range(d)]


def idx(i, j, k, dims):
    return i + j*dims[0] + k*dims[0]*dims[1]


def solve(a, A):
    a = sorted(a)
    N = len(a)
    S = sum(a)
    dims = (N+1, N+1, N*A+1)
    dp = [0] * functools.reduce(lambda x,y:x*y, dims, 1)

    a.insert(0, float("inf"))  # add dummy at the head

    dp[0] = 1
    for j in range(1, N+1):
        for k in range(0, N+1):
            for s in range(0, k*A+1):
                dp[idx(j,k,s,dims)] += dp[idx(j-1,k,s,dims)]
                if s >= a[j]:
                    dp[idx(j,k,s,dims)] += dp[idx(j-1,k-1,s-a[j],dims)]
    ans = 0
    for k in range(1, N+1):
        ans += dp[idx(N,k,k*A,dims)]
    return ans


def main():
    N, A = map(int,input().split())
    a = [int(x) for x in input().split()]
    print(solve(a,A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import functools


def zeros(*dim):
    import copy
    if len(dim)==0:
        return 0
    else:
        d = dim[0]
        a = zeros(*dim[1:])
        return [copy.deepcopy(a) for _ in range(d)]


def idx(i, j, k, dims):
    return i + j*dims[0] + k*dims[0]*dims[1]


def solve(a, A):
    a = sorted(a)
    N = len(a)
    S = sum(a)
    dp = zeros(N+1, N+1, N*A+1)
    dims = (N+1, N+1, N*A+1)
    dp = [0] * functools.reduce(lambda x,y:x*y, dims, 1)

    a.insert(0, float("inf"))  # add dummy at the head

    dp[0] = 1
    for j in range(1, N+1):
        for k in range(0, N+1):
            for s in range(0, k*A+1):
                dp[idx(j,k,s,dims)] += dp[idx(j-1,k,s,dims)]
                if s >= a[j]:
                    dp[idx(j,k,s,dims)] += dp[idx(j-1,k-1,s-a[j],dims)]
    ans = 0
    for k in range(1, N+1):
        ans += dp[idx(N,k,k*A,dims)]
    return ans


def main():
    N, A = map(int,input().split())
    a = [int(x) for x in input().split()]
    print(solve(a,A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import functools


def zeros(*dim):
    import copy
    if len(dim)==0:
        return 0
    else:
        d = dim[0]
        a = zeros(*dim[1:])
        return [copy.deepcopy(a) for _ in range(d)]


def idx(i, j, k, dims):
    return i + j*dims[0] + k*dims[0]*dims[1]


def solve(a, A):
    a = sorted(a)
    N = len(a)
    S = sum(a)
    dp = zeros(N+1, N+1, N*A+1)
    dims = (N+1, N+1, N*A+1)
    dp = [0] * functools.reduce(lambda x,y:x*y, dims, 1)

    a.insert(0, float("inf"))  # add dummy at the head

    dp[0] = 1
    for j in range(1, N+1):
        for k in range(0, N+1):
            for s in range(0, N*A+1):
                dp[idx(j,k,s,dims)] += dp[idx(j-1,k,s,dims)]
                if s >= a[j]:
                    dp[idx(j,k,s,dims)] += dp[idx(j-1,k-1,s-a[j],dims)]
    ans = 0
    for k in range(1, N+1):
        ans += dp[idx(N,k,k*A,dims)]
    return ans


def main():
    N, A = map(int,input().split())
    a = [int(x) for x in input().split()]
    print(solve(a,A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def zeros(*dim):
    import copy
    if len(dim)==0:
        return 0
    else:
        d = dim[0]
        a = zeros(*dim[1:])
        return [copy.deepcopy(a) for _ in range(d)]


def solve(a, A):
    a = sorted(a)
    N = len(a)
    S = sum(a)
    dp = zeros(N+1, N+1, N*A+1)

    a.insert(0, float("inf"))  # add dummy at the head

    dp[0][0][0] = 1
    for j in range(1, N+1):
        for k in range(0, N+1):
            for s in range(0, N*A+1):
                dp[j][k][s] += dp[j-1][k][s]
                if s >= a[j]:
                    dp[j][k][s] += dp[j-1][k-1][s-a[j]]
    ans = 0
    for k in range(1, N+1):
        ans += dp[N][k][k*A]
    return ans


def main():
    N, A = map(int,input().split())
    a = [int(x) for x in input().split()]
    print(solve(a,A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
x= sorted(x)
sho = sum(x)//a
dp = [[[[0]*(sho+1) for _ in range(a)]for _ in range(n+1)] for _ in range(n+1)]
#dp[i枚目まで選ぶ][選んだ枚数][aで割ったときの余り][aで割った商]=通り数

dp[0][0][0][0]=1 #何も選ばない

for i in range(0,n):
  j = x[i]%a
  kuwaeru = x[i]//a
  num = 0
  while num<=i:
    for k in range(a):
      for l in range(sho+1):
        if k+j<a and l+kuwaeru <= sho:
          dp[i+1][num+1][(k+j)%a][l+kuwaeru] += dp[i][num][k][l]  #i番目のカードを選ぶ
        elif k+j>=a and l+kuwaeru+1 <= sho:
          dp[i+1][num+1][(k+j)%a][l+kuwaeru+1] += dp[i][num][k][l]  #i番目のカードを選ぶ
  
        dp[i+1][num][k][l] += dp[i][num][k][l]  #i番目のカードを選ばない
    num +=1

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,A=map(int,input().split())
lst=list(map(int,input().split()))
_count=0
for i in range(1,N+1):
    for j in itertools.combinations(lst,i):
        if sum(j)/len(j) == A:
            _count+=1
print(_count)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(2 ** n):
    B = []
    for a in A:
        if i % 2 == 1:
            B.append(a)
        i //= 2
    if len(B) > 0 and sum(B) / len(B) == k:
        cnt += 1
        
print(cnt)

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 for _ in range(N+1)] for _ in range(N+1)] for _ in range(sum(X)+1)]

dp[0][0][0] = 1
for i in range(sum(X) + 1):
    for j in range(1, N + 1):
        for k in range(N + 1):
            if i - X[j] >= 0 and k >= 1:
                dp[i][j][k] = dp[i][j - 1][k] + dp[i - X[j]][j - 1][k - 1]
            else:
                dp[i][j][k] = dp[i][j - 1][k]
                
res = 0

for k in range(1, N + 1):
    if A * k <= sum(X):
        res += dp[A*k][N][k]
                
print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
    #入力
    n, a = map(int,input().split())
    x = list(map(int,input().split()))

    #パターン0~2^n
    #ptの0bit目が0->x1を選択する
    pt = 0
    count = 0

    for pt in range(2**n):
        #ptにしたがって選択カードの合計を計算
        sum_tmp = 0
        num_tmp = 0
        average = 0
        for j in range(n):
            if (pt >> j)&1 :
                sum_tmp += x[j]
                num_tmp += 1
        
        #選択カードの合計から平均を計算
        if num_tmp!=0:
            average = sum_tmp/num_tmp

        if average == a:
            count += 1
        
    print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

maxx = xlist[-1] if xlist[-1] > a else a
# dp[j][k][s]: x_1...x_jまでのなかからk枚選んで合計をsにする総数
dp = [[[0 for _ in range(maxx * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0][0] = 1  # 0枚選んで合計を0にするのは1通り
for j in range(n + 1):
  for k in range(n + 1):
    for s in range(maxx * k + 1):
      if j >= 1 and s < xlist[j-1]:  # x_0は選ばないのと同じなので0のまま更新しない
        dp[j][k][s] = dp[j-1][k][s]
      elif j >= 1 and k >= 1 and s >= xlist[j-1]:
        dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-xlist[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:
n, a = map(int, input().split())
xlist = list(sorted(map(int, input().split())))

maxx = xlist[-1] if xlist[-1] > a else a
# dp[j][k][s]: x_1...x_jまでのなかからk枚選んで合計をsにする総数
dp = [[[0 for _ in range(maxx * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0][0] = 1  # 0枚選んで合計を0にするのは1通り
for j in range(n + 1):
  for k in range(n + 1):
    for s in range(maxx * k + 1):
      if j >= 1:  # x_0は選ばないのと同じなので0のまま更新しない
        if s < xlist[j-1]:
          dp[j][k][s] = dp[j-1][k][s]
        elif k >= 1 and s >= xlist[j-1]:
          dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-xlist[j-1]]

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

Submission status: Time Limit Exceeded

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

maxx = max(xlist[-1], a)
# dp[j][k][s]: x_1...x_jまでのなかからk枚選んで合計をsにする総数
dp = [[[0 for _ in range(maxx * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0][0] = 1  # 0枚選んで合計を0にするのは1通り
for j in range(n + 1):
  for k in range(n + 1):
    for s in range(maxx * n + 1):
      if j >= 1:  # x_0は選ばないのと同じなので0のまま更新しない
        if s < xlist[j-1]:
          dp[j][k][s] = dp[j-1][k][s]
        elif k >= 1 and s >= xlist[j-1]:
          dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-xlist[j-1]]

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

Submission status: Time Limit Exceeded

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

from collections import deque
import copy
memo = []
checked = []
q = deque()
q.append([False]*N)

while q:
    indexs = q.popleft()
    if indexs in checked:
        continue
    checked.append(indexs)
    sum_x = 0
    for i, bit in enumerate(indexs):
        if bit:
            sum_x += x[i]

    if indexs.count(True) > 0 and sum_x / indexs.count(True) - A == 0:
        if indexs not in memo:
            memo.append(indexs)

    for i in range(N):
        a = copy.deepcopy(indexs)
        a[i] = not(a[i])
        if a not in checked:
            q.append(a)

print(len(memo))

Submission status: Time Limit Exceeded

Solution code:
#ABC044C
n,a=map(int,input().split())
x=list(map(int,input().split()))
res=[[0  for i in range(max(1+a*n,1+sum(x)))] for j in range(n+1)]
res[0][0]+=1
for i in range(n):
    for k in range(sum(x),0,-1):
        for j in range(1,n+1):
            if k-x[i]>=0:
                res[j][k]+=res[j-1][k-x[i]]
ans=0
for i in range(1,n+1):
    ans+=res[i][a*i]
print(ans)

Submission status: Time Limit Exceeded

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

from itertools import combinations

cnt = 0
for i in range(1,N+1):
  for per in combinations(X, i):
    #print(per,i,sum(per))
    if(sum(per)/i == A):
      cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
X=sorted(list(map(int,input().split())))
#x1...xjからk枚選んでxiの合計をsにするような選び方の総数
m=max(a,X[-1])
dp=[[[0 for j in range(m*n+1)] for k in range(n+1)]for s 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(m*n+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]]
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 = map(int,input().split())
X = [int(e) for e in input().split()]
# dp[i][k][s]: i番目まで見てk個選んで総和sとなる場合の数
# 初期条件: dp[0][0][0] = 1
# 遷移: dp[i][k][s] += dp[i-1][k-1][s-X[i]] + dp[i-1][k][s]
# 答え: sum(dp[N][k][k*A] 1 <= k <= N)
s_max = 2500
dp = [[[0]*(s_max+1) for k in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 1
for i in range(1,N+1):
    for k in range(N+1):
        for s in range(s_max+1):
            dp[i][k][s] += dp[i-1][k][s]
            if k != 0 and 0 <= s-X[i-1] <= s_max:
                dp[i][k][s] += dp[i-1][k-1][s-X[i-1]]
ans = 0
for k in range(1,N+1):
    s = k*A
    ans += dp[N][k][s]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, A = map(int, input().split())
num_li = list(map(int, input().split()))

per_li = []
for i in range(1,N+1):
  part_ = list(itertools.combinations(num_li,i))
  per_li.append(part_)
  
counter = 0
for j in range(len(per_li)):
  for k in range(len(per_li[j])):
    ans = sum(per_li[j][k])/len(per_li[j][k])
    if ans == A:
      counter += 1
    
print(counter)

Submission status: Time Limit Exceeded

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

from itertools import product
flags = tuple(product((False, True), repeat=N))
cnt = 0
for flag in flags:
    if True not in flag:
        continue
    if sum([x for x, f in zip(X, flag) if f]) == sum(flag) * A:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(2 ** n):
    tmp = 0
    cnt = 0
    for x in X:
        if i % 2 == 0:
            tmp += x
            cnt += 1
        i //= 2
    if cnt != 0 and tmp  == a * cnt:
        ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
m=max(x)
L3=[]
for i3 in range(n+1):
  L2=[]
  for i2 in range(n+1):
    L1=[0 for i1 in range(n*m+1)]
    L2.append(L1)
  L3.append(L2)
for i3 in range(n+1):
  for i2 in range(n+1):
    for i1 in range(m*n+1):
      if i1==0 and i2==0 and i3==0:
        L3[i3][i2][i1]=1
      elif i3>0 and i1<x[i3-1]:
        L3[i3][i2][i1]=L3[i3-1][i2][i1]
      elif i3>0 and i2>0 and i1>=x[i3-1]:
        L3[i3][i2][i1]=L3[i3-1][i2][i1]+L3[i3-1][i2-1][i1-x[i3-1]]
      else:
        L3[i3][i2][i1]=0
ct=0
for i2 in range(n+1):
  for i1 in range(1,m*n+1):
    if i1==i2*a:
      ct+=L3[n][i2][i1]
print(ct)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, A = map(int, input().split())
x = list(map(int, input().split()))
count = 0
x_all = []
for i in range(1, N+1):
    b = []
    a = list(itertools.combinations(x, i))
    for j in a:
        b.append(sum(list(j)))
    x_all.append(b)
base = 1
for i in x_all:
    for j in i:
        if j == A*base:
            count += 1
    base += 1
print(count)

Submission status: Time Limit Exceeded

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

max_sum = sum(x)
dp = [[[0] * 2551 for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(max_sum+1):
            dp[i+1][j+1][k+x[i]] += dp[i][j][k]
            dp[i+1][j][k] += dp[i][j][k]

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

Submission status: Time Limit Exceeded

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

max_sum = sum(x)
dp = [[[0] * (max_sum+1) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(max_sum+1):
            if k+x[i] <= max_sum:
                dp[i+1][j+1][k+x[i]] += dp[i][j][k]
            dp[i+1][j][k] += dp[i][j][k]

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

Submission status: Time Limit Exceeded

Solution code:
N,A = map(int,input().split())
L = list(map(int,input().split()))
#for i in range(N) :
#    L[i] -= A
#L = sorted(L)
ans = 0
for bit in range(1 << N) :
    calc = 0
    ctr = 0
    for k in range(N) :
        if bit & (1 << k) :
            calc += L[k]
            ctr += 1
    if calc == 0 :
        continue
    if calc == A*ctr :
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,A = map(int,input().split())
x = list(map(int,input().split()))
# k個選んだとき k*A == sum(choise)
count = 0
for k in range(1,N+1):
    for ch in itertools.combinations(x,k):
        if sum(ch) == k * A:
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1,N+1):
    com = [sum(c) for c in combinations(X,r=i)]
    ans += com.count(i*A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def heikin(index, num, cnt):
    global A, ans, x, N
    if index < N:
        heikin(index+1, num + x[index], cnt+1)
        heikin(index+1, num, cnt)
    elif index == N:
        if num == A * cnt:
            ans += 1


if __name__ == "__main__":
    N, A = map(int, input().split())
    x = [i for i in map(int, input().split())]
    ans = 0
    heikin(0, 0, 0)
    print(ans-1)

Submission status: Time Limit Exceeded

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


def main():
    from itertools import product

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

    for b in list(product([0, 1], repeat=n)):
        total = 0
        len_b = len(b)
        zero_count = 0

        for i in range(len_b):
            total += x[i] * b[i]

            if b[i] == 0:
                zero_count += 1

        if total > 0 and total == a * (n - zero_count):
            count += 1

    print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections

#リストの中のすべての和の組み合わせについて、合計値と組み合わせ数の辞書を返す
def dictKazu(lst):
    dc = collections.defaultdict(lambda: 0)
    for n in range(1, 2**len(lst)):
        wa = 0
        nbit = '0'*(len(lst)-len(bin(n))+2) + bin(n)[2:]

        for i, l in enumerate(nbit):
            if int(l) == 0:
                pass
            else:
                wa += lst[i]
        dc[wa] += 1
    return dc
       

#昇順にソートされたリストに対し、0が始まるインデックスと、正に切り替わるインデックスを返す
#0が存在しない場合は、[0]=-1を設定
def seifu_i(sortedlst):
    ans = []
    if sortedlst[0] > 0 or sortedlst[-1] < 0:
        return [-1, -1]
    else:
        #0が存在するケース
        if sortedlst.count(0) != 0:
            ans.append(sortedlst.index(0))
            if sortedlst[-1] != 0:
                c = ans[0]         
                while sortedlst[c] <= 0:
                    c += 1
                ans.append(c)
            else:
                ans.append(-2)
        #0が存在しないケースは、最初のインデックスを-1にする
        else:
            ans.append(-1)
            c = 0
            if sortedlst[-1] != 0:
                while sortedlst[c] <= 0:
                    c += 1
                ans.append(c)
            else:
                ans.append(-2)
        return ans

#正負両方があるソートされたリストについて、0を除いて正負でリストをスプリット       
def split(check, sortedlst):
    if check[0] == -1:
        return [sortedlst[:check[1]], sortedlst[check[1]:]]
    else:
        return [sortedlst[:check[0]], sortedlst[check[1]:]]

#組み合わせの数を確認
def tori(lst):
    sortedlst = sorted(lst)
    ch = seifu_i(sortedlst)
#    print("sorted ", sortedlst)
#    print("seifu_i ", ch)

    #組み合わせがないケース
    if ch == [-1, -1]:
        return 0

    #0のみの組み合わせしかありえないケース
    elif ch[0] == 0 or ch[1] == -2:
        if ch[1] == -2:
            zerokazu = len(sortedlst) - ch[0]
        else:
            zerokazu = ch[1] - ch[0]
        return 2**(zerokazu)-1

    #正負が両方あるケース    
    else:
        sp = split(ch, sortedlst)
        negls = [-i for i in sp[0]]
        posls = sp[1]
        negdict, posdict = dictKazu(negls), dictKazu(posls)
#        print("neg ", negdict)
#        print("pos ", posdict)
        if ch[0] == -1:
            zerokazu = 0
        else:
            zerokazu = ch[1] - ch[0]
        
        total = 0
        if len(negdict) > len(posdict):
            for i in negdict:
                if i in posdict:
#                    print("i in posdict ", i, posdict[i], negdict[i])
                    total += negdict[i] * posdict[i]
        else:
            for i in posdict:
                if i in negdict:
                    total += negdict[i] * posdict[i]
        if total == 0:
            if zerokazu == 0:
                return 0
            else:
                return 2**(zerokazu)-1
        else:
            if zerokazu == 0:
                return total
            else:
                return total*2**zerokazu + 2**(zerokazu)-1
         

             

N, A = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
xa = []
for i in range(N):
    xa.append(x[i] - A)

#print(xa)
#print(dictKazu(xa))
#print(seifu_i(xa))
print(tori(xa))

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
# X = list(map(lambda x: int(x) - A, input().split()))
X = list(map(int, input().split()))
maxn = max(max(X), A)

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

for i in range(N):
    for j in range(i + 1):
        for k in range((i + 1) * maxn + 1):
            dp[i + 1][j][k] += dp[i][j][k]
            if k >= X[i]:
                dp[i + 1][j + 1][k] += dp[i][j][k - X[i]]

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()))
M = max(x)
M = max(M, a)
dp = [[[0]*(n*M+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*M+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]]
ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]
print(ans)