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()))
t=[[[0 for s in range((n+1)*a+1)]for k in range(n+1)]for j in range(n+1)]
ans=0
for j in range(n+1):
  for k in range(n+1):
    if k>j:
      break
    for s in range((n+1)*a+1):
      if s==0 and k==0 and j==0:
        t[j][k][s]=1
      elif j>=1 and x[j-1]>s:
        t[j][k][s]=t[j-1][k][s]
      elif j>=1 and k>=1 and x[j-1]<=s:
        t[j][k][s]=t[j-1][k][s]+t[j-1][k-1][s-x[j-1]]
      if j==n and k>=1 and s==k*a:
        ans+=t[j][k][s]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
t=[[[0 for s in range((n+1)*a+1)]for k in range(n+1)]for j in range(n+1)]
for j in range(n+1):
  for k in range(n+1):
    if k>j:
      break
    for s in range((n+1)*a+1):
      if s==0 and k==0 and j==0:
        t[j][k][s]=1
      elif j>=1 and x[j-1]>s:
        t[j][k][s]=t[j-1][k][s]
      elif j>=1 and k>=1 and x[j-1]<=s:
        t[j][k][s]=t[j-1][k][s]+t[j-1][k-1][s-x[j-1]]
ans=0
for i in range(n):
  ans+=t[n][i+1][(i+1)*a]
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,ad=map(int,input().split())
b=[int(i)for i in input().split()]
def combs(a):
    if len(a) == 0:
        return [[]]
    cs =[]
    for c in combs(a[1:]):
        cs += [c, c+[a[0]]]
    return cs
cou=0
for i in combs(b):
  if len(i)==0:
    continue
  elif sum(i)/len(i)==ad:
    cou+=1
print(cou)

Submission status: Time Limit Exceeded

Solution code:

n, a = map(int, input().split())
x = list(map(int, input().split()))
ans = 0
for i in range(1, 2 ** n):
    sum = 0
    cnt = 0
    for j in range(n):
        if i >> j & 1:
            sum += x[j]
            cnt += 1
    
    if sum / cnt == a:
        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 for k in range(50 * N + 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):
    for j in range(i+1):
        for k in range(50 * N + 1):
            dp[i][j][k] += dp[i-1][j][k]
            if j != 0 and k - X[i-1] >= 0:
                dp[i][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()))
#n=4
#a=8
#x=[7,9,8,9]

#xsum=max(max(x),a)*n
xsum=max(sum(x),a*n)
dp=[[[0]*(xsum+1) for i in range(n+1)] for ii in range(n+1)]

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

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

Submission status: Time Limit Exceeded

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

xsum=max(max(x),a)*n
dp=[[[0]*(xsum+1) for i in range(n+1)] for ii in range(n+1)]

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N, A = tuple(map(int, input().split()))
x = list(map(int, input().split()))
x_sub = []
ans = 0
for n in range(len(x)+1):
    if n>0:
        for c in combinations(x, n):
            x_sub.append(c)
#print(x_sub)
x_means = [sum(a)/len(a) for a in x_sub]
#print(x_means)
for i in range(len(x_means)):
    if x_means[i]==A:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

# ABC044-C
# N枚のカードがあり、i番目(1<i<N)番目のカードには整数x(i)が書かれている
# カードを一枚以上選び、選んだカードの平均をAとしたい
# このような選び方は何通りあるか
# 三次元配列を用いたdpを行う。計算量はO(N^3*X)

N,A=imn()
x = iln()
# 数値の最大値
X = 50

# dp[i][j][k]とする
# xの中からj枚を選んで、x(i)の合計をkにするような選び方の総数
dp = [[[0 for _ in range(N*X+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for j in range(N):
    for k in range(N):
        for s in range(N*X+1):
            # 選択したカードの数値がS未満の場合
            if s-x[j] < 0:
                # 選択できないので、前回値をそのまま移行
                dp[j+1][k][s] = dp[j][k][s]
            else:
                # 選択した場合の値は下記の2値を加算
                # 1.dp[j][k+1][s]は今回選択してないが、既に合計がsのなる場合の数
                # 2.dp[j][k][s-x[j]]は今回選択することにより、合計がsとなる場合の数 
                dp[j+1][k+1][s] = dp[j][k+1][s] + dp[j][k][s-x[j]]


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

import itertools

cnt = 0
for n in range(1, N+1):
    for i in itertools.combinations(x, n):
        if sum(i) / n == A:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N,A=imn()
x = iln()

ans = 0
for i in range(1,2**N):
    bit = i
    selected = []
    index = 0

    while bit > 0:
        if bit & 1 == 1:
           selected.append(x[index])
        index += 1
        bit = bit >> 1

    if sum(selected) == A*len(selected):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

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

# i 個目までのj個選んで　和のmod aが k

for i in range(n):    
    for j in range(i+1):
        for k in range(2501):

            dp[i+1][j][k] += dp[i][j][k]
            if k+l[i] < 2501:
                dp[i+1][j+1][k+l[i]] += 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:
def resolve():
	n, a = map(int, input().split())
	x = list(map(int, input().split()))
	ans = 0
	for i in range(1 << n):
		selected = []
		for j in range(n):
			if (i >> j) & 1:
				selected.append(x[j])
		if len(selected) and a == sum(selected) / len(selected):
			ans += 1
	print(ans)
resolve()

Submission status: Time Limit Exceeded

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

xmax=max(max(x),a)
    
nx=n*xmax
dp=[[[0]*(nx+1) for ii in range(n+1)] for i in range(n+1)]

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

for j in range(1,n+1):
    jj=j-1
    for k in range(n+1):
        for s in range(nx+1):
            if s<x[jj]:
                dp[j][k][s]=dp[j-1][k][s]
            elif 1<=k and  x[jj]<=s:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-x[jj]]
            else:
                dp[j][k][s]=0
#            if dp[j][k][s]!=0:
#                print(j,k,s,dp[j][k][s])
dpsum=0
for k in range(1,n+1):
    dpsum=dpsum+dp[n][k][k*a]
                
print(dpsum)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
from functools import lru_cache, reduce
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# ここから書き始める
n, a = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
ans = 0
flag = True
y = [0] * n
cnt2 = 0
for i in range(n):
    if x[n - i - 1] == a:
        if flag:
            flag = False
        else:
            cnt2 += 1
            y[n - i - 1] = cnt2
# print("y =", y)


def dfs(i, total, cnt):
    global ans
    if i == n:
        if cnt > 0 and total / cnt == a:
            ans += 1
        return 
    if cnt > 0 and total / cnt > a:
        return 
    if cnt > 0 and total / cnt == a:
        if x[i - 1] == a:
            ans += 2 ** y[i - 1]
        else:
            ans += 1
        return 
    dfs(i + 1, total + x[i], cnt + 1)
    dfs(i + 1, total, cnt)

dfs(0, 0, 0)
print(ans)
# for i in range(n):
#     x[i] -= a
# x.sort()
# print(x)
# ans = 0


# def dfs(i, total):
#     global ans
#     if i == n:
#         if total == 0:
#             ans += 1
#             # if prev == 0:
#             #     ans += 1
#         return
#     if total > 0:
#         return 
#     if total == 0 and i > 0:
#         ans += 1
#         # if prev == 0:
#         #     ans += 1
#         return 
#     dfs(i + 1, total + x[i])
#     dfs(i + 1, total)

# dfs(0, 0)
# print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
from functools import lru_cache, reduce
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# ここから書き始める
n, a = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
ans = 0
flag = True
y = [0] * n
cnt2 = 0
for i in range(n):
    if x[n - i - 1] == a:
        if flag:
            flag = False
        else:
            cnt2 += 1
            y[n - i - 1] = cnt2
# print("y =", y)


def dfs(i, total, cnt):
    global ans
    if i == n:
        if cnt > 0 and total / cnt == a:
            ans += 1
        return 
    if cnt > 0 and total / cnt > a:
        return 
    if cnt > 0 and total / cnt == a:
        ans += 2 ** y[i - 1]
        return 
    dfs(i + 1, total + x[i], cnt + 1)
    dfs(i + 1, total, cnt)

dfs(0, 0, 0)
print(ans)
# for i in range(n):
#     x[i] -= a
# x.sort()
# print(x)
# ans = 0


# def dfs(i, total):
#     global ans
#     if i == n:
#         if total == 0:
#             ans += 1
#             # if prev == 0:
#             #     ans += 1
#         return
#     if total > 0:
#         return 
#     if total == 0 and i > 0:
#         ans += 1
#         # if prev == 0:
#         #     ans += 1
#         return 
#     dfs(i + 1, total + x[i])
#     dfs(i + 1, total)

# dfs(0, 0)
# print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
from functools import lru_cache, reduce
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# ここから書き始める
n, a = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
ans = 0

def dfs(i, total, cnt):
    global ans
    if i == n:
        if cnt > 0 and total / cnt == a:
            ans += 1
        return 
    if cnt > 0 and total / cnt > a:
        return 
    # if cnt > 0 and total / cnt == a:
    #     ans += 1
    #     return 
    dfs(i + 1, total + x[i], cnt + 1)
    dfs(i + 1, total, cnt)

dfs(0, 0, 0)
print(ans)
# for i in range(n):
#     x[i] -= a
# x.sort()
# print(x)
# ans = 0


# def dfs(i, total):
#     global ans
#     if i == n:
#         if total == 0:
#             ans += 1
#             # if prev == 0:
#             #     ans += 1
#         return
#     if total > 0:
#         return 
#     if total == 0 and i > 0:
#         ans += 1
#         # if prev == 0:
#         #     ans += 1
#         return 
#     dfs(i + 1, total + x[i])
#     dfs(i + 1, total)

# dfs(0, 0)
# print(ans - 1)

Submission status: Time Limit Exceeded

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

for i in range(n):
    x[i]=x[i]-a
    
n2=n//5
n3=n-n2*4

y1=[]
y2=[]
y3=[]
y4=[]
for i in range(n2):
    y1.append(x[i])
    y2.append(x[i+n2])
    y3.append(x[i+n2*2])
    y4.append(x[i+n2*3])
y9=[]
for i in range(n3):
    y9.append(x[i+n2*4])
    
# itertools 使用 bit全探索
import itertools

def xdic(n2,xx):
    xsum=dict()
    for i in itertools.product([0,1], repeat=n2):
        isum=0
        for ii in range(n2):
            if i[ii]==0:
                isum=isum+xx[ii]
        if isum in xsum:
            xsum[isum]=xsum[isum]+1
        else:
            xsum[isum]=1
    return xsum

xsum1=xdic(n2,y1)
xsum2=xdic(n2,y2)
xsum3=xdic(n2,y3)
xsum4=xdic(n2,y4)
xsum9=xdic(n3,y9)
    
icnt=0
for xs1 in xsum1.items():
    for xs2 in xsum2.items():
        for xs3 in xsum3.items():
            for xs4 in xsum4.items():
                for xs9 in xsum9.items():
                    if xs1[0]+xs2[0]+xs3[0]+xs4[0]+xs9[0]==0:
                        icnt=icnt+xs1[1]*xs2[1]*xs3[1]*xs4[1]*xs9[1]

print(icnt-1)

Submission status: Time Limit Exceeded

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

for i in range(n):
    x[i]=x[i]-a
    
n2=n//8
n3=n-n2*8

y1=[]
y2=[]
y3=[]
y4=[]
y5=[]
y6=[]
y7=[]
y8=[]
for i in range(n2):
    y1.append(x[i])
    y2.append(x[i+n2])
    y3.append(x[i+n2*2])
    y4.append(x[i+n2*3])
    y5.append(x[i+n2*4])
    y6.append(x[i+n2*5])
    y7.append(x[i+n2*6])
    y8.append(x[i+n2*7])
y9=[]
for i in range(n3):
    y9.append(x[i+n2*8])
    
# itertools 使用 bit全探索
import itertools

def xdic(n2,xx):
    xsum=dict()
    for i in itertools.product([0,1], repeat=n2):
        isum=0
        for ii in range(n2):
            if i[ii]==0:
                isum=isum+xx[ii]
        if isum in xsum:
            xsum[isum]=xsum[isum]+1
        else:
            xsum[isum]=1
    return xsum

xsum1=xdic(n2,y1)
xsum2=xdic(n2,y2)
xsum3=xdic(n2,y3)
xsum4=xdic(n2,y4)
xsum5=xdic(n2,y5)
xsum6=xdic(n2,y6)
xsum7=xdic(n2,y7)
xsum8=xdic(n2,y8)
xsum9=xdic(n3,y9)
    
icnt=0
for xs1 in xsum1.items():
    for xs2 in xsum2.items():
        for xs3 in xsum3.items():
            for xs4 in xsum4.items():
                for xs5 in xsum5.items():
                    for xs6 in xsum6.items():
                        for xs7 in xsum7.items():
                            for xs8 in xsum8.items():
                                for xs9 in xsum9.items():
                                    if xs1[0]+xs2[0]+xs3[0]+xs4[0]+xs5[0]+xs6[0]+xs7[0]+xs8[0]+xs9[0]==0:
                                        icnt=icnt+xs1[1]*xs2[1]*xs3[1]*xs4[1]*xs5[1]*xs6[1]*xs7[1]*xs8[1]*xs9[1]

print(icnt-1)

Submission status: Time Limit Exceeded

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

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

n2=n//4
n3=n-n2*4

y1=[]
y2=[]
y3=[]
y4=[]
for i in range(n2):
    y1.append(x[i])
    y2.append(x[i+n2])
    y3.append(x[i+n2*2])
    y4.append(x[i+n2*3])
#    y5.append(x[i+n2*4])
#    y6.append(x[i+n2*5])
#    y7.append(x[i+n2*6])
#    y8.append(x[i+n2*7])
y9=[]
for i in range(n3):
    y9.append(x[i+n2*4])
    

# itertools 使用 bit全探索
import itertools

def xdic(n2,xx):
    xsum=dict()
    for i in itertools.product([0,1], repeat=n2):
        isum=0
        for ii in range(n2):
            if i[ii]==0:
                isum=isum+xx[ii]
        if isum in xsum:
            xsum[isum]=xsum[isum]+1
        else:
            xsum[isum]=1
    return xsum

xsum1=xdic(n2,y1)
xsum2=xdic(n2,y2)
xsum3=xdic(n2,y3)
xsum4=xdic(n2,y4)
#xsum5=xdic(n2,y5)
#xsum6=xdic(n2,y6)
#xsum7=xdic(n2,y7)
#xsum8=xdic(n2,y8)
xsum9=xdic(n3,y9)
  
#xsum[0]=xsum[0]
#print(xsum)        
    
icnt=0
for xs1 in xsum1.items():
    for xs2 in xsum2.items():
        for xs3 in xsum3.items():
            for xs4 in xsum4.items():
                for xs9 in xsum9.items():
                    if xs1[0]+xs2[0]+xs3[0]+xs4[0]+xs9[0]==0:
                        icnt=icnt+xs1[1]*xs2[1]*xs3[1]*xs4[1]*xs9[1]

print(icnt-1)

Submission status: Time Limit Exceeded

Solution code:

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

#n=4
#a=8
#x=[7,9,8,9]

#n=8
#a=5
#x=[3,6,2,8,7,6,5,9]

for i in range(n):
    x[i]=x[i]-a
    
n2=n//2
n3=n-n2

y=[]
for i in range(n3):
    y.append(x[i+n2])

xsum=dict()
for i in range(2 ** n2):
    isum=0
    for j in range(n2):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            isum=isum+x[j]
    if isum in xsum:
        xsum[isum]=xsum[isum]+1
    else:
        xsum[isum]=1
#print(xsum)        
    
icnt=0
for i in range(2 ** n3):
    isum=0
    for j in range(n3):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            isum=isum+y[j]
#    print(isum)
    for xs in xsum.items():
        if xs[0]==-isum:
            icnt=icnt+(xs[1])
#            print(isum,xs[1],(xs[1]),icnt)

print(icnt-1)

Submission status: Time Limit Exceeded

Solution code:

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

#n=4
#a=8
#x=[7,9,8,9]

#n=8
#a=5
#x=[3,6,2,8,7,6,5,9]

for i in range(n):
    x[i]=x[i]-a
    
n2=n//2
n3=n-n2

y=[]
for i in range(n3):
    y.append(x[i+n2])

# itertools 使用 bit全探索
import itertools

xsum=dict()
for i in itertools.product([0,1], repeat=n2):
    isum=0
    for ii in range(n2):
        if i[ii]==0:
            isum=isum+x[ii]
    if isum in xsum:
        xsum[isum]=xsum[isum]+1
    else:
        xsum[isum]=1
#xsum[0]=xsum[0]
#print(xsum)        
    
icnt=0
for i in itertools.product([0,1], repeat=n3):
    isum=0
    for ii in range(n3):
        if i[ii]==0:
            isum=isum+y[ii]
#    print(isum)
    for xs in xsum.items():
        if xs[0]==-isum:
            icnt=icnt+(xs[1])
#            print(isum,xs[1],(xs[1]),icnt)

print(icnt-1)

Submission status: Time Limit Exceeded

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

#n=4
#a=8
#x=[7,9,8,9]

#n=8
#a=5
#x=[3,6,2,8,7,6,5,9]

for i in range(n):
    x[i]=x[i]-a
    
n2=n//2
n3=n-n2

y=[]
for i in range(n3):
    y.append(x[i+n2])

# itertools 使用 bit全探索
import itertools

xsum=dict()
for i in itertools.product([0,1], repeat=n2):
    isum=0
    for ii in range(n2):
        if i[ii]==0:
            isum=isum+x[ii]
    if isum in xsum:
        xsum[isum]=xsum[isum]+1
    else:
        xsum[isum]=1
xsum[0]=xsum[0]-1*0
#print(xsum)        
    
icnt=0
for i in itertools.product([0,1], repeat=n3):
    isum=0
    for ii in range(n3):
        if i[ii]==0:
            isum=isum+y[ii]
#    print(isum)
    for xs in xsum.items():
        if xs[0]==-isum:
            icnt=icnt+(xs[1])
#            print(isum,xs[1],(xs[1]),icnt)

print(icnt-1)

Submission status: Time Limit Exceeded

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

#n=4
#a=8
#x=[7,9,8,9]

#n=8
#a=5
#x=[3,6,2,8,7,6,5,9]

for i in range(n):
    x[i]=x[i]-a
    
n2=n//2
n3=n-n2

y=[]
for i in range(n3):
    y.append(x[i+n2])

# itertools 使用 bit全探索
import itertools

xsum=[]
for i in itertools.product([0,1], repeat=n2):
    isum=0
    for ii in range(n2):
        if i[ii]==0:
            isum=isum+x[ii]
    xsum.append(isum)
    
icnt=0
for ix in range(len(xsum)):
    for i in itertools.product([0,1], repeat=n3):
        isum=0
        for ii in range(n3):
            if i[ii]==0:
                isum=isum+y[ii]
#        print(isum,xsum[ix])
        if isum==-xsum[ix]:
            icnt=icnt+1

print(icnt-1)

Submission status: Time Limit Exceeded

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

for i in range(n):
    x[i]=x[i]-a
    
# itertools 使用 bit全探索
import itertools
icnt=0
for i in itertools.product([0,1], repeat=n):
    isum=0
    for ii in range(n):
#        if i[ii]==0:
        isum=isum+x[ii]*i[ii]
    if isum==0:
        icnt=icnt+1

print(icnt-1)