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

Submission status: Accepted

Solution code:
from collections import defaultdict

N, A = map(int, input().split())
X = list(map(int, input().split()))
for i in range(N):
    X[i] -= A

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

for x in X:
    for j, c in list(dp.items()):
        dp[j + x] += c

print(dp[0]-1)

Submission status: Accepted

Solution code:

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

dp = [[[0 for i in range(4000)]for j in range(51)]for k in range(51)]

# dp[i][j][k] → i枚のうちj枚を選んで 和が kになる組み合わせ
dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for k in range(3000):
            if dp[i][j][k] != 0:
                dp[i+1][j][k] += dp[i][j][k]    #i枚目を選ばなかった世界線
                dp[i + 1][j + 1][k + nums[i]]  += dp[i][j][k]          #i枚目を選んだ世界線


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

Submission status: Accepted

Solution code:
from collections import defaultdict

n, k = map(int, input().split())
arr = list(map(int, input().split()))
arr = [x - k for x in arr]

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

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

print(dct[0] - 1)

Submission status: Accepted

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



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

dp = defaultdict(lambda:0)
for i in range(N):
  x = Xn[i]-A
  keys = list(dp.items())
  if x > 0:
    keys = sorted(keys,reverse=True)
  else:
    keys = sorted(keys)
  for k,t in keys:
    dp[k+x] += dp[k]
  dp[x] += 1

print(dp[0])

Submission status: Accepted

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

NX = N * max(x + [A])
y = [0] + [v - A for v in x]
dp = [[0] * (2 * NX + 1) for _ in range(N + 1)]

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

Submission status: Accepted

Solution code:
# どんな和が作れるか
N,A = map(int,input().split())
X = [int(x) for x in input().split()]

import numpy as np

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

for x in X:
  dp[1:,x:] += dp[:-1,:-x].copy()
  
answer = 0
for n in range(1,N+1):
  answer += dp[n,n*A]
  
print(answer)

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
X = max(x)
y = [i - a for i in x]
dp = [[0 for t in range(2 * n * X + 10)] for j in range(n + 1)]
dp[0][n * X] = 1
for j in range(1, n + 1):
    for t in range(2 * n * X + 1):
        if 0 <= t - y[j - 1] <= 2 * n * X:
            dp[j][t] = dp[j - 1][t] + dp[j - 1][t - y[j - 1]]
        elif t - y[j - 1] < 0 or t - y[j - 1] > 2 * n * X:
            dp[j][t] = dp[j - 1][t]
print(dp[n][n * X] - 1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections


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

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

    for c in x:
        current = list(d.items())
        for diff, count in current:
            delta = diff + c - a
            d[delta] = d[delta] + count

    print(d[0] - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
import itertools
import functools


@functools.lru_cache(maxsize=100000000)
def sigma(s):
    return sum(k * v for k, v in s)


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

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

    for c in x:
        current = list(d.items())
        for diff, count in current:
            delta = diff + c - a
            d[delta] = d[delta] + count

    print(d[0] - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

max_num = max(x)
max_num = max(A, max_num)
# x_jまでからk枚選んで合計がｓになる選び方の総数。ｓはk*Aにすれば平均がAになる
dp = [[[0 for _ in range(max_num * N + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
#何も選ばないで平均が０
dp[0][0][0] = 1

for j in range(N+1):
  for k in range(j+1):
    for s in range(max_num * k + 1):
      if j >= 1 and s < x[j - 1]:
        # j番目を選んでk+1個を選んだ際に平均がAにならない場合
        dp[j][k][s] = dp[j - 1][k][s]
      elif j >= 1 and k >= 1 and s >= x[j - 1]:
        # j番目をえらんでk+1個選んで平均がAになるものがあるなら、j-1番までの合計はs-x_j-1なので、その数を足している
        dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j - 1]]
 

ans = 0
# 合計がkAになるものを加算
for k in range(1, N + 1):
  ans += dp[N][k][k*A]
print(ans)

Submission status: Accepted

Solution code:
def main():
	N, A = map(int, input().split())
	x = list(map(int, input().split()))
	X = A
	for xi in x:
		X = max(X, xi)
	y = [xi-A for xi in x]
	dp = [[0 for _ in range(2*N*X+1)] for _ in range(N+1)]
	dp[0][N*X] = 1
	for j in range(1, N+1):
		for t in range(2*N*X):
			if t - y[j-1] < 0 or t - y[j-1] > 2*N*X:
				dp[j][t] = dp[j-1][t]
			else:
				dp[j][t] = dp[j-1][t] + dp[j-1][t-y[j-1]]
	print(dp[N][N*X]-1)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def solve():
  n,a = (int(i) for i in input().split())
  x = list(int(i) for i in input().split())
  tp = max(x)
  if tp < a:
    print(0)
    exit()
  
  dp = [[[0 for i in range(n*tp +1)] for j in range(n+1)] for k in range(n+1)]
  query = a*n
  dp[0][0][0] = 1
  for i in range(1,n+1):
    for j in range(n+1):
      for k in range(n*tp +1):
        #選ばない
        dp[i][j][k] = dp[i-1][j][k]
        if x[i-1] <= k and j > 0:
         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][j*a]
  #print(dp)
  print(ans)
  
  
  
  
  
  
solve()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N, A = map(int, input().split())
    X = [int(c) - A for c in input().split()]
    d = defaultdict(lambda: 0)

    for x in X:
        d_ = defaultdict(lambda: 0)
        for key in d.keys():
            d_[key + x] += d[key]

        for key in d_.keys():
            d[key] += d_[key]

        d[x] += 1

    return d[0]


if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

    print(ans)


def editorial_3d(N, A, X):
    """
    dp[N][N][sum]
    N枚の選択肢, N枚選ぶ, 合計値
    """
    max_sum = N * A
    dp = [[None] for _ in range(N+1)]
    for i in range(N+1):
        tmp = [[0] * (2 * max_sum + 1) for _ in range(N+1)]
        dp[i] = tmp
    # 0枚選択肢のとき、合計0はあり得る
    dp[0][0][0] = 1

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

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

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

    return ans


def editorial_2d(N, A, X):
    """
    dp[N][sum]
    N枚の選択肢, 合計値
    """
    # X[i] がすべて0なら -A することで最低値になりうる
    # よって2倍確保して対応
    max_sum = 2 * (N * 50)
    dp = [[0] * (max_sum + 1) for _ in range(N+1)]
    # 真ん中の位置を0扱い
    dp[0][max_sum // 2] = 1

    for i in range(1, N+1):
        for k in range(max_sum + 1):
            v = dp[i-1][k]
            s = k - (X[i-1] - A)
            if 0 <= s <= max_sum:
                v += dp[i-1][s]

            dp[i][k] += v

    # 0枚のとき合計0はあり得るが、問題文より
    # これらのカードの中から 1枚以上を選び、
    # 選んだカードに書かれた整数の平均をちょうど Aにしたい
    # よって -1 しないといけない
    # 今回の組合せは、掛け算で増えないためそのまま減算で良い(はず)
    ans = dp[N][max_sum // 2] - 1

    return ans


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

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

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

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

        return ans

    ans = rec(0, N)
    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#x枚目まででy枚選んで合計がzになる場合の数dp[x][y][z](x+1*y+1*たくさん)
N,A=map(int,input().split())
x=[int(i) for i in input().split()]
dp=[[[0]*(50*N+1) for i in range(N+1)]for k in range(N+1)]
ans=0
dp[0][0][0]=1
for made,i in enumerate(dp):#走査して、一個上を書き換え
    if made>N:break
    for maisu,j in enumerate(i):
        for wa,k in enumerate(j):
            if k and made<N:#made枚目までにmaisu枚選んでwaになる場合の数
                dp[made+1][maisu][wa]+=k#made+1枚目についての議論
                newwa=wa+x[made]
                if newwa<=A*N:
                    dp[made+1][maisu+1][newwa]+=k
for mai in range(1,N+1):
    a=dp[N][mai][mai*A]
    if a:
        ans+=a
print(ans)

Submission status: Accepted

Solution code:
def tak_and_cards(N: int, A: int, X: list) -> int:
    #  部分点解法
    # :---------:
    # count = 0
    # for b in range(1, 1 << N):
    #     n, s = 0, 0
    #     for i in range(N):
    #         if (b >> i) & 1 == 0:
    #             continue
    #         n += 1
    #         s += X[i]

    #     if s == n * A:
    #         count += 1
    # return count
    max_X = max(X)
    dp = [[0] * (2 * max_X * N + 1) for _ in range(N + 1)]
    dp[0][max_X * N] = 1

    for k, x in enumerate(X):
        for t in range(2 * max_X * N + 1):
            y = x - A

            dp[k + 1][t] = dp[k][t]
            if 0 <= t - y and t - y <= 2 * max_X * N:
                dp[k + 1][t] += dp[k][t - y]

    return dp[N][max_X*N] - 1


if __name__ == "__main__":
    N, A = map(int, input().split())
    x = [int(s) for s in input().split()]
    ans = tak_and_cards(N, A, x)
    print(ans)

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
stack=[0]*5001
stack[2500]=1
for i in range(len(x)):
  x[i]-=a
for i in x:
  stack2=[i for i in stack]
  for j in range(5001):
    if 0<=j+i<=5000:
      stack2[j+i]+=stack[j]
  stack=[i for i in stack2]
print(stack[2500]-1)

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
stack=[0]*5001
stack[2500]=1
ans=0
for i in range(len(x)):
  x[i]-=a
for i in x:
  ans+=stack[2500-i]
  stack2=[i for i in stack]
  for j in range(5001):
    if 0<=j+i<=5000:
      stack2[j+i]+=stack[j]
  stack=[i for i in stack2]
print(stack[2500]-1)

Submission status: Accepted

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

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

X = max(max(x), A)
# dp = [[[0]*(N*X+1) for _ in range(N+1)] for _ in range(N+1)]
# for j in range(N+1):
# 	for k in range(N+1):
# 		for s in range(N*X+1):
# 			if j == 0 and k == 0 and s == 0:
# 				dp[j][k][s] = 1
# 			elif j >= 1 and s < x[j-1]: # 探索先が総和より大きい
# 				dp[j][k][s] = dp[j-1][k][s]
# 			elif j >= 1 and k >= 1 and s >= x[j-1]:
# 				dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
# 			else:
# 				dp[j][k][s] = 0
# sum = 0
# for i in range(1, N+1):
# 	sum += dp[N][i][i*A]
# print(sum)

dp = [[0]*(2*N*X+1) for _ in range(N+1)]
y = [0] * len(x)
for i in range(len(x)):
	y[i] = x[i]-A

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:
from sys import stdin
input = stdin.readline

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

X = max(max(x), A)
# dp = [[[0]*(N*X+1) for _ in range(N+1)] for _ in range(N+1)]
# for j in range(N+1):
# 	for k in range(N+1):
# 		for s in range(N*X+1):
# 			if j == 0 and k == 0 and s == 0:
# 				dp[j][k][s] = 1
# 			elif j >= 1 and s < x[j-1]: # 探索先が総和より大きい
# 				dp[j][k][s] = dp[j-1][k][s]
# 			elif j >= 1 and k >= 1 and s >= x[j-1]:
# 				dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
# 			else:
# 				dp[j][k][s] = 0
# sum = 0
# for i in range(1, N+1):
# 	sum += dp[N][i][i*A]
# print(sum)

dp = [[0]*(2*N*X+1) for _ in range(N+1)]
y = [0] * len(x)
for i in range(len(x)):
	y[i] = x[i]-A

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

Submission status: Accepted

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

X = [int(i)-a for i in input().split()]
dp = [[0]*(100*n+1) for i in range(n+1)]
dp[0][50*n] = 1

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

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

Submission status: Accepted

Solution code:
from functools import reduce

def main():
    # 一文字のみを読み込み
    # s = input().rstrip().split(' ')
    
    # スペース区切りで標準入力を配列として読み込み
    # s = input().rstrip().split(' ')

    # 位置文字ずつ標準入力を配列として読み込み
    # s = list(input().rstrip())
    N, A = [int(_) for _ in input().split()]
    X = [int(_) for _ in input().split()]

    # dp[n][k][s] : n枚目までからk枚選んで合計をsにする場合の数
    dp = [[[0 for _ in range(2501)] 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 s in range(50*k+1):
                if(n>=1 and s<X[n-1]):
                    dp[n][k][s] = dp[n-1][k][s]
                if(n>=1 and s>=X[n-1]):
                    dp[n][k][s] = dp[n-1][k][s] + dp[n-1][k-1][s-X[n-1]]

    Ans = 0
    for i in range(1,N+1):
        Ans += dp[N][i][i*A]
 
    print(Ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from scipy.ndimage import shift

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

dp = [np.array([[0]*(N*A+1) for _ in range(N+1)])]
#dp[0]: [0, 0]～[N, N*A]

for x in X:
  new_dp = dp[-1].copy()
  new_dp += shift(dp[-1], [1,x])
  if x<=N*A:
    new_dp[1, x] += 1
  
  dp.append(new_dp)
#print(dp[-1])
  
print(sum([dp[-1][i, i*A] for i in range(1, N+1)]))

Submission status: Accepted

Solution code:
import numpy as np

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

dp = [np.array([[0]*(N*A+1) for _ in range(N+1)])]
#dp[0]: [0, 0]～[N, N*A]

for x in X:
  new_dp = dp[-1].copy()
  new_dp[1:, x:] += dp[-1][0:N, 0:N*A+1-x]
  if x<=N*A:
    new_dp[1, x] += 1
  
  dp.append(new_dp)
#print(dp[-1])
  
print(sum([dp[-1][i, i*A] for i in range(1, N+1)]))

Submission status: Accepted

Solution code:
def main():
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
    dp = [[0]*(50*N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for x in X:
        for i in range(N-1, -1, -1):
            for j in range(50*N+1):
                if j+x <= 50*N:
                    dp[i+1][j+x] += dp[i][j]
    ans = 0
    for i in range(1, N+1):
        ans += dp[i][i*A]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

xs = {0: 1}

for n in X:
    #print(xs)
    kv = list(xs.items())
    for k, v in kv:
        nk = k + n - A
        xs[nk] = xs.get(nk, 0) + v

#print(xs)

result = xs[0] - 1

print(result)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
n,a = LI()
x = LI()
s = sum(x)
dp = [[[0 for i in range(s+1)] for j in range(n+1)] for k 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,n+1):
        for k in range(s+1):
            if k >= x[i-1]:
                dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
            else:
                dp[i][j][k] = dp[i-1][j][k]
ans = 0
for i in range(1,n+1):
    if a*i <= s:
        ans += dp[n][i][a*i]
print(ans)
#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
def main():
    #入力
    n, a = map(int,input().split())
    x = [0] + list(map(int,input().split()))

    sum_max = (n)*(max(x))+1

    #dp[i][j][k]:x1-xiからj枚選んで、合計をkにする選び方の数
    dp = [[[0]*2501 for _ in range(n+1)] for _ in range(n+1)]

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

    for i in range(1,n+1):
        for j in range(n+1):
            for k in range(50*j+1):
                #xi>kのとき
                if x[i]>k:
                    dp[i][j][k] = dp[i-1][j][k]
                elif j>=1 and x[i]<=k:
                    #xi<=kのとき
                    dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-x[i]]

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

maxx = max(x)
maxx = max(maxx, a)
# dp[j][k][s] : j枚目までからk枚選んで合計をsにする場合の数
dp = [[[0 for _ in range(maxx * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for j in range(n + 1):
    for k in range(j + 1):
        for s in range(maxx * k + 1):
            if 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]]

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

Submission status: Accepted

Solution code:
#ABC044C
n,a=map(int,input().split())
x=list(map(int,input().split()))
res=[[0  for i in range(max(1+a*n,1+sum(x)))] for j in range(n+1)]
res[0][0]+=1
for i in range(n):
    for k in range(sum(x),0,-1):
        if k-x[i]<0:continue
        for j in range(1,i+2):
            res[j][k]+=res[j-1][k-x[i]]
ans=0
for i in range(1,n+1):
    ans+=res[i][a*i]
print(ans)

Submission status: Accepted

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

X = [int(x) - A for x in input().split()]
dp = [[0 for _ in range(100*N+1)] for _ in range(N+1)]
dp[0][50*N] = 1

for i in range(N):
  for j in range(50, 100*N+1-50):
    dp[i+1][j] = dp[i][j] + dp[i][j - X[i]]
print(dp[N][50*N] - 1)

Submission status: Accepted

Solution code:
from collections import Counter
n,a=map(int,input().split())
X=sorted(list(map(lambda x:int(x)-a,input().split())))
ans=Counter([0])
for x in X:
  tmp=Counter()
  for k,v in ans.items():
    tmp[k+x]+=v
  ans+=tmp
print(ans[0]-1)

Submission status: Accepted

Solution code:
from collections import Counter

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

X = [x-A for x in X]

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

print(c[0]-1)

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
X = [int(e)-A for e in input().split()]
# dp[i][s]: i番目まで見て部分和がsとなるような場合の数
# 初期条件: dp[0][0] = 1
# 遷移: dp[i][s] += dp[i-1][s-X[i]] + dp[i-1][s]
# 答え: dp[N][0]
s_max = 5001
dp = [[0]*(s_max+1) for i in range(N+1)]
dp[0][2500] = 1
for i in range(1,N+1):
    for s in range(s_max+1):
        if 0 <= s-X[i-1] <= s_max:
            dp[i][s] += dp[i-1][s-X[i-1]]
        dp[i][s] += dp[i-1][s]
# 全てを選ばなかった1通りは除外
ans = dp[N][2500] - 1
print(ans)

Submission status: Accepted

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

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

for i in range(1, N + 1):
    dp[i][y[i - 1] + X*N] += 1
    for j in range(len(dp[0])):
        dp[i][j] += dp[i - 1][j]
        diff = j + y[i - 1]
        if 0 <= diff and diff <= 2*X*N:
            dp[i][diff] += dp[i - 1][j]

print(dp[N][X*N])

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
num_base = list(map(int, input().split()))
num_li = [n - A for n in num_base]

import collections as cols
C = cols.Counter([0])

for n in num_li:
  adcols = cols.Counter()
  for idx, count in C.items():
    adcols[n+idx] += count
  C += adcols
print(C[0]-1)

Submission status: Accepted

Solution code:
import collections as co
n,a=map(int,input().split())
X=[int(x)-a for x in input().split()]
C=co.Counter([0])
for x in X:
  itiji=co.Counter()
  for i,c in C.items():
    itiji[i+x]+=c
  C+=itiji
print(C[0]-1)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
*x,=map(int,input().split())
dp=[[[None]*(n*50+1) for i in range(n+1)] for _ in range(n+1)]

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

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,=map(int,input().split())
dp=[[[0]*(n*50+1) for i in range(n+1)] for _ in range(n+1)]

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

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

Submission status: Accepted

Solution code:
from collections import Counter
N,A=map(int,input().split())
X=[int(x)-A for x in input().split()]
combination=Counter([0])
for x in X:
    tmp=Counter()
    for key,count in combination.items():
        tmp[key+x]+=count
    combination+=tmp
print(combination[0]-1)