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: Accepted

Solution code:
N,A=map(int,input().split())
x=list(map(int,input().split()))
x=[i-A for i in x]
dp=[[0]*50*N*2 for i in range(N+1)]
dp[0][50*N]=1
for i in range(1,N+1):
    for j in range(50*N*2):
        n=j-x[i-1]
        if n>=0 and n<50*N*2:
            dp[i][j]=dp[i-1][j]+dp[i-1][n]
        else:
            dp[i][j]=dp[i-1][j]
    #else:
        #print(dp[i])

print(dp[N][50*N]-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
x = [0] + x
dp = [[[0 for _ in range(max(x)*n+1)] for _ in range(n+1)] for _ in range(n+1)]
x.sort()
for j in range(n+1):
    for k in range(n+1):
        for s in range(max(x)*n+1):
            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif j >= 1 and s < x[j]:
                dp[j][k][s] = dp[j-1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j]]
            else:
                dp[j][k][s] = 0

ans = 0
for k in range(1, n+1):
    try:
        ans += dp[n][k][k*a]
    except:
        pass

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

dp = [[[0 for k in range(n+1)] for j in range(n+1)] for s in range(2501)]


dp[0][0][0] = 1
for s in range(2501):
    for j in range(1, n+1):
        for k in range(j+1):
            idx = j-1
            if x[idx] > s:
                dp[s][j][k] = dp[s][j-1][k]
            else:
                dp[s][j][k] = dp[s][j-1][k] + dp[s-x[idx]][j-1][k-1]

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

print(ans)

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
ns = list(map(int, input().split()))
ns = [0] + ns
ma = max(ns+[a])
dp = [[[0] * (ma * n+1) for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    for j in range(i+1):
        for k in range(n * ma+1):
            if i == j == k == 0:
                dp[i][j][k] = 1
            elif i > 0 and k < ns[i]:
                dp[i][j][k] = dp[i - 1][j][k]
            elif i > 0 and j >= 1 and k >= ns[i]:
                dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - ns[i]]
print(sum(dp[n][i][i*a] for i in range(1, n+1)))

Submission status: Accepted

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
t = [[[0] * (50*(j+1)+1) for j in range(i+2)] for i in range(n+1)]
ans = 0
t[0][0][0] = 1

for i in range(1, n+1):
    for j in range(i+1):
        for k in range(50*j + 1):
            if j >= 1 and k >= x[i-1]:
                t[i][j][k] = t[i - 1][j - 1][k - x[i-1]] + t[i - 1][j][k]
            else:
                t[i][j][k] = t[i - 1][j][k]
for i in range(1,n+1):
    ans += t[n][i][i*a]
print(ans)

Submission status: Accepted

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

def main():
    N, A = map(int, readline().rstrip().split())
    X = list(map(int, readline().rstrip().split()))
    lim = max(X) * N
    X = [x-A for x in X]
    dp = [[0]*(2*lim) for _ in range(N+1)]
    dp[0][lim] = 1
    for i in range(1, N+1):
        x = X[i-1]
        for j in range(2*lim):
            if 0 <= j - x < 2 * lim:
                dp[i][j] = dp[i-1][j] + dp[i-1][j-x]
            else:
                dp[i][j] = dp[i-1][j]
    
    print(dp[N][lim] - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [[0]*2501 for _ in range(n+1)]
for i in range(n+1):
  for j in range(i-1, -1, -1):
    if j == 0:
      dp[j+1][x[i-1]] += 1
    for k in range(2500, -1, -1):
      if dp[j][k] and k+x[i-1] <= 2500:
        dp[j+1][k+x[i-1]] += dp[j][k]

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())
xxx = list(map(int, input().split()))
limit = a * n
dp = [[0] * (limit + 1) for i in range(n + 1)]
dp[0][0] = 1
for i, x in enumerate(xxx):
    if x > limit:
        continue
    for j in range(i, -1, -1):
        for k in range(limit - x, -1, -1):
            dp[j + 1][k + x] += dp[j][k]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
    N, A = list(map(int, input().split()))
    X = [int(i) - A for i in input().split()]
    d = {0: 1}
    for x in X:
        for _sum, count in list(d.items()):
            d[_sum+x] = d.get(_sum+x, 0) + count

    print(d[0]-1)
    


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
nums=[int(i)-a for i in input().split()]
d={0:1}
for i in nums:
  s = [[j, d[j]] for j in d]
  for j in s:
    if j[0] + i in d:
      d[j[0]+i] += j[1]
    else:
      d[j[0]+i] = j[1]
print(d[0]-1)

Submission status: Accepted

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

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

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

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

    return arr

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

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

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

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, a = map(int, input().split())            
x = [i - a for i in map(int, input().split())]
dp = [[0 for j in range(4901)] for i in range(n)]
dp[0][2450] += 1
dp[0][x[0] + 2450] += 1
for i in range(1, n):
    for j in range(4901):
        dp[i][j] = dp[i - 1][j]
        if 0 <= j - x[i] < 4901:
            dp[i][j] += dp[i - 1][j - x[i]]
ans = dp[n - 1][2450] - 1
print(ans)

Submission status: Accepted

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

def main():
    N, A = (int(_) for _ in input().split())
    X = [int(_) for _ in input().split()]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,a,*l=map(int,open(0).read().split())
R=2500
dp=[[0]*R*2,[0]*R*2]
dp[0][0]=1
t=0
for i in range(n):
  u=1-t
  for s in range(-R,R):
    dp[u][s]=dp[t][s]+dp[t][s-l[i]+a]
  t=u
print(dp[t][0]-1)

Submission status: Accepted

Solution code:
n,a,*l=map(int,open(0).read().split())
R=2500
dp=[[0]*R*2,[0]*R*2]
dp[0][0]=1
for i in range(n):
  for s in range(-R,R):
    dp[i+1&1][s]=dp[i&1][s]+dp[i&1][s-l[i]+a]
print(dp[n&1][0]-1)

Submission status: Accepted

Solution code:
n,a,*l=map(int,open(0).read().split())
R=2500
dp=[[0]*R*2 for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
  for s in range(-R,R):
    dp[i+1][s]=dp[i][s]+dp[i][s-l[i]+a]
print(dp[n][0]-1)

Submission status: Accepted

Solution code:
_,a,*l=map(int,open(0).read().split())
d={0:1}
for i in l:
  for k,v in d.copy().items(): d[i-a+k]=d.get(i-a+k,0)+v
print(d[0]-1)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,a=f()
l=[i-a for i in f()]
dp=[[0]*5000 for _ in range(51)]
Z=2500
dp[0][Z]=1
for i in range(n):
  for s in range(5000-max(l[i],0)):
    dp[i+1][s]+=dp[i][s]
    dp[i+1][s+l[i]]+=dp[i][s]
print(dp[n][Z]-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict


def main():
    N, A = map(int, input().split())
    X = [int(x) - A for x in input().split()]

    result = Counter([0])

    for x in X:
        dct = defaultdict(int)
        for k, v in result.items():
            dct[k + x] += v
        result += dct

    print(result[0] - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

x = [int(i) for i in input().split()] 
y = [int(i)-a for i in x] 


max = max(x)

dp = [[0 for _ in range(2*n*max+1)] for _ in range(n+1)]

dp[0][n*max] = 1 

for i in range(1, n+1):
	for j in range(2*n*max+1):
		if j - y[i-1] < 0 or j - y[i-1] > 2*n*max:
			dp[i][j] = dp[i-1][j]
		else: 
			dp[i][j] = dp[i-1][j] + dp[i-1][j-y[i-1]]

result = dp[n][n*max]-1

print(result)

Submission status: Accepted

Solution code:
from collections import Counter


N, A = map(int, input().split())
X = list(map(int, input().split()))
Y = [x - A for x in X]
L = Counter()
L[0] = 1

for y in Y:
    for key, value in list(L.items()):
        L[key + y] += value

print(L[0] - 1)

Submission status: Accepted

Solution code:
def c_tak_and_cards():
    from collections import defaultdict
    N, A = [int(i) for i in input().split()]
    X = [int(i) for i in input().split()]

    average = [x - A for x in X]
    dp = defaultdict(int)  # dp[s]: y から 1 枚以上選んで整数の和を s にする方法
    dp[0] = 1  # 「選ばない」 1 通り
    for y in average:
        for k, v in list(dp.items()):  # for 文中で要素数が変わってはいけないため
            dp[k + y] += v
    return dp[0] - 1

print(c_tak_and_cards())

Submission status: Accepted

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

dp = defaultdict(dict)
dp[0][0] = 1  # カード0枚で合計

for x in X:
    newDP = defaultdict(dict)
    for card, memo in dp.items():
        for k, v in memo.items():
            # カードXを追加しない
            if k in newDP[card]:
                newDP[card][k] += v
            else:
                newDP[card][k] = v
            # カードXを追加するよ
            if k + x in newDP[card + 1]:
                newDP[card + 1][k + x] += v
            else:
                newDP[card + 1][k + x] = v
    dp = newDP

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

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

dp = [0] * (2 * n * 50 + 2)
dp[0] = 1

for i in range(n):
    h = dp[:]
    for j in range(-(n - 1) * 50, (n - 1) * 50 + 1):
        h[j] += dp[j - x[i]]
    dp = h

print(dp[0] - 1)

Submission status: Accepted

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

blist = list(map(lambda x:x-A,alist))
sum_plus = 0
sum_minus = 0
for i in blist:
    if i >0:
        sum_plus +=i
    else:
        sum_minus +=i

N=len(alist)
dp = [[0 for i in range(sum_plus - sum_minus + 1)] for j in range(N+1)]
dp[0][0-sum_minus]=1

for i in range(N):
    for j in range(sum_plus - sum_minus+1):
        if j-blist[i] <= (sum_plus - sum_minus):
            dp[i+1][j]=dp[i][j-blist[i]]+dp[i][j]
        else:
            dp[i+1][j]=dp[i][j]

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,a = m()

x = l()

ma = max(x)

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

dp[0][0] = 1

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

ans = 0

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

print(ans)

Submission status: Accepted

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

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

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

for j in range(N):
    for k in range(N):
        for s in range(N*X+1):
            #dp[j+1][k][s] = max(dp[j+1][k][s], dp[j][k][s])
            if s-x[j] < 0:
                dp[j+1][k][s] = dp[j][k][s]
            else:
            #if s-x[j] >= 0:
                dp[j+1][k+1][s] = dp[j][k+1][s] + dp[j][k][s-x[j]]


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

Submission status: Accepted

Solution code:
N, A = input().split(" ")
N, A = int(N), int(A)
x = input().split(" ")
x = [int(i) for i in x]
y = [0]+[int(i)-A for i in x]
X = max(x+[A])

dp = [[0 for t in range(2*N*X+1)] for j in range(N+1)]

for j in range(N+1):
    for t in range(2*N*X+1):
        if j == 0 and t == N*X:  # 0枚の時は0しか達成できない
            dp[j][t] = 1
        elif j >= 1 and (t - y[j-1] < 0 or t-y[j] > 2*N*X):  # xの値が平均Aを超えてしまう場合は、前回の結果から場合の総数に変化なし
            dp[j][t] = dp[j-1][t]
        elif j >= 1 and 0 <= t-y[j-1] <= 2*N*X:  # 前回の場合の総数に、今回の数を足して0になる場合の総数を足す
            dp[j][t] = dp[j-1][t] + dp[j-1][t-y[j]]
        else:
            dp[j][t] = 0
print(dp[N][N*X] - 1)

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
A=list(map(int,input().split()))
for i in range(n):
  A[i]=A[i]-a
B=[]
c=0
for i in range(n):
  if A[i]==0:
    c=c+1
  else:
    B.append(A[i])
n=len(B)
dp=[[0]*5010 for i in range(n+1)]#0と2505を対応
for i in range(1,n+1):
  dp[i]=dp[i-1][0:5010]
  dp[i][2505+B[i-1]]+=1
  for j in range(5010):
    if 0<=j+B[i-1] and j+B[i-1]<=5009:
      dp[i][j+B[i-1]]+=dp[i-1][j]
ans=dp[n][2505]
print((ans+1)*2**c-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import io

nim, mike = map(int, input().split())
kite = list(map(int, input().split()))
for i in range(nim):
    kite[i] -= mike
qwe = defaultdict(int)
qwe[0] = 1
for o in kite:
    for j, c in list(qwe.items()):
        qwe[j + o] += c
print(qwe[0]-1)

Submission status: Accepted

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

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



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

            dp[i+1][j][k] += dp[i][j][k]
            if k+l[i] < 2501:
                dp[i+1][j+1][k+l[i]] += dp[i][j][k]


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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,a = map(int, input().split())
    x = list(map(int, input().split()))
    for i in range(n):
        x[i] -= a
    dp = [[0]*5001 for _ in range(n+1)]

    dp[0][0] = 1

    for i in range(1, n+1):
        for j in range(-2500, 2501):
            dp[i][j] += dp[i-1][j]
            if -2500 <= j-x[i-1] <= 2500:
                dp[i][j] += dp[i-1][j-x[i-1]]
    print(dp[-1][0]-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

n, a, *x = map(int, sys.stdin.read().split())
for i in range(n): x[i] -= a

def main():
  dp = defaultdict(int); dp[0] = 1
  for i in range(n):
    ndp = dp.copy()
    for k, v in dp.items():
      ndp[k+x[i]] += v
    dp = ndp
  print(dp[0] - 1)
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

n, a, *x = map(int, sys.stdin.read().split())

def main():
    dp = np.zeros((n + 1, 2501), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(n):
        dp[1:, x[i]:] += dp[:-1, :-x[i]].copy()
    i = np.arange(1, n + 1)
    print(dp[i, i * a].sum())

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

n, a, *x = map(int, sys.stdin.read().split())

def main():
    m = 2500
    dp = np.zeros((n + 1, m + 1), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(n):
        dp[1:, x[i]:] += dp[:-1, :-x[i]].copy()
    i = np.arange(1, n + 1)
    print(dp[i, i * a].sum())

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

n, a, *x = map(int, sys.stdin.read().split())

def main():
    m = 2500
    dp = np.zeros((n + 1, m + 1), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(n):
        ndp = np.copy(dp)
        ndp[1:, x[i]:] += dp[:-1, :m-x[i]+1]
        dp = ndp
    i = np.arange(1, n + 1)
    print(np.sum(dp[i, i * a]))

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

n, a, *x = map(int, sys.stdin.read().split())

def main():
    m = 2500
    dp = np.zeros((n + 1, m + 1), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(n):
        ndp = np.copy(dp)
        for j in range(1, n + 1):
            ndp[j][x[i]:] += dp[j-1][:m-x[i]+1]
        dp = ndp
    i = np.arange(1, n + 1)
    print(np.sum(dp[i, i * a]))

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
n,a = map(int, input().split())
X = list(map(int, input().split()))
x = [i-a for i in X]
dp = [[0]*5201 for i in range(n+1)]
dp[0][2600] = 1 
for i,xi in enumerate(x):
  for k in range(99,5101):
    dp[i+1][k+xi] += dp[i][k] 
    dp[i+1][k] += dp[i][k]
ans = dp[n][2600] - 1
print(ans)

Submission status: Accepted

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

for i in range(n):
    x[i]=x[i]-a
    
nx=n*n
dp=[[0]*(2*nx+1) for i in range(n+1)]

#print(dp)

dp[0][nx]=1

for j in range(1,n+1):
    jj=j-1
    for t in range(2*nx+1):
        if t-x[jj]<0 or 2*nx<t-x[jj]:
            dp[j][t]=dp[j-1][t]
        elif 0<t-x[jj] and  t-x[jj]<2*nx:
            dp[j][t]=dp[j-1][t]+dp[j-1][t-x[jj]]
        else:
            dp[j][t]=0

print(dp[n][nx]-1)

Submission status: Accepted

Solution code:
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""


def readInts():
  return list(map(int,input().split()))

def main():
  n,a = readInts()
  
  X = readInts()
  
  X = list(map(lambda i: i-a, X))# lambda iに、 i - aという演算のもと Xから入れる
  # ここで、平均が8になるもの key = 0の時が答えになる。
  # だからこそ　答えで dp[0] - 1 するのはこのため
  
  dp = {0:1} 
  
  for i in X:
    for k,v in list(dp.items()): # key,valueをそれぞれ抽出
      dp[i+k] = dp.get(i+k, 0) + v
      #
      # get(なんか) なんかに入ってる辞書のvalueが返ってくる
      # 無かったら、get(なんか,〇)で、〇に入ってるので辞書が更新される
      # 
  # print(dp)
  #{0: 6, 1: 6, 2: 2, -1: 2}
  # 負の数にも対応している
  print(dp[0]-1)
  
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 =[x - A for x in X]

d = defaultdict(int)
d[0] = 1

for x in X:
  for k, v in list(d.items()):
    d[k+x] += v

print(d[0]-1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,a = map(int,readline().split())
lst1 = list(map(int,readline().split()))

import numpy as np

dp = np.zeros((n+1,3000),dtype=np.int64) # 枚数、目標数ごとに場合の数
dp[0,0] = 1

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

Submission status: Accepted

Solution code:
def solve(n, a, lst):
  m = max(max(lst), a)
  ans = [[[0]*(n*m+1) for i in range(n+1)] for j in range(n+1)]
  #ans[i][j][k] : lst[:i]までの中からj枚選んで合計kにする選び方
  for i in range(n+1):
    for j in range(n+1):
      for k in range(n*m+1):
        if i == 0 and j == 0 and k == 0:
          ans[i][j][k] = 1
        elif i >= 1 and k < lst[i-1]:
          ans[i][j][k] = ans[i-1][j][k]
        elif i >= 1 and lst[i-1] <= k and j >= 1:
          ans[i][j][k] = ans[i-1][j-1][k-lst[i-1]] + ans[i-1][j][k]
        else:
          ans[i][j][k] = 0
  ret = 0
  for i in range(1,n+1):
    ret += ans[-1][i][i*a]
  return int(ret)

if __name__ == "__main__":
  n, a = map(int,input().split())
  x_list = [int(i) for i in input().split()]
  ans = solve(n,a,x_list)
  print(ans)

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,A = map(int,input().split())
X = [0] + list(map(int,input().split())) # 1枚も選ばない場合として 0 を足しておく

# dp[n][k][d] : n枚からk枚選んで合計dにする選び方
dp = [[[0 for _ in range(50*N+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for n in range(N+1):
    for k in range(n+1):
        for d in range(50*k+1):
            # 目指す "合計の数 : d" がn枚目のカードより小さい場合, そのカードは使えない
            if d < X[n]:
                dp[n][k][d] = dp[n-1][k][d]
            # そうでない場合
            else:
                # k==0のときはカードを選べないことに注意
                if k >= 1:
                    dp[n][k][d] = dp[n-1][k][d] + dp[n-1][k-1][d-X[n]]
                    # dp[n-1][k][d] : k枚目のカードを選ばない場合
                    # dp[n-1][k-1][d-X[n]] : k枚目のカードを選ぶ場合。n-1枚目までで合計 d-X[n] であれば良い。

ans = 0
for i in range(1,N+1): # 0を除く、0のときは「0枚から0枚選んで0にする」で1通りになるが、これは答えには含まれない
    # N枚からi枚選んで平均がA,つまり合計がA*i
    ans += dp[N][i][A*i]

print(ans)