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()))
dp = [ [ [0]*2501 for i in range(51) ] for j in range(51) ]

def dfs(index,u,ss):
    global N,A,x,dp
    cu = bin(u).count("1")
    if dp[index][cu][ss] > 0:
        return dp[index][cu][ss]
    if index==N:
        s = 0.0
        d = 0
        for i in range(N):
            if (u>>i)&1:
                s += float(x[i])
                d += 1
        if d > 0:
            s /= d
            if s==float(A):
                return 1
        return 0
    else:
        dp[index][cu][ss] = dfs(index+1,u,ss) + dfs(index+1,u|(1<<index),ss+x[index])
        return dp[index][cu][ss]

print(dfs(0,0,0))

Submission status: Time Limit Exceeded

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

def dfs(index,u):
    global N,A,x
    if index==N:
        s = 0.0
        d = 0
        for i in range(N):
            if (u>>i)&1:
                s += float(x[i])
                d += 1
        if d > 0:
            s /= d
            if s==float(A):
                return 1
        return 0
    else:
        return dfs(index+1,u) + dfs(index+1,u|(1<<index))

print(dfs(0,0))

Submission status: Time Limit Exceeded

Solution code:
def count_up(N, A, x, check, card, total):
  if check == N:
    return 1 if card > 0 and card * A == total else 0
  else:
    return count_up(N, A, x, check+1, card+1, total+x[check]) + count_up(N, A, x, check+1, card, total)

def bad_method(N, A, x):
  print count_up(N, A, x, 0, 0, 0)

def well_method(N, A, x):
  dp = [[[1 for a in range(N*50)] for b in range(N+1)] for c in range(N+1)]
  for j in range(N+1):
    for k in range(N+1):
      for s in range(N*50):
        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

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

line = raw_input().split()
N = int(line[0])
A = int(line[1])
line = raw_input().split()
x = {}
for i in range(N):
  x[i] = int(line[i])

# bad_method(N, A, x)
well_method(N, A, x)

Submission status: Time Limit Exceeded

Solution code:
def count_up(N, A, x, check, card, total):
  if check == N:
    return 1 if card > 0 and card * A == total else 0
  else:
    return count_up(N, A, x, check+1, card+1, total+x[check]) + count_up(N, A, x, check+1, card, total)

def bad_method(N, A, x):
  print count_up(N, A, x, 0, 0, 0)

line = raw_input().split()
N = int(line[0])
A = int(line[1])
line = raw_input().split()
x = {}
for i in range(N):
  x[i] = int(line[i])

bad_method(N, A, x)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N, A = map(int, raw_input().split())
x = map(int, raw_input().split())
res = 0
for i in range(1, N+1):
    for ele in combinations(x, i):
        if sum(ele)*1.0/i == A:
            res += 1
print res

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, A = [int(i) for i in input().split()]
x = [int(i) - A for i in input().split()] 
# card num
count = 0
for i in range(1, N+1):
    # combination
    for element in itertools.combinations(x, i):
        #print(element)
        if sum(element) == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

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

L = list(map(lambda x: x-A, L))

c = -1

def f(s, seq):
    global c
    if len(seq) == 0:
        if s == 0:
            c += 1
    else:
        f(s+seq[0], seq[1:])
        f(s, seq[1:])

f(0, L)

print(c)

Submission status: Time Limit Exceeded

Solution code:
import itertools

line1 = raw_input()
line1_lst = line1.split()
line1_lst = [int(a) for a in line1_lst]
N = line1_lst[0]
A = line1_lst[1]

line2 = raw_input()
line2_lst = line2.split()
number_lst = [int(a) for a in line2_lst]


all_averages = []

for i in range(N):
    tmp_combis_lst = list(itertools.combinations(number_lst, (i + 1)))
    tmp_ave_lst = [0] * len(tmp_combis_lst)
    for j in range(len(tmp_combis_lst)):
        curr_ave = float(sum(tmp_combis_lst[j])) / len(tmp_combis_lst[j])
        tmp_ave_lst[j] = curr_ave
    all_averages.extend(tmp_ave_lst)

print all_averages.count(A)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,a = (int(s) for s in input().strip().split(' '))
x = sorted([int (s) for s in input().strip().split(' ')])
print(str(sum([1 for i in range(1,len(x)+1) for j in list(itertools.combinations(x,i)) if sum(j)/len(j) == a])))

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
x = list(map(int, input().split()))
y = [n - A for n in x]
p = [k for k in y if k > 0]
n = [k for k in y if k < 0]
z = y.count(0)
a = 2**z - 1

def c(n):
	i = n
	a = 0
	b = 0
	while i != 0:
		a += (i%2)*10**b
		b += 1
		i = int(i/2)
	return(a)

s = []
t = []
for i in range(1,2**len(p)):
	j = str(c(i))
	if len(j) < len(p):
		j = "0"*(len(p) - len(j)) + j
	s.append(j)

for i in range(1,2**len(n)):
	j = str(c(i))
	if len(j) < len(n):
		j = "0"*(len(n) - len(j)) + j
	t.append(j)

e = 0
for i in s:
	c = 0
	for u, j in enumerate(i):
		if j == "1":
			c += p[u]
	for k in t:
		d = c
		for m, l in enumerate(k):
			if l == "1":
				d += n[m]
		if d == 0:
			e += 1
a = a + e*(a+1)
print(a)

Submission status: Time Limit Exceeded

Solution code:
import re
import itertools


class IO_for_Contest(object):
    @staticmethod
    def my_input():
        # return raw_input()
        return input()

    @staticmethod
    def read_from_input():
        buf = IO_for_Contest.read_n_int(2)
        n = buf[0]
        a = buf[1]
        x = IO_for_Contest.read_n_int(n)
        return a, x

    @staticmethod
    def read_line():
        return IO_for_Contest.my_input().strip()

    @staticmethod
    def read_int():
        return int(IO_for_Contest.my_input().strip())

    @staticmethod
    def read_n_int(n):
        return list(map(
                    int,
                    re.split('\s+', IO_for_Contest.my_input().strip())))[: n]


def solve():
    buf = IO_for_Contest.read_from_input()
    a = buf[0]
    x = buf[1]
    print(think_ways_of_mean(x, a))


def think_ways_of_mean(x, a):
    count = 0
    for n in range(1, len(x) + 1):  # n cards
        for indice in itertools.combinations(list(range(len(x))), n):
            if mean(sublist(x, indice)) == a:
                count += 1
    return count


def sublist(numbers, indice):
    sub = []
    for i in indice:
        sub.append(numbers[i])
    return sub


def mean(numbers):
    return float(sum(numbers)) / max(len(numbers), 1)

if __name__ == '__main__':
    # doctest.testmod()
    solve()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

l = []

for i in range(1, len(x) + 1):
    for comb in combinations(x, i):
        l.append(comb)

result = 0
for j in l:
    if sum(j)/len(j) == float(A):
        result += 1

print(result)

Submission status: Time Limit Exceeded

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

# dp := x1, ... ,xjからk枚選んでxiの合計をｓにするような選び方の総数
dp = [[[0 for s in range(n * a + 1)] for k in range(n + 1)] for j in range(n + 1)]

for j in range(n + 1):
    dp[j][0][0] = 1

for j in range(1, n + 1):
    for k in range(1, j + 1):
        for s in range(1, n * a + 1):
            if s < x[j - 1]:
                # 新たに加えることができない場合
                dp[j - 1][k][s] = dp[j - 2][k][s]
            elif s >= x[j - 1]:
                tmp_s = s - x[j - 1]
                dp[j - 1][k][s] = dp[j - 2][k][s] + dp[j - 2][k - 1][tmp_s]

count = 0
for k in range(1, n + 1):
    count += dp[n - 1][k][k * a]
print(count)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

n,a=map(int,raw_input().split())
x=map(int,raw_input().split())

el_plus = []
el_minus = []
sum_plus_dict = {"def":None}
sum_minus_dict = {"def":None}

x = [el - a for el in x]
count_zero = 0
count = 0

for i in range(len(x)):
    if x[i] > 0:
       el_plus.append(x[i])
    elif x[i] < 0:
        el_minus.append(x[i])
    else:
        count_zero += 1

if (el_plus == [] or el_minus == []):
    if count_zero==0:
        print 0
    else:
        print pow(2, count_zero) - 1
else:
    for i in range(len(el_minus)):
        el_minus[i] = el_minus[i] * (-1)
    dict_max = max(sum(el_plus), sum(el_minus))
    dict_min = min(sum(el_plus), sum(el_minus))
    for i in range(1, dict_max+1):
        sum_plus_dict.update({i:0})
        sum_minus_dict.update({i:0})

    for i in range(1, len(el_plus)+1,):
        comb_sum_plus = combinations(el_plus, i)
        for comb in comb_sum_plus:
            sum_plus = sum(list(comb))
            sum_plus_dict[sum_plus] += 1

    for i in range(1, len(el_minus)+1):
        comb_sum_minus = combinations(el_minus, i)
        for comb in comb_sum_minus:
            sum_minus = sum(list(comb))
            sum_minus_dict[sum_minus] += 1

    for key in range(1, dict_min+1):

       count += sum_plus_dict[key] * sum_minus_dict[key] * pow(2, count_zero)
    count += pow(2, count_zero)-1
    print count

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
 
n,a=map(int,raw_input().split())
x=map(int,raw_input().split())
 
el_plus = []
el_minus = []
sum_plus_dict = {"def":None}
sum_minus_dict = {"def":None}
 
x = [el - a for el in x]
count_zero = 0
count = 0
 
for i in range(len(x)):
    if x[i] > 0:
       el_plus.append(x[i])
    elif x[i] < 0:
        el_minus.append(x[i])
    else:
        count_zero += 1

if (el_plus == [] or el_minus == []):
    if count_zero==0:
        print 0
    else:
        print pow(2, count_zero) - 1
else:
    for i in range(len(el_minus)):
        el_minus[i] = el_minus[i] * (-1)
    dict_max = max(sum(el_plus), sum(el_minus))
    dict_min = min(sum(el_plus), sum(el_minus))
    for i in range(1, dict_max+1):
        sum_plus_dict.update({i:0})
        sum_minus_dict.update({i:0})
 
    for i in range(1, len(el_plus)+1,):
        comb_sum_plus = combinations(el_plus, i)
        for comb in comb_sum_plus:
            sum_plus = sum(list(comb))
 
            sum_plus_dict[sum_plus] += 1
    for i in range(1, len(el_minus)+1):
        comb_sum_minus = combinations(el_minus, i)
        for comb in comb_sum_minus:
            sum_minus = sum(list(comb))
            sum_minus_dict[sum_minus] += 1
 
    for key in range(1, dict_min+1):
        if sum_plus_dict[key] > 0 and sum_minus_dict[key] > 0:
            count += sum_plus_dict[key] * sum_minus_dict[key] * pow(2, count_zero)
    count += pow(2, count_zero)-1
    print count

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
X = sorted(map(int, input().split()))
ans = 0
def f(l, i, b):
    global ans
    if len(l) > 0:
        s = sum(l)
        if s//len(l) == A and s%len(l) == 0 and b:
            ans += 1
            b = False
        if s//len(l) > A : return
    if i >= N : return
    f(l, i+1, False)
    f(l+[X[i]], i+1, True)
f([], 0, True)
print(ans)

Submission status: Time Limit Exceeded

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

x =[]

for i in range(1,n+1):
    x.append(list(itertools.combinations(m,i)))
    
b = len(x)    
for i in range(b):
    for j in x[i]:
        c = len(j)
        if sum(j)/c == a:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2016/08/28

@author: diyosko7
'''
import numpy
import itertools

if __name__ == '__main__':
    n = 2
    e = [[int(i) for i in input().split()] for i in range(n)] 
    l1 = e[0]
    l2 = e[1]
    N = l1[0]   #maisuu
    A = l1[1]   #heikin
    xList = l2  #x
    

    lst = []
    cnt = 0
    for i in range(0,N):
        for s in itertools.combinations(xList,i+1):
            if numpy.average(numpy.array(s))==A:
                cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/local/bin/python3

import sys, os, itertools

if __name__ == '__main__':
    data = input().split()
    n = int(data[0])
    a = int(data[1])

    data = input().split()
    b = []
    for j in range(0, n):
        b.append(int(data[j]))

    flag = 0
    for j in range(1, n+1):
        c = (itertools.combinations(b, j))
        for i in c:
            if sum(i) == a*j:
                flag += 1
    print(flag)

Submission status: Time Limit Exceeded

Solution code:
import sys

N,A = sys.stdin.readline().split()
cards = sys.stdin.readline().split()
cards[:] = [int(x) - int(A) for x in cards]

pyramid = [[1],[1,1]]

def build_pyramid_to(l):
	while len(pyramid) <= l:
		new = [1]
		i = 0
		last_list = pyramid[-1]
		while i < len(last_list)-1:
			new.append(last_list[i]+last_list[i+1])
			i = i + 1
		new.append(1)
		pyramid.append(new)
def exponent_funct(base, count):
	ret = [0,base]
	while len(ret) != count + 1:
		ret.append(ret[-1]+base)
	return ret
#build_pyramid_to(5)
#print pyramid

coefficient = []
exponent = []
for x in set(cards):
	count = cards.count(x)
	build_pyramid_to(count)
	coefficient.append(pyramid[count])	
	exponent.append(exponent_funct(x,count))

#print coefficient
#print exponent

#multiplication
the_sum = 0
def golevel(l, pos, count_of_path):
	if l == len(exponent):
		if pos == 0:
			global the_sum
			the_sum = the_sum + count_of_path
	else:
		for i in xrange(len(exponent[l])):
			golevel(l+1,pos+exponent[l][i],count_of_path*coefficient[l][i])

golevel(0,0,1)
print the_sum - 1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/local/bin/python3

import sys, os, itertools

if __name__ == '__main__':
    data = input().split()
    n = int(data[0])
    a = int(data[1])

    data = input().split()
    b = []
    for j in range(0, n):
        b.append(int(data[j]))

    flag = 0
    for j in range(1, n+1):
        for i in (itertools.combinations(b, j)):
            if sum(i) == a*j:
                flag += 1
    print(flag)

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2016/08/28

@author: diyosko7
'''
import numpy
import itertools

if __name__ == '__main__':
    n = 2
    e = [[int(i) for i in input().split()] for i in range(n)] 
    l1 = e[0]
    l2 = e[1]
    N = l1[0]   #maisuu
    A = l1[1]   #heikin
    xList = l2  #x
    

    lst = []
    for i in range(0,N):
        lst.append(numpy.array(list(itertools.combinations(xList,i+1))))
    cnt = 0
    lst = numpy.array(lst)
    for l in lst:
        for s in l:
            if numpy.average(s) == A:
                cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

ans = 0
for i in range(N):
    com = list(itertools.combinations(x, i+1))
    for com_i in com:
        if sum(com_i) == (i+1)*A :
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/local/bin/python3

import sys, os, itertools

if __name__ == '__main__':
    data = input().split()
    n = int(data[0])
    a = int(data[1])

    data = input().split()
    b = []
    for j in range(0, n):
        b.append(int(data[j]))

    flag = 0
    for j in range(1, n+1):
        for i in (itertools.combinations(b, j)):
            if sum(i) / j == a:
                flag += 1
    print(flag)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

ans=0
for i in range(1,n+1):
    Sum = i*avg

    xlist=list(itertools.combinations(x,i))

    for j in xlist:
        if sum(j)==Sum:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

m = input().split()
b = input().split()
d = list(map(int,m))

n = d[0]
a = d[1]
x = list(map(int,b))

ans = 0

for i in range(1,len(x)+1):
    ary = list(itertools.combinations(x,i))
    for j in range(0,len(ary)):
        sumx = 0
        for k in range(0,len(ary[j])):
            sumx += ary[j][k]
        if sumx / i == a:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N, A = map(int, input().split())
A = float(A)
nums = list(map(int, input().split()))
avg_count = 0
len = len(nums)
for i in range(len):
    sequence_len = i+1
    combos = combinations(nums, sequence_len)
    for t in combos:
        total = 0
        for j in range(sequence_len):
           total += t[j]
        avg = total / sequence_len
        if avg == A:
            avg_count += 1
print(avg_count)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import numpy as np
N, A = map(int, raw_input().split())
x = map(int, raw_input().split())
count = 0
for i in xrange(len(x)):
    for c in combinations(x, len(x) - i):
        if np.array(c).mean() == A:
            count += 1
print count

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
for i in range(N):
    X[i] -= A
D = {0: 1}
for i in range(N):
    F = [[j, D[j]] for j in D]
    for j in F:
        if j[0] + X[i] in D:
            D[j[0] + X[i]] += j[1]
        else:
            D[j[0] + X[i]] = j[1]
print(D[0]-1)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
nums = list(map(int, input().split()))
MAX = A*N
dp = [[0 for _ in range(A*N+1)] for _ in range(N+1)]
dp[0][0] = 1
for k, num in enumerate(nums, start=1):
  for i in range(N-1, -1, -1):
    for j in range(A*N-1, -1, -1):
      if j + num <= A*N:
        dp[i+1][j+num] += dp[i][j]
ans = 0
for i in range(1, N+1):
  ans += dp[i][i*A]
print(ans)

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
xlst = list(map(int, input().split()))
dp = [[0 for _ in range(5001)] for _ in range(n + 1)]
center = 2500
dp[0][center] = 1
for i, x in enumerate(xlst, 1):
    num = x - a
    for j in range(5001):
        dp[i][j] = dp[i - 1][j]
        if 0 <= j - num <= 5000:
            dp[i][j] += dp[i - 1][j - num]
print(dp[-1][center] - 1)

Submission status: Accepted

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


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

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

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
l = list(map(int, input().split()))
ans = 0
dp = list([0]*(n*a+1) for _ in range(n+1))#動的計画法で解く
dp[0][0] = 1
for x in l:
    for i in range(n, 0, -1):#下行から順に格納していく(上からだと格納したばかりの値が参照されてしまう)
        for j in range(n*a+1):
            if x > j:
                continue
            dp[i][j] += dp[i-1][j-x]

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

print(ans)

Submission status: Accepted

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

dp = [[[0]*(2501) for i in range(51)] for j in range(51)]
dp[0][0][0] = 1
for i in range(N):
    value = X[i]
    for j in range(i+2):
        for k in range(2501):
            if i >= j:
                dp[i+1][j][k] += dp[i][j][k]
            if j >= 1 and k >= value:
                dp[i+1][j][k] += dp[i][j-1][k-value]

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

x=list(map(int,input().split()))
A=max(x)
x.insert(0,-1)
dp=[[[0]*(n+1) for _ in range(n*A+1)] for i in range(n+1)]
dp[1][x[1]][1]=1
dp[1][0][0]=1
for i in range(1,n):
    q=x[i+1]
    for s in range(n*A+1):
        for k in range(i+1):
            if s+q<=n*A:
                dp[i+1][s+q][k+1]+=dp[i][s][k]
            dp[i+1][s][k]+=dp[i][s][k]

ans=0
i=1

while i<=n and a*i<=n*A:
    ans+=dp[n][a*(i)][i]
    i+=1
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, A = MAP()
x = LIST()

X = max(max(x), A)

y = [0]*len(x)
for i in range(len(x)):
	y[i] = x[i]-A

dp = [[0]*(2*N*X+1) for _ in range(N+1)]  #dp[j][t] = y1...yj から0枚以上選んで合計がt-N*Xにするような選び方

for j in range(N+1):
	for t in range(-N*X, N*X+1):
		if j == 0 and t == 0:
			dp[j][t] = 1
		elif j >= 1 and (t-y[j-1] < -N*X or t-y[j-1] > N*X):
			dp[j][t] = dp[j-1][t]
		elif j >= 1 and -N*X <= t-y[j-1] <= N*X:
			dp[j][t] = dp[j-1][t] + dp[j-1][t-y[j-1]]
		else:
			dp[j][t] = 0

print(dp[N][0]-1)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, A = MAP()
x = LIST()

big = []
small = []
cnt = 0

for y in x:
	if y == A:
		cnt += 1
	elif y < A:
		small.append(A-y)
	else:
		big.append(y-A)

big_possible = [0]*2501
small_possible = [0]*2501
big_possible[0] = 1
small_possible[0] = 1

for a in big:
	for i in range(2500-a, -1, -1):
		if big_possible[i]:
			big_possible[i+a] += big_possible[i]

for b in small:
	for i in range(2500-b, -1, -1):
		if small_possible[i]:
			small_possible[i+b] += small_possible[i]

ans = 1
for i in range(1, 2501):
	ans += small_possible[i]*big_possible[i]


ans *= 2**cnt
print(ans-1)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fac = [1 for i in range(self.n + 1)]
        self.finv = [1 for i in range(self.n + 1)]
        for i in range(2, self.n+1):
            self.fac[i] = (self.fac[i - 1] * i) % self.mod
            self.finv[i] = (self.finv[i-1] * pow(i, -1, self.mod)) % self.mod

    def comb(self, n, m):
        return self.fac[n] * (self.finv[n-m] * self.finv[m] % self.mod) % self.mod
def iparse():
    return list(map(int, input().split()))

if __name__ == "__main__":
    n, a = iparse()
    x = iparse()

    dp = [[[0 for i in range(sum(x) + 10)] for j in range(n + 10)] \
        for k in range(n + 10)]
    dp[0][0][0] = 1
    for i in range(n):
        for j in range(n + 1):
            for k in range(sum(x) + 1):
                if j >= 1 and k - x[i] >= 0:
                    dp[i + 1][j][k] = dp[i][j][k] + dp[i][j - 1][k - x[i]]
                else:
                    dp[i+1][j][k] = dp[i][j][k]
    ans = 0
    for i in range(n):
        if (i + 1) * a >= sum(x) + 10:
            break
        ans += dp[n][i + 1][(i+1)*a]
    print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, A, *X = map(int, read().split())

    X = [x - A for x in X]

    base = 2500
    dp = [0] * 5001
    dp[base] = 1
    for i in range(N):
        dp, dp_prev = dp[:], dp
        for j in range(5001):
            if 0 <= j - X[i] <= 5000:
                dp[j] += dp_prev[j - X[i]]

    print(dp[base] - 1)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, A, *X = map(int, read().split())

    X = [x - A for x in X]

    base = 2500
    dp = [[0] * 5001 for _ in range(N + 1)]
    dp[0][base] = 1
    for i in range(N):
        for j in range(-2500, 2501):
            if -2500 <= j - X[i] <= 2500:
                dp[i + 1][j + base] = dp[i][j + base] + dp[i][j - X[i] + base]
            else:
                dp[i + 1][j + base] = dp[i][j + base]

    print(dp[N][base] - 1)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n, a = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
x = list(map(lambda x:x - a, x))
dic = defaultdict(int)
dic[0] = 1
for i in x:
    for j, k in list(dic.items()):
        dic[j + i] = dic.get(j + i, 0) + k
print(dic[0] - 1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
offset = 2500

def main():
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
    for i in range(N): X[i] -= A
    dp = [0] * 5010
    dp[offset] += 1
    dp[X[0] + offset] += 1
    for i, x in enumerate(X):
        if i == 0: continue
        dp2 = [0] * 5010
        for j in range(5010):
            if j < x or j - x >= 5010:
                dp2[j] = dp[j]
            else:
                dp2[j] = dp[j] + dp[j - x]
        dp = dp2
        #print(dp[offset - 3: offset + 4])
    print(dp[offset] - 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

z=len(lst)
dp=[[[0]*2501 for i in range(51)] for j in range(z+1)]
dp[0][0][0]=1

for i in range(z):
  x=lst[i]
  for j in range(z):
    for k in range(2451):
      dp[i+1][j][k]+=dp[i][j][k]
      dp[i+1][j+1][k+x]+=dp[i][j][k]

ans=0

for i in range(z+1):
  ans+=dp[-1][i][i*a]

print(ans-1)

Submission status: Accepted

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

dp = [[0]*(N*A+1) for _ in range(N+1)] #dp[i][j]:i枚の和がjとなるようなカードの選び方
dp[0][0] = 1  
for x in X:
    for i in reversed(range(1,N+1)):
        for j in reversed(range(N*A+1)):
            if j < x:
                continue
            dp[i][j] += dp[i-1][j-x]
ans = sum(dp[k][k*A] for k in range(1,N+1)) 
print(ans)

Submission status: Accepted

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

max_a=sum(li)

dp=[[ 0 for _ in range(n+1)]for _ in range(max_a+1)]
dp[max_a][n]=1

for j in range(n):
  for i in range(max_a+1):
    for k in range(n+1):
      if dp[i][k]>0:
        dp[i-li[j]][k-1]+=dp[i][k]
        
  
ans=0
for f in range(max_a+1):
  for g in range(n+1):
    if f==g*a:
      ans+=dp[f][g]
      
      
print(ans-1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353


def resolve():
    n, a = map(int, input().split())
    X = list(map(int, input().split()))
    MAX = sum(X)
    dp = [[[0] * (MAX + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 1
    for i in range(1, n + 1):
        x = X[i - 1]
        for j in range(n + 1):
            for k in range(MAX + 1):
                dp[i][j][k] += dp[i - 1][j][k]
                if k + x < MAX + 1 and j + 1 <= n:
                    dp[i][j + 1][k + x] += dp[i - 1][j][k]
    res = 0
    for j in range(1, n + 1):
        total = a * j
        if total <= MAX:
            res += dp[n][j][total]
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
ls1 = [0] + list(map(int,input().split()))

dp = [[[0 for k in range(2600)] for j in range(51) ] for i in range(51)]
for i in range(51):
    dp[i][0][0] = 1
for j in range(1,N+1):
    for k in range(1,j+1):
        for s in range(2600):
            if s < ls1[j]:
                dp[j][k][s] = dp[j-1][k][s]
            elif s >= ls1[j]:
                dp[j][k][s] = dp[j-1][k-1][s-ls1[j]] + dp[j-1][k][s]
ans = 0
for k in range(1,N+1):
    ans += dp[N][k][k*A]
print(ans)

Submission status: Accepted

Solution code:
n,a = map(int, raw_input().split())
ais = map(int, raw_input().split())
mem = {}
def dfs(i,ais, cumul,count,a):
	if i == len(ais):
		return 1 if (count > 0 and count * a == cumul) else 0
	if (i,cumul,count) in mem:
		return mem[(i,cumul,count)]
	mem[(i,cumul,count)] = dfs(i+1, ais, cumul + ais[i], count +1, a) + dfs(i+1, ais, cumul, count, a)
	return mem[(i,cumul,count)]
print dfs(0,ais,0,0,a)