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:
import itertools as iter

N, A = list(map(int, input().split())) # N枚のカード 整数の平均A

card_list = list(map(int, input().split()))

# 1からNまでの個数の全ての組み合わせ
ncr = [n for n in range(1, N+1)]

match = 0

for r in ncr:
    # print("{}個の組み合わせ".format(r))
    comb_list = list(iter.combinations(card_list, r))
    m = A * r
    # print(comb_list)
    for t in comb_list:
        # print("{} => 平均:{} ".format(t, sum(t) / r))
        if sum(t) == m:
            match += 1

print(match)

Submission status: Time Limit Exceeded

Solution code:
import itertools as iter

N, A = list(map(int, input().split())) # N枚のカード 整数の平均A

card_list = list(map(int, input().split()))

# 1からNまでの個数の全ての組み合わせ
ncr = [n for n in range(1, N+1)]

match = 0

for r in ncr:
    # print("{}個の組み合わせ".format(r))
    comb_list = list(iter.combinations(card_list, r))
    # print(comb_list)
    for t in comb_list:
        # print("{} => 平均:{} ".format(t, sum(t) / r))
        if sum(t) / r == A:
            match += 1

print(match)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools

def solve(N: int, A: int, x: "List[int]"):
    X = max(x)
    dp = [[[0 for _ in range(max(N*X+1, N*A+1))] for _ in range(N+1) ] for _ in range(N+1)]
    dp[0][0][0] = 1
    for n in range(N+1):
        for m in range(N+1):
            for k in range(N*X+1):
                if n >= 1 and k < x[n-1]:
                    dp[n][m][k] = dp[n-1][m][k]
                elif n >= 1 and m >= 1 and k >= x[n-1]:
                    dp[n][m][k] = dp[n-1][m][k] + dp[n-1][m-1][k-x[n-1]]
    s = 0
    for i in range(1, N+1):
        s += dp[N][i][i*A]
    print(s)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    x = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A, x)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
N,A=list(map(int, input().split()))
X=list(map(int, input().split()))

count=0

for i in range(1, N+1):
    Y=list(itertools.combinations(X, i))
    Z=[np.mean(Y[j]) for j in range(len(Y))]
    for x in Z:
        if x==A:
            count+=1
        else: pass
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
"""解説
dp[j][k][s] := x1,...,xjから k枚選んで xiの合計をsにするような選び方の総数

[@lilium氏]
https://atcoder.jp/contests/abc044/submissions/5887235
"""

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

    max_x = max(X)
    dp = [[[0 for _ in range(4000+1)] for __ in range(N+1)] for ___ in range(N+1)]

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

    # dp[i][j][k] := i枚のうちj枚を選んで、和がkになる組み合わせ
    """
    dp[i][j][k] := i枚のうち、k枚のカードを選んで、選んだカードの総和がkになる選び方の総数
    i: i枚目のカード
    j: j枚のカードを選んだ
    k: 選んだカードの総和
    """
    for i in range(N):
        for j in range(N):
            for k in range(4000+1):
                if (k+X[i] < 4000+1) :
                    dp[i+1][j][k] += dp[i][j][k]  # i枚目を選ばなかった
                    dp[i+1][j+1][k+X[i]] += dp[i][j][k]  # i枚目を選んだ

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

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
x = list(map(int, input().split()))
dp = [[[0 for _ in range(2551)] for _ in range(51)] for _ in range(51)]

dp[0][0][0] = 1
for i in range(N):
    for k in range(i + 1):
        for t in range(2501):
            dp[i + 1][k][t] += dp[i][k][t]
            dp[i + 1][k + 1][t + x[i]] += dp[i][k][t]

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 = list(map(int, input().split()))
dp = [[[0 for _ in range(2501)] for _ in range(51)] for _ in range(51)]

dp[0][0][0] = 1
for i in range(1, N + 1):
    for k in range(i + 1):
        for t in range(2501):
            dp[i][k][t] = dp[i - 1][k][t]
            if t - x[i - 1] >= 0:
                dp[i][k][t] += dp[i - 1][k - 1][t - x[i - 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 = list(map(int, input().split()))
S = sum(x)
dp = [[[0 for _ in range(S + 1)] for _ in range(N + 1)] for _ in range(N + 1)]

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import itertools

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

ans = 0

# 違ったよーう！！！！
# nCr = {}

# 二項係数の公式 nCr = n-1Cr + n-1Cr-1
# 参考：
# https://qiita.com/kyoro1/items/c9c58496ad3dd798c665
# https://mathtrain.jp/stnum
# https://qiita.com/derodero24/items/91b6468e66923a87f39f#既存ツールを用いた手法３評価-

# def cmb(n,r):
#     if r == 0 or r == n:
#         return 1
#     if r == 1:
#         return n

#     if (n,r) in nCr:
#         return nCr[(n,r)]
#     nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
#     return nCr[(n,r)]

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


print(ans)

Submission status: Time Limit Exceeded

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

X = max(A, max(x))

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as c
ways = 0
N,A = list(map(int , input().split()))
l = list(map(int , input().split()))
for i in range(1,N+1):
  res = c(l,i)
  for i in res:
    if sum(i)/len(i) == A:
      ways+=1
print(ways)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
N, A = map(int, input().split())
x = list(map(int, input().split()))
dp = [[0] * (A*N+1) for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    _x = x[i]
    dpc = deepcopy(dp)
    for j in range(i+1):
        for a in range(A*N+1):
            if a >= _x:
                dp[j+1][a] += dpc[j][a-_x]
ans = 0
for i in range(1, N+1):
    ans += dp[i][i*A]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
n, a = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
t = 0
@lru_cache(maxsize=1024)
def dfs(i,ave):
    if i ==n:
        if ave == 0:
            return 1
        else:
            return 0

    return dfs(i+1,ave)+dfs(i+1,ave+x[i]-a)



print(dfs(0,0)-1)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
n, a = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
t = 0
@lru_cache(maxsize=1024)
def dfs(i,sum,v):
    if i == n:
        v = max(1,v)
        if sum/v == a:
            return 1
        else:
            return 0
    return dfs(i+1,sum,v)+dfs(i+1,sum+x[i],v+1)

print(dfs(0,0,0))

Submission status: Time Limit Exceeded

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

X = max(x)
if X < A:
    X = A

def check(j, k, s):
    if dp[j][k][s] != -1:
        return dp[j][k][s]
    if j == 0 and k == 0 and s == 0:
        dp[j][k][s] = 1
        return 1
    if j >= 1 and s < x[j-1]:
        a = check(j-1, k ,s)
        dp[j][k][s] = a
        return a
    if j >= 1 and k >= 1 and s >= x[j-1]:
        a = check(j-1, k, s) + check(j-1, k-1, s-x[j-1])
        dp[j][k][s] = a
        return a
    dp[j][k][s] = 0
    return 0
        
dp = [[[-1] * (N*X+1) for _ in range(N+1)] for _ in range(N + 1)]
dp = np.array(dp)
# print (dp)
# for j in range(N+1):
#     for k in range(N+1):
#         for s in range(N*X + 1):
#             print (j, k, s)
#             dp[j][k][s] = check(j, k, s)

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

print (ans)

Submission status: Time Limit Exceeded

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

count = 0
for i in range(2 ** N):
    tmp = 0
    card = 0
    for j in range(N):
        if (i>>j) &1:
            tmp += x[j]
            card += 1
    if A * card == tmp:
        # print (tmp, bin(i))
        count += 1

print (count-1) #0はAの倍数としてカウントされている

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

N, A = map(int, sys.stdin.readline().split())
x = list(map(int, sys.stdin.readline().split()))


count = 0
for i in range(1, N + 1):
    combi_list = itertools.combinations(x, i)
    for j in combi_list:
        mean = sum(j) / i
        if mean == A:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
count = 0
for i in range(2**n):
  bag = []
  for j in range(n):
    if (i>>j)&1:
      bag.append(j)

  s = 0
  for idx in bag:
    s += x[idx]
  if len(bag) != 0 and s / len(bag) == a:
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


n, k = map(int, input().split())

arr = list(map(int, input().split()))

arr = [x - k for x in arr]
arr.sort()

arr_minus = [-x for x in arr if x < 0]
arr_zero = sum(x==0 for x in arr)
arr_plus = [x for x in arr if x > 0]

minus_nums = defaultdict(int)

for i in range(1, 2 ** len(arr_minus)):
    bin_minus = "{:050b}".format(i)[::-1]
    item = sum(x for idx, x in enumerate(arr_minus) if bin_minus[idx] == "1")
    minus_nums[item] += 1

cnt = 0
for i in range(1, 2 ** len(arr_plus)):
    bin_plus = "{:050b}".format(i)[::-1]
    item = sum(x for idx, x in enumerate(arr_plus) if bin_plus[idx] == "1")
    cnt += minus_nums[item]

print((1 + cnt) * 2 ** arr_zero - 1)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    N, A = map(int, input().split(' '))
    X = list(map(int, input().split(' ')))
    #print(N,A)
    #print(X)
    count = 0
    
    for i in range(1 << N):
        card = []
        for j in range(N):
            if ((i >> j) & 1) == 1:
                card.append(X[j])
        #print(card)
        if len(card) >= 1:
            card_ave = sum(card) / len(card)
            if (card_ave == A):
                #print(card_ave)
                count += 1
    
    print(count)

Submission status: Time Limit Exceeded

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

result = 0
for i in range(2 ** N):
	temp, count = 0, 0
	for j, x in enumerate(X):
		if i >> j & 1:
			temp += x
			count += 1
	if count:
		if temp / count == A:
			result += 1
print(result)

Submission status: Time Limit Exceeded

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

ways = 0
def findNumOfWays(x, s, i, a, t):
	global ways
	try:
		if i >= len(x) or (s + x[i]) / (t + 1) > a:
			return
		else:
			if (s + x[i]) / (t + 1) == a:
				ways += 1
			elif (s + x[i]) / (t + 1) > a:
				return
			findNumOfWays(x, s + x[i], i + 1, a, t + 1)
			findNumOfWays(x, s, i + 1, a, t)
	except Exception as e:
		print(e)

	

findNumOfWays(x, 0, 0, a, 0)
print(ways)

Submission status: Time Limit Exceeded

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

XX = sum(X) + 1

dp = [[[0 for i in range(XX * 2)] for i in range(N + 3)] for i in range(N + 3)]

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, A, *x = map(int, open(0).read().split())

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

dp[0][0][0] = 1
for j in range(1, N + 1):
    for k in range(N + 1):
        for s in range(c_nx + 1):
            if s < x[j]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif s >= x[j]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j]]
                
print(sum(dp[N][k][k * A] for k in range(1, N + 1)))

Submission status: Time Limit Exceeded

Solution code:
N, A, *x = map(int, open(0).read().split())
max_sum = sum(x)
max_len = len(x)
ans = 0

for i in range(1, 2 ** max_len):
    l = list(map(int, '{0:0>{1:}b}'.format(i, max_len)))
    c = l.count(1)
    s = sum(i * j for i, j in zip(x, l))
    ans += int(s == A * c)
    
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
N, A = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(max(x), A)

dp = [[[0 for s in range(x_max * N + 1)]for n in range(N + 1)] for i in range(N + 1)]
dp[0][0][0] = 1

for i, n, s in product(range(1, N + 1), range(N + 1), range(x_max * N + 1)):
    if s < x[i - 1]:
        dp[i][n][s] = dp[i - 1][n][s]
    elif 0 < n and x[i - 1] <= s:
        dp[i][n][s] = dp[i - 1][n][s] + dp[i - 1][n - 1][s - x[i - 1]]

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
N, A = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(max(x), A)

dp = [[[0 for s in range(x_max * (N + 1))] for n in range(N + 1)] for i in range(N + 1)]
dp[0][0][0] = 1

for i, n, s in product(range(1, N + 1), range(N + 1), range(x_max * (N + 1))):
    if s < x[i - 1]:
        dp[i][n][s] = dp[i - 1][n][s]
    elif 0 < n and x[i - 1] <= s:
        dp[i][n][s] = dp[i - 1][n][s] + dp[i - 1][n - 1][s - x[i - 1]]

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

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)
x_sum = sum(x)
ans = 0
if x_max >= a:
    dp = [[[0 for k in range(x_sum + 1)] for j in range(n + 1)] for i in range(2)]
    dp[0][0][0] = 1
    for i in range(1, n + 1):
        idx = i % 2
        for j in range(n + 1):
            for k in range(x[i - 1]):
                dp[idx][j][k] = dp[1 - idx][j][k]
            if j > 0:
                for k in range(x[i - 1], x_sum + 1):
                    dp[idx][j][k] = dp[1 - idx][j][k] + dp[1 - idx][j - 1][k - x[i - 1]]

    for j in range(1, min(x_sum // a + 1, n + 1)):
        ans += dp[idx][j][j * a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, a = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)
x_sum = sum(x)
if x_max < a:
    print(0)
else:
    dp = np.zeros([n + 1, n + 1, x_sum + 1], dtype=int)
    dp[0, 0, 0] = 1
    for i in range(1, n + 1):
        for j in range(n + 1):
            for k in range(x[i - 1]):
                dp[i, j, k] = dp[i - 1, j, k]
            if j > 0:
                for k in range(x[i - 1], x_sum + 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, min(x_sum // a + 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_max = max(x)
x_sum = sum(x)
if x_max < a:
    print(0)
else:
    dp = [[[0 for k in range(x_sum + 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(n + 1):
            for k in range(x[i - 1]):
                dp[i][j][k] = dp[i - 1][j][k]
            if j > 0:
                for k in range(x[i - 1], x_sum + 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, min(x_sum // a + 1, n + 1)):
        ans += dp[-1][j][j * a]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from statistics import mean
n,a = map(int,input().split())
x = list(map(int, input().split()))

countM = 0

for L in range(1, len(x)+1):
  for subset in itertools.combinations(x, L):
    if mean(subset) == a:
      countM += 1
      
print(countM)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

dp = [[[0 for _ in range(a * 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(a * n + 1):
            dp[i][j][k] = dp[i-1][j][k]
            if j > 0 and k - xs[i-1] >= 0:
                dp[i][j][k] += dp[i-1][j-1][k-xs[i-1]]


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

print(c)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

count = 0
for i in range(1, n+1):
    for c in itertools.combinations(xs, i):
        if sum(c) == a * i:
            count += 1

print(count)

Submission status: Time Limit Exceeded

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

from collections import deque
stack1=deque([0])
stack2=deque([0])
cnt=0

for j in range(N):
    for i in range(len(stack1)):
        val1=stack1[i]
        val2=stack2[i]
        stack1.append(val1+x[j])
        stack2.append(val2+1)
        
for i in range(len(stack1)):
    if stack2[i] !=0:
        if stack1[i]/stack2[i]==A:
            cnt+=1
#print(stack1)
#print(stack2)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,a,*x=map(int,open(0).read().split())
  x=[0]+x
  dp=[[[0]*(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):
    dp[i][0]=dp[i-1][0]
    for j in range(1,n+1):
      for k in range(1,50*n+1):
        dp[i][j][k]=dp[i-1][j][k]
        if k-x[i]>=0:
          dp[i][j][k]+=dp[i-1][j-1][k-x[i]]
  ans=0
  for i in range(1,n+1):
    j=i*a
    if j<50*n+2:
      ans+=dp[-1][i][j]
  print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n,a,*x=map(int,open(0).read().split())
x=[0]+x
dp=[[[0]*(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):
  dp[i][0]=dp[i-1][0]
  for j in range(1,n+1):
    for k in range(1,50*n+1):
      dp[i][j][k]=dp[i-1][j][k]
      if k-x[i]>=0:
        dp[i][j][k]+=dp[i-1][j-1][k-x[i]]
ans=0
for i in range(1,n+1):
  j=i*a
  if j<50*n+2:
    ans+=dp[-1][i][j]
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
ans = 0
def dfs(sum, cnt, num):
    global ans
    if cnt==n:
        if num!=0 and sum/num==a:
            ans = ans + 1
        return 1
    dfs(sum+x[cnt],cnt+1,num+1)
    dfs(sum,cnt+1,num)
    return 1
dfs(0,0,0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
arr=list(map(int,input().split()))
x=max(arr)
x=max(x,a)
dp=[[[0 for i in range(n*x+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  xi=arr[i-1]
  for j in range(n+1):
    for k in range(n*x+1):
      if k<xi:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        if j>=1:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-xi]
ans=0
for i in range(1,n+1):
  ans+=dp[n][i][i*a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools, random
from collections import deque
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 7)
ans = 0
tmp = 0
inf = 10 ** 20
INF = float("INF")
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
ddn9 = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n, a = wi()
x = wi()
X = max(x)
dp = [[[0] * (n + 1) for j in range(X * n + 2)] for i in range(n)]
dp[0][0][0] = 1
dp[0][x[0]][1] = 1

for p in range(1, n):
    for k in range(X * n + 2):
        for usenum in range(p + 1):
            dp[p][k][usenum] += dp[p - 1][k][usenum]
            if k - x[p] >= 0:
                dp[p][k][usenum + 1] += dp[p - 1][k - x[p]][usenum]

for k in range(X * n + 2):
    for usenum in range(n + 1):
        if usenum != 0:
            if k / usenum == a:
                ans += dp[n - 1][k][usenum]
print(ans)

Submission status: Time Limit Exceeded

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

import itertools

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

Submission status: Time Limit Exceeded

Solution code:
N,A = map(int,input().split())
*X, = map(int,input().split())
dp=[[[0]*2510 for _ in [0]*(N+10)] for _ in [0]*(N+10)]
for n in range(0,N+1):dp[n][0][0] = 1
for n in range(1,N+1):
    x = X[n-1]
    for k in range(1,n+1):
        for s in range(2501):
            dp[n][k][s] = dp[n-1][k][s]
            if s>=x:
                dp[n][k][s] += dp[n-1][k-1][s-x]
print(sum(dp[N][k][k*A] for k in range(1,N+1)))

Submission status: Time Limit Exceeded

Solution code:
import itertools


def how_many(A, cards):
    count = 0
    for r in range(1, len(cards)+1):
        for values in gen_combination(cards, r):
            if sum(values) / r == A:
                count += 1
    return count


def gen_combination(cards, r):
    for values in itertools.combinations(cards, r):
        yield values
        

def main():
    N, A = (int(i) for i in input().split())
    cards = [int(i) for i in input().split()]
    print(how_many(A, cards))

main()

Submission status: Time Limit Exceeded

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

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


def dfs(total, cnt, idx):
  
  #末尾まで確認した
  if idx == len(x):
    if cnt != 0:
      return 1 if total / cnt == A else 0
    else:
      return 0
  
  ret = 0
  
  ret += dfs(total + x[idx], cnt+1, idx+1)
  ret += dfs(total, cnt, idx+1)
  
  return ret
      
  
ans = dfs(0, 0, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def D2NC(D: int, N: int, link=False) -> list:
    alp = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    res = []
    while D > 0:
        if D % N > 9:
            tmp = alp[D % N - 10]
            res.insert(0, str(tmp))
        else:
            res.insert(0, str(D % N))
        D //= N
    if not res:
        res.append('0')
    if link:
        res = ''.join(res)
    return res


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

minus = [-i for i in x if i < 0]
plus = [i for i in x if i > 0]
zero = [i for i in x if i == 0]

if minus and plus:
    if sum(minus) <= sum(plus):
        n = len(minus)
        ct = 0
        for i in range(1, 2**n):
            combi = D2NC(i, 2, link=True).zfill(n)
            Sum, idx = 0, 0
            for j in combi:
                if j == '1':
                    Sum += minus[idx]
                idx += 1
            for j in plus:
                if j == Sum:
                    ct += 1
            tmp = [j for j in plus if j < Sum]
            m = len(tmp)
            for j in range(1, 2**m):
                combi = D2NC(j, 2, link=True).zfill(m)
                Sum_p, idx = 0, 0
                for k in combi:
                    if k == '1':
                        Sum_p += tmp[idx]
                    if Sum_p > Sum:
                        break
                    idx += 1
                if Sum_p == Sum:
                    ct += 1
        if zero:
            ans = 2 ** len(zero) * ct + 2 ** (len(zero)) - 1
        else:
            ans = ct
    else:
        n = len(plus)
        ct = 0
        for i in range(1, 2**n):
            combi = D2NC(i, 2, link=True).zfill(n)
            Sum, idx = 0, 0
            for j in combi:
                if j == '1':
                    Sum += plus[idx]
                idx += 1
            for j in minus:
                if j == Sum:
                    ct += 1
            tmp = [j for j in minus if j < Sum]
            m = len(tmp)
            for j in range(1, 2**m):
                combi = D2NC(j, 2, link=True).zfill(m)
                Sum_p, idx = 0, 0
                for k in combi:
                    if k == '1':
                        Sum_p += tmp[idx]
                    if Sum_p > Sum:
                        break
                    idx += 1
                if Sum_p == Sum:
                    ct += 1
        if zero:
            ans = 2 ** len(zero) * ct + 2 ** (len(zero)) - 1
        else:
            ans = ct
else:
    if zero:
        ans = 2 ** len(zero) - 1
    else:
        ans = 0

print(ans)

Submission status: Time Limit Exceeded

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

def solve(N, A, X):
    count = 0
  
    for i in range(1<<N):
        bit = 0
        sum = 0
        for j in range(N):
            if((i>>j)&1):
                sum += X[j]
                bit += 1
        if(bit == 0):
            continue
        elif(sum/bit == A):
            count += 1
            
    print(count)
    
if __name__ == '__main__':
    N, A = map(int, input().split())
    X = [int(x) for x in input().split()]
    
    solve(N, A, X)

Submission status: Time Limit Exceeded

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

    ans = editorial_3d(N, A, X)
    # ans2 = editorial_2d(N, A, X)
    # assert ans == ans2
    if N <= 16:
        ans3 = part(N, A, X)
        assert ans == ans3

    print(ans)


def editorial_3d(N, A, X):
    """
    dp[N][N][sum]
    N枚の選択肢, N枚選ぶ, 合計値
    """
    max_sum = N * A
    dp = [[None] for _ in range(N+1)]
    for i in range(N+1):
        tmp = [[0] * (max_sum + 1) for _ in range(N+1)]
        dp[i] = tmp
    dp[0][0][0] = 1

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

                dp[i][j][k] = v

    ans = 0
    for j in range(1, N+1):
        if j * A <= max_sum:
            ans += dp[N][j][j * A]

    return ans


def editorial_2d(N, A, X):
    """TODO
    dp[N][sum]
    N枚の選択肢, 合計値
    """
    max_sum = N * A
    dp = [[0] * (2 * max_sum + 1) for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(1, N+1):
        for k in range(max_sum, 2 * max_sum + 1):
            v = dp[i-1][k]
            if k >= X[i-1] - A:
                v += dp[i-1][k - X[i] - A]

            dp[i][k] = v

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

    return ans


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

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

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

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

        return ans

    ans = rec(0, N)
    return ans


if __name__ == '__main__':
    main()