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: Wrong Answer

Solution code:
import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = xs[:l], r - l, xs[r:]
if len(low) > len(high):
    low, high = list(map(neg, high)), list(map(neg, low))
else:
    high = high[::-1]
acc = list(accumulate(high[::-1]))[::-1]

factor = 2 ** n0
lsums = sum((Counter(map(sum, combinations(low, 1 + i))) for i in range(len(low))), Counter())

ans = 0
for lsum, cnt in lsums.items():
    tmp = 0
    q = deque()
    q.append((0, max(lsum, -lsum - acc[0])))
    while len(q) > 0:
        i, v = q.popleft()
        if i + 1 < len(high) and v + acc[i + 1] >= 0:
            q.append((i + 1, v))
        if i >= len(high):
            continue
        v += high[i]
        if v == 0:
            tmp += 1
            continue
        if v < 0:
            q.append((i + 1, v))
    ans += tmp * cnt

ans *= factor
ans += 2 ** n0 - 1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = xs[:l], r - l, xs[r:]
if len(low) > len(high):
    low, high = list(map(neg, high)), list(map(neg, low))
else:
    high = high[::-1]
acc = list(accumulate(high[::-1]))[::-1]
highrev = high[::-1]

factor = 2 ** n0
lsums = sum((Counter(map(sum, combinations(low, 1 + i))) for i in range(len(low))), Counter())

ans = 0
for lsum, cnt in lsums.items():
    tmp = 0
    q = deque()
    val = max(lsum, -lsum - acc[0])
    pos = len(high) - bisect.bisect_right(highrev, -val)
    q.append((pos, val))
    while len(q) > 0:
        i, v = q.popleft()
        if i >= len(high):
            continue
        if v + acc[i] < 0:
            continue
        q.append((i + 1, v))
        v += high[i]
        if v == 0:
            tmp += 1
            continue
        if v > 0:
            continue
        q.append((i + 1, v))
    ans += tmp * cnt

ans *= factor
ans += 2 ** n0 - 1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = xs[:l], r - l, xs[r:]
if len(low) > len(high):
    low, high = list(map(neg, high)), list(map(neg, low))
else:
    high = high[::-1]
acc = list(accumulate(high[::-1]))[::-1]

factor = 2 ** n0
lsums = sum((Counter(map(sum, combinations(low, 1 + i))) for i in range(len(low))), Counter())

ans = 0
for lsum, cnt in lsums.items():
    tmp = 0
    q = deque()
    q.append((0, max(lsum, -lsum - acc[0])))
    while len(q) > 0:
        i, v = q.popleft()
        if i >= len(high):
            continue
        if v + acc[i] < 0:
            continue
        q.append((i + 1, v))
        v += high[i]
        if v == 0:
            tmp += 1
            continue
        if v > 0:
            continue
        q.append((i + 1, v))
    ans += tmp * cnt

ans *= factor
ans += 2 ** n0 - 1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = list(map(neg, xs[:l])), r - l, xs[r:]
if len(low) > len(high):
    low, high = high, low
else:
    high = high[::-1]
acc = list(accumulate(high[::-1]))[::-1]

factor = 2 ** n0
lsums = sum((Counter(map(sum, combinations(low, 1 + i))) for i in range(len(low))), Counter())

ans = 0
for lsum, cnt in lsums.items():
    q = deque()
    q.append((0, 0))
    while len(q) > 0:
        i, v = q.popleft()
        if v == lsum:
            ans += 1
            continue
        if i >= len(high):
            continue
        if v > lsum:
            continue
        if v + acc[i] < lsum:
            continue
        q.append((i + 1, v))
        q.append((i + 1, v + high[i]))

ans *= factor
if n0:
    ans += (2 ** n0 - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = list(map(neg, xs[:l])), r - l, xs[r:]
if len(low) > len(high):
    low, high = high, low[::-1]
acc = list(accumulate(high[::-1]))[::-1]

factor = 2 ** n0
lsums = sum((Counter(map(sum, combinations(low, 1 + i))) for i in range(len(low))), Counter())

ans = 0
for lsum, cnt in lsums.items():
    q = deque()
    q.append((0, 0))
    while len(q) > 0:
        i, v = q.popleft()
        if v == lsum:
            ans += 1
            continue
        if i >= len(high):
            continue
        if v > lsum:
            continue
        if v + acc[i] < lsum:
            continue
        q.append((i + 1, v))
        q.append((i + 1, v + high[i]))

ans *= factor
if n0:
    ans += (2 ** n0 - 1)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    t = input().split(" ")
    N, A= int(t[0]), int(t[1])

    t = input().split(" ")
    x_p = []
    x_n = []
    x_z = 0
    for i in t:
        i = int(i)
        if A < i:
            x_p.append(i - A)
        elif i < A:
            x_n.append(A - i)
        else:
            x_z += 1
    x_p.sort()
    x_n.sort()
    x_p_sum=[{0:1}]
    x_n_sum=[{0:1}]
    for i in range(len(x_p)):
        x_p_sum.append({})
        for j in x_p_sum[i]:
            if j in x_p_sum[i+1]:
                x_p_sum[i+1][j] += x_p_sum[i][j]
            else:
                x_p_sum[i+1][j] = x_p_sum[i][j]
            x_p_sum[i+1][j+x_p[i]] = x_p_sum[i][j]
    for i in range(len(x_n)):
        x_n_sum.append({})
        for j in x_n_sum[i]:
            if j in x_n_sum[i+1]:
                x_n_sum[i+1][j] += x_n_sum[i][j]
            else:
                x_n_sum[i+1][j] = x_n_sum[i][j]
            x_n_sum[i+1][j+x_n[i]] = x_n_sum[i][j]
    sum = 0
    for i in x_n_sum[-1]:
        if i in x_p_sum[-1]:
            sum += (x_n_sum[-1][i] * x_p_sum[-1][i])
    sum *= 2**x_z
    sum -= 1
    print(sum)
main()

Submission status: Wrong Answer

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

xa = []
xb = []
count = 0
for i in x:
    if i > a:
        xa.append(i-a)
    elif i < a:
        xb.append(i-a)
    else:
        count += 1
ans = 0
if len(xa) == 0 or len(xb) == 0:
    print(2**count-1)
else:
    for i in range(1,len(xa)+1):
        for j in range(1,len(xb)+1):
            for k in itertools.combinations(xa,i):
                for l in itertools.combinations(xb,j):
                    if sum(k)+sum(l) == 0:
                        ans += 1
    if ans == 0:
        print(0)
    else:
        print((ans+1)*2**count-count)

Submission status: Wrong Answer

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

xa = []
xb = []
count = 0
for i in x:
    if i > a:
        xa.append(i-a)
    elif i < a:
        xb.append(i-a)
    else:
        count += 1
ans = 0
if len(xa) == 0 or len(xb) == 0:
    print(count ** 2)
else:
    for i in range(1,len(xa)+1):
        for j in range(1,len(xb)+1):
            for k in itertools.combinations(xa,i):
                for l in itertools.combinations(xb,j):
                    if sum(k)+sum(l) == 0:
                        ans += 1
    print((ans+1)*2**count-count)

Submission status: Wrong Answer

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

MX = max(X+[0])

dp = [[0 for i in range(2*MX*N+1)] for _ in range(N+1)]

for i in range(N+1):
    for t in range(2*MX*N+1):
        if i==0 and t==N*MX:
            dp[i][t] = 1
        elif i>=1:
            if t-X[i-1]>=0 and t-X[i-1]<=2*MX*N:
                dp[i][t] = dp[i-1][t]+dp[i-1][t-X[i-1]]
            else:
                dp[i][t] = dp[i-1][t]
        else:
            dp[i][t] = 0
    
print(dp[N][N*MX]-1)
print("\n".join([str(d) for d in dp]))

Submission status: Wrong Answer

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

for i in range(1,N+1):
    tot = [0]*(N-i+1)
    for j in range(N-i+1):
        if j == 0:
            tot[j] = sum([x[k] for k in range(i)])
        else:
            tot[j] = tot[j-1] + x[j+-1] - x[j-1]
    a = a + [k/i for k in tot]

count = 0
print(sum([1 if i == A else 0 for i in a]))

Submission status: Wrong Answer

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
y=[]
for i in x:
  y.append(i-a)
s=2*n*a
dp=[[0 for i in range(s+1)] for j in range(n+1)]
dp[0][n*a]=1
for i in range(n):
  for j in range(s+1):
    x=j-y[i]
    if(0<=x and x<=2*n*a):
      dp[i+1][j]=dp[i][j-y[i]]+dp[i][j]
    else:
      dp[i+1][j]=dp[i][j]

print(dp[n][n*a])

Submission status: Wrong Answer

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

maxi = 0
for i in range(n):
    maxi = max(maxi, x[i])
maxi = max(maxi, a)

dp = [[[0 for i in range(maxi * n + 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):
    for j in range(0, n + 1):
        for s in range(maxi * n):
            if j > i:
                continue
            if (i == 0) & (j == 0) & (s == 0):
                continue
            if (i > 0) & (s < x[i]):
                dp[i][j][s] = dp[i - 1][j][s]
            elif (i > 0) & (j > 0) & (s >= x[i]):
                dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - x[i]]

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

print(sum)

Submission status: Wrong Answer

Solution code:
import itertools

N,A = map(int, input().split())
x = list(map(int, input().split()))
result = 0
for i in range(1, (len(x)+1 if N == 1 else len(x)) ):
	for j in itertools.combinations(x, i):
		if sum(j)/len(j) == A:
			result += 1
 
print(result)

Submission status: Wrong Answer

Solution code:
import itertools

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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**9

def f():
    n,a = list(map(int, input().split()))
    x = list(map(int, input().split()))
    x.sort()
    b = [(a-_) for _ in x if _ < a]
    c = [0 for _ in x if _ == a]
    d = [(_-a) for _ in x if _ > a]
    m = 50
    ba = [0]*(m+1)
    ba[0] = 1
    for bi in b:
        for j in range(m-bi,-1,-1):
            ba[j+bi] += ba[j]
    da = [0]*(m+1)
    da[0] = 1
    for di in d:
        for j in range(m-di,-1,-1):
            da[j+di] += da[j]
    r = -1
    for i in range(m+1):
        r += ba[i] * da[i]
    cl = len(c)
    cr = 2**cl - 1
    return r * (cr+1) + cr

print(f())

Submission status: Wrong Answer

Solution code:
import numpy as np

N, A = map(int, input().split())
xs = np.array(list(map(int, input().split()))) - A

dp = np.zeros((50*50*2+1, N+1), dtype=np.int64)
dp[50,0] = 1

for i, x in enumerate(xs):
    dp[:,i+1] = dp[:,i]
    dp[max(0,x):min(len(dp),len(dp)+x),i+1] += dp[max(0,-x):min(len(dp),len(dp)-x),i]

print(dp[50,N]-1)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n,a = ii()
x = ii()
ans=0

def dp(i,b,c):
    if i<0:
        return 0
    elif b>i+1:
        return 0
    elif b==1:
        return x[0:i+1].count(c)
    else:
        return dp(i-1,b,c)+dp(i-1,b-1,c-x[i])
        
for j in range(n):
    ans+=dp(n-1,j,a*j)

print ans

Submission status: Wrong Answer

Solution code:
#coding: utf-8                                                                                                                                              

N, A = map(int, raw_input().split())
x = map(int, raw_input().split())
count = 0
if N>16:
    print 0

else:
    for bi in xrange(1, 2**N):
        b = str(bin(bi))[2:].zfill(N)
        s = 0.0
        for (i, a) in enumerate(b):
            if a == '1':
                s += x[i]
        if s/b.count('1') == A:
            count += 1
            #print b                                                                                                                                        
    print count

Submission status: Wrong Answer

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

if N >= 17:
    exit()

ans = 0
for i in range(1, N + 1):
    combs = combinations(range(N), i)
    for comb in combs:
        temp = sum([X[c] for c in comb])
        if temp == A * i:
            ans += 1
print(ans)

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(2**N):
    b = [i>>j&1 for j in range(N)]
    sum = 0
    count = 0
    for j in range(N):
        if b[j] == 1:
            sum += x[j]
            count += 1
    if count > 0 and sum%count==0 and sum // count == A:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

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,1<<n):
  c=0
  s=0
  for j in range(n):
    if (i>>j)&1==1:
      c+=1
      s+=x[j]
  if s==c*a:
    ans+=1
print(ans)

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):
    li=list(combinations(x,i))
    for d in li:
        if sum(d)==a*i:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

dp = [list( [0 for _ in range(10**4)] for _ in range(n+1)) for _ in range(n+1)]
dp[0][0][0] = 1


for i in range(n):
    for k in range(n):
        for s in range(sum(x)+1):
                dp[i+1][k][s] += dp[i][k][s]
                dp[i+1][k+1][s+x[i]] += dp[i][k][s]

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

Submission status: Time Limit Exceeded

Solution code:
MAX=2500
n,a=map(int,input().split())
x=list(map(int,input().split()))
# dp[i][j][k] := x[0:i]のカードからj枚とって合計がkとなる取り方の数
dp = [[[0] * (MAX+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(0,n+1):
    for k in range(0, MAX+1):
      dp[i+1][j][k] += dp[i][j][k] # i番目のカードを取らない
  for j in range(0,n):
    for k in range(0, MAX+1-x[i]):
      dp[i+1][j+1][k+x[i]] += dp[i][j][k] # i番目のカードを取る

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, A = in_nn()
    X = in_nl()

    for i in range(N):
        X[i] -= A

    N1 = N // 2
    N2 = N - N1

    comb1 = itertools.product(range(2), repeat=N1)
    comb2 = itertools.product(range(2), repeat=N2)

    d1 = defaultdict(int)
    d2 = defaultdict(int)

    for comb in comb1:
        sum = 0
        for i, c in enumerate(comb):
            if c == 1:
                sum += X[i]
        d1[sum] += 1

    for comb in comb2:
        sum = 0
        for i, c in enumerate(comb):
            if c == 1:
                sum += X[N1 + i]
        d2[sum] += 1

    ans = 0
    for k, v in d1.items():
        ans += v * d2[-k]

    ans -= 1
    print(ans)


if __name__ == '__main__':
    main()

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] -= a
ans = 0
for i in range(1,2**n):
    b,t,j = i,0,0
    while b > 0:
        if b % 2 != 0:
            t += x[j]
        b = b // 2
        j += 1
    if t == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,ave = map(int,input().split())
card_ls = list(map(int, input().split()))
#dp[i+1][n][s] := i番目までのカード(0idx)からn枚使って合計がsとなるパターンの数
dp = [[[0]*(ave*N+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for n in range(N):
        for s in range(ave*N+1):
            # i番目を新しく使う
            if s+card_ls[i] < ave*N+1:
                dp[i+1][n+1][s+card_ls[i]] += dp[i][n][s]
            # i番目を使わない
            dp[i+1][n][s] += dp[i][n][s]

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

Submission status: Time Limit Exceeded

Solution code:

import itertools
import math

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

ans = 0
for card_set in itertools.product([True, False], repeat=n):
    card_num = 0
    card_sum = 0
    for ni in range(n):
        if card_set[ni]:
            card_num += 1
            card_sum += x[ni]
    if card_num > 0:
        if card_sum == card_num * 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[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0]*(a*n+1) for k in range(n+1) ] for j in range(n)]

dp[0][0][0] = 1
if x[0]<= a*n:
    dp[0][1][x[0]] = 1
    
for j in range(n-1):
    for k in range(n+1):
        for s in range(a*n+1):
            if k == 0 and s == 0:
                dp[j+1][k][s] = 1
            elif k>j+2:
                dp[j+1][k][s]=0
            elif s>=x[j+1] and k>= 1:
                dp[j+1][k][s]=dp[j][k][s] + dp[j][k-1][s-x[j+1]]
            else:
                dp[j+1][k][s]=dp[j][k][s]

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
# ARC060A

import itertools

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

# n, a = 33, 3
# x = [3] * 33

count = 0
bin = list(itertools.product([0, 1], repeat=n))
for i in bin:
    s = 0
    m = sum(i)
    if m:
        for j in range(n):
            if i[j] == 1:
                s += x[j]
        # print(s, i)
        if s / m == a:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, A, *x = map(int, open(0).read().split())
dp = [[[0]*(3000) for _ in range(55)] for _ in range(55)]
dp[0][0][0] = 1

for j in range(N+1):
    for k in range(N+1):
        for s in range(N*A+1):
            if j >= 1:
                dp[j][k][s] += dp[j-1][k][s]  # 選ばない場合
                if k >= 1 and s >= x[j-1]:
                    dp[j][k][s] += dp[j-1][k-1][s-x[j-1]]  # 選ぶ場合
ans = 0
for k in range(1, N+1):
    ans += dp[N][k][k*A]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    # dp[i][k][s] := i個までみて，それまでにk選んでて，そのときの総和がsとなる物の総数
    dp = [[[0] * (N * A + 1) for _ in range(N + 1)] for _ in range(N + 1)]

    dp[0][0][0] = 1
    for i in range(N):
        for k in range(N):
            for s in range(N * A + 1):
                # 使わない
                dp[i + 1][k][s] += dp[i][k][s]

                # 使う
                if s + X[i] <= N * A:
                    dp[i + 1][k + 1][s + X[i]] += dp[i][k][s]

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0 for i in range(2501)] for j in range(n+1)] for k in range(n+1)]
#dp[i][j][k]:=i枚目まで見てj枚選んで和がkとなるようなカードの取り方の数
dp[0][0][0]=1
for i in range(n):
    see=x[i]
    for j in range(i+2):
        for k in range(2501):
            dp[i+1][j][k]+=dp[i][j][k]
            if see>k or j==0:continue
            dp[i+1][j][k]+=dp[i][j-1][k-see]
ans=0
for i in range(1,n+1):
    ans+=dp[-1][i][i*a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


def main():
    N, X = read_values()
    A = read_list()

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

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

    for i, a in enumerate(A):
        for j in range(N + 1):
            for k in range(N * X):
                if k + a <= N * X and j < N:
                    dp[i + 1][j + 1][k + a] += dp[i][j][k]
                dp[i + 1][j][k] += dp[i][j][k]
    
    res = 0
    for i in range(1, N + 1):
        res += dp[N][i][i * X]

    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1<<n):
    sum1 = 0
    cnt = 0
    for j in range(n):
        if i>>j&1:
            cnt +=1
            sum1 +=L[j]
    if cnt != 0:
        if sum1/cnt == a:
            ans +=1
print(ans)

Submission status: Time Limit Exceeded

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

    # x.insert(0, 0)

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

    for i in range(1, N + 1):
        for j in range(1, i + 1):
            for k in range(1, N * A + 1):
                dp[i][j][k] = dp[i - 1][j][k]
                if k >= x[i - 1]:
                    dp[i][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:
if __name__ == '__main__':
    N, A = map(int, input().split())
    x = list(map(int, input().split()))

    x.insert(0, 0)

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

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

    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()))
 
dp = [[[0 for k in range(2501)] for j in range(N+1)] for i in range(N+1)]
 
for i in range(1,N+1):
    x = X[i-1]
    dp[i][1][x] += 1
    for j in range(1,i+1):
        for k in range(1,2501):
            if k-x > 0:
                dp[i][j][k] += dp[i-1][j-1][k-x] + dp[i-1][j][k]
            else:
                dp[i][j][k] += dp[i-1][j][k]
 
ans = 0
 
for j in range(1,N+1):
    ans += dp[N][j][j*A]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, a = map(int, input().split())
    x = [int(x) for x in input().split()]
    answer = 0
    for i in range(1, pow(2, n)):
        count_1 = 0
        now_sum = 0
        for j in range(n):
            if (i >> j) & 1:
                count_1 += 1
                now_sum += x[j]
        if a * count_1 == now_sum:
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp = [[[0] * 2501 for j in range(51)] for i in range(51)]

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

for i in range(n):
    for j in range(51):
        for k in range(2501):
            if k >= l[i] and j >= 1:
                dp[i+1][j][k] = dp[i][j][k] + dp[i][j-1][k-l[i]]
            else:
                dp[i+1][j][k] = dp[i][j][k]

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

Submission status: Time Limit Exceeded

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

j = n
k = n
t = n * a



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

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

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

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

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

print(count)

Submission status: Time Limit Exceeded

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

j = n
k = n
t = n * a



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

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

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

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

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

print(count)