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:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,a = list(map(int, input().split()))
x = list(map(lambda x: int(x)-a, input().split()))
size = max(1, sum(abs(item) for item in x))
# 0: 
dp = [[0]*(2*size+1) for _ in range(n+1)]
dp[0][size+1] = 1
for i in range(1,n+1):
    xx = x[i-1]
    for j in range(2*size+1):
        dp[i][j] = dp[i-1][j]
        if 0<=j-xx<2*size+1:
            dp[i][j] += dp[i-1][j-xx]
print(dp[n][size+1]-1)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, a = map(int, input().split())
x = list(map(int, input().split()))
y = [xi - a for xi in x]

# 解説AC
dp = [defaultdict(int) for i in range(n + 1)]
dp[0][0] = 1

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

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

Submission status: Accepted

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

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

for i in range(1,N):
    for v in range(-M, M+1):
        dp[i][v+M] += dp[i-1][v+M]
        if -M<=v-X[i]<=M:
            dp[i][v+M] += dp[i-1][v-X[i]+M]

print(dp[-1][M]-1)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, a = map(int, input().split())
x = list(map(int, input().split()))
y = [xi - a for xi in x]

# 解説AC
dp = [defaultdict(int) for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for j in dp[i]:
        dp[i + 1][j + y[i]] += dp[i][j]
        dp[i + 1][j] += dp[i][j]
print(dp[n][0] - 1)

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
x=[int(j)-a for j in input().split()]
from collections import defaultdict
dp=[defaultdict(int)for i in range(n+1)]
dp[0][0]=1
for i,j in enumerate(x,1):
    l=dp[i-1].copy()
    for k in dp[i-1]:
        l[k+j]+=dp[i-1][k]
    dp[i]=l

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

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

x = [i-a for i in x]

d = {0:1}
for i in x:
    nd = d.copy()
    for k,v in d.items():
        if k+i in nd:
            nd[k+i] += v
        else:
            nd[k+i] = v

    d = nd

    #print(d)
print(d[0]-1)

Submission status: Accepted

Solution code:
N,A=list(map(int,input().split()))
x = list(map(int,input().split()))
sx = sum(x)
dp=[[0]*(N+1) for i in range(sx+1)]
dp[0][0]=1
for i in range(N):
  dp_sub=[[0]*(N+1) for j in range(sx+1)]#k枚のカードでsxを表す場合が何通りあるかを記録しておく
  for j in range(sx+1):
    for k in range(N+1):
      if dp[j][k]!=0:
        dp_sub[j+x[i]][k+1]=dp[j][k]
  for j in range(sx+1):
    for k in range(N+1):
      dp[j][k]+=dp_sub[j][k]#dp_subの結果をdpに反映

cnt=0

for i in range(min(sx//A,N)):
  cnt+=dp[A*(i+1)][i+1]
print(cnt)

Submission status: Accepted

Solution code:
card_num, target_average = list(map(int, input().split()))
x = list(map(int, input().split()))

dp = [[[0]*(card_num * target_average + 1) for _ in range(card_num + 1)] for _ in range(card_num + 1)]
dp[0][0][0] = 1

# number of cards to be ranged.
for i in range(card_num):
  # number of cards to be selected.
  for n in range(card_num):
    # total sum.
    for sm in range(card_num * target_average):
      if dp[i][n][sm] == 0:
        continue
      # pattern use xi
      dp[i + 1][n][sm] += dp[i][n][sm]
      # pattern not use xi
      if sm + x[i] <= card_num * target_average:
        dp[i + 1][n + 1][sm + x[i]] += dp[i][n][sm]

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

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=[]
for i in range(n+1):
  dp.append([])
  for i in range(6000):
    dp[-1].append(0)
dp[0][3000]=1
for i in range(n):
  for j in range(6000):
    if j+x[i]<6000 and j+x[i]>=0:
      dp[i+1][j+x[i]]+=dp[i][j]
      dp[i+1][j]+=dp[i][j]
print(dp[n][3000]-1)

Submission status: Accepted

Solution code:
#ARC60 C
N,A=map(int,input().split())
X=[""]+list(map(int,input().split()))
for i in range(1,N+1):
    X[i]-=A

dp=[[0 for j in range(5001)] for i in range(N+1)]

dp[0][2500]=1

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

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

Submission status: Accepted

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

dp = [[[0 for k in range(50 * N + 1)] for j in range(N + 1)] for i in range(N + 1)]

for i in range(N):
    dp[i][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(50 * N + 1):
            if k - X[i] >= 0:
                dp[i + 1][j + 1][k] += dp[i][j][k - X[i]]
            dp[i + 1][j + 1][k] += dp[i][j + 1][k]

res = 0

for j in range(N + 1):
    for k in range(50 * N + 1):
        if k == j * A:
            res += dp[N][j][k]

print(res)

Submission status: Accepted

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

print(dp[-1][2500]-1)

Submission status: Accepted

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

print(dp[-1][2500]-1)

Submission status: Accepted

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

INF = 2500

y = [i-A for i in x]
y.sort()

y1 = [abs(x) for x in y if x < 0]
y2 = [x for x in y if x > 0]

y3 = [x for x in y if x == 0]


def p(y,A):
      dp=[[0 for i in range(A+1)] for j in range(N+1)]
      dp[0][0]=1
      N1 = len(y)
      #DP
      for i in range(N1):
          for j in range(A+1):
              if y[i]<=j: #i+1番目の数字a[i]を足せるかも
                  dp[i+1][j]=dp[i][j-y[i]]+ dp[i][j]
              else: #入る可能性はない
                  dp[i+1][j]=dp[i][j]
      return dp[N1]


dp1 = p(y1,INF)
dp1[0] = 0
dp2 = p(y2,INF)

n = min(len(dp1),len(dp2))

ans = 2 ** len(y3) - 1
for i in range(INF):
    ans += dp1[i] * dp2[i] * (2 ** len(y3))

print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
import sys
import math
from collections import Counter, defaultdict, deque
import copy

# from itertools import product, permutations, combinations, combinations_with_replacement
# from itertools import accumulate
# from operator import itemgetter
# from bisect import bisect_left,bisect
# from heapq import heappop,heappush
# from math import ceil,floor
# from copy import deepcopy
# from heapq import heappop,heappush,heapify
# import heapq


# def combinations(n, r):
# 	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# def gcd(a, b):
# 	if b == 0:
# 		return a
# 	else:
# 		return gcd(b, a%b)
 
# def lcm(a, b):
# 	return a // gcd(a, b) * b

# l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
# c = Counter(l)

# d = defaultdict(int)

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

# リストの要素を改行を挟んで表示する
p2D = lambda x: print(*x, sep="\n")
# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())

def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())

# 入力全てを整数に変換したものの配列を受け取る
# def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI(): return list(map(lambda x:int(x), sys.stdin.readline().split()))
def HI(): return list(map(lambda x:int(x)*(-1), sys.stdin.readline().split()))


N, A=MI()
X = LI()

X = [x-A for x in X]
d = defaultdict(int)
d[0] = 1
for x in X:
	# new_dic = defaultdict(int)
	for k,v in list(d.items()):
		d[k+x] = d[k+x]+v
	# new_dic[x] = d[x] + 1
	# d = new_dic
print(d[0]-1)

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
X = list(map(int,input().split()))
Y = [x-A for x in X]
t = sum(X)
dp = [[0]*(t*2+1) for _ in range(N+1)]
#dp[i][j] -> i枚目まで見る。合計をj-tにするパターン数
#i枚目を使う場合 -> dp[i][j] += dp[i-1][j-Yi]
#i枚目を使わない場合 -> dp[i][j] += dp[i-1][j]
dp[0][t] = 1

for i in range(1,N+1):
    y = Y[i-1]
    for j in range(t*2+1):
        if 0 <= j-y <= t*2:
            dp[i][j] += dp[i-1][j-y]
        dp[i][j] += dp[i-1][j]

print(dp[-1][t]-1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n, a = Is()
X = LI()
Y = [x-a for x in X]
# dp[i][total]
dp = [[0]*101*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
    for j in range(-50*(n+1), 51*(n+1)):
        dp[i][j] += dp[i-1][j]
        dp[i][j+Y[i-1]] += dp[i-1][j]
print(dp[n][0]-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
普通に数え上げDPで行けそう
dp[i][j][k] ->　カードをi枚使う/j種類目のカードまで見る/カードの数字の合計がkになる
j種類目のカードを使う場合：
dp[i][j][k] += dp[i-1][j-1][k-x]
j種類目のカードを使わない場合：
dp[i][j][k] += dp[i][j-1][k]

という風に計算していって、最終的に各iごとにk/i=Aとなるようなkを見出して、dp[i][-1][k]をanswerとして加算する。
"""
N,A = map(int,input().split())
X = list(map(int,input().split()))
sumX = sum(X)
dp = [[[0]*(sumX+1) for _ in range(N+1)]for _ in range(N+1)]
for j in range(N+1):
    dp[0][j][0] = 1
for i in range(1,N+1):
    for j in range(1,N+1):
        x = X[j-1]
        for k in range(1,sumX+1):
            dp[i][j][k] += dp[i][j-1][k]
            if k-x >= 0:
                dp[i][j][k] += dp[i-1][j-1][k-x]
ans = 0
for i in range(1,N+1):
    target = A*i
    if target <= sumX:
        ans += dp[i][-1][target]

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def main():
    N, A, *xlst = map(int, sys.stdin.read().split())
    x_p = []
    x_n = []
    x_z = 0
    for i in xlst:
        if A < i:
            x_p.append(i - A)
        elif i < A:
            x_n.append(A - i)
        else:
            x_z += 1
    x_p.sort(), x_n.sort()

    x_p_sum, x_n_sum = defaultdict(int, {0: 1}), defaultdict(int, {0: 1})

    for i in range(len(x_p)):
        for j in sorted(x_p_sum, reverse=1):
            x_p_sum[j + x_p[i]] += x_p_sum[j]

    for i in range(len(x_n)):
        for j in sorted(x_n_sum, reverse=1):
            x_n_sum[j + x_n[i]] += x_n_sum[j]

    res = sum(x_n_sum[i] * x_p_sum[i] for i in x_p_sum if i in x_n_sum)
    res *= 1 << x_z
    res -= 1
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def main():
    N, A, *xlst = map(int, sys.stdin.read().split())
    x_p = []
    x_n = []
    x_z = 0
    for i in xlst:
        if A < i:
            x_p.append(i - A)
        elif i < A:
            x_n.append(A - i)
        else:
            x_z += 1
    x_p.sort(), x_n.sort()

    x_p_sum = defaultdict(int, {0: 1})
    x_n_sum = defaultdict(int, {0: 1})
    for i in range(len(x_p)):
        for j in sorted(x_p_sum, reverse=1):
            x_p_sum[j + x_p[i]] += x_p_sum[j]

    for i in range(len(x_n)):
        for j in sorted(x_n_sum, reverse=1):
            x_n_sum[j + x_n[i]] += x_n_sum[j]

    res = 0
    for i in x_p_sum:
        if i in x_n_sum:
            res += (x_n_sum[i] * x_p_sum[i])
    res *= 1 << x_z
    res -= 1
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def main():
    N, A, *xlst = map(int, sys.stdin.read().split())
    x_p = []
    x_n = []
    x_z = 0
    xlst.sort()
    for i in xlst:
        if A < i:
            x_p.append(i - A)
        elif i < A:
            x_n.append(A - i)
        else:
            x_z += 1

    x_p_sum = defaultdict(int, {0: 1})
    x_n_sum = defaultdict(int, {0: 1})
    for i in range(len(x_p)):
        for j in sorted(x_p_sum, reverse=1):
            x_p_sum[j + x_p[i]] += x_p_sum[j]

    for i in range(len(x_n)):
        for j in sorted(x_n_sum, reverse=1):
            x_n_sum[j + x_n[i]] += x_n_sum[j]

    res = 0
    for i in x_n_sum:
        if i in x_p_sum:
            res += (x_n_sum[i] * x_p_sum[i])
    res *= 1 << x_z
    res -= 1
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def main():
    N, A, *xlst = map(int, sys.stdin.read().split())
    x_p = []
    x_n = []
    x_z = 0
    for i in xlst:
        i = int(i)
        if A < i:
            x_p.append(i - A)
        elif i < A:
            x_n.append(A - i)
        else:
            x_z += 1
    x_p.sort()
    x_n.sort()
    x_p_sum = defaultdict(int, {0: 1})
    x_n_sum = defaultdict(int, {0: 1})
    for i in range(len(x_p)):
        for j in sorted(x_p_sum, reverse=1):
            x_p_sum[j + x_p[i]] += x_p_sum[j]

    for i in range(len(x_n)):
        for j in sorted(x_n_sum, reverse=1):
            x_n_sum[j + x_n[i]] += x_n_sum[j]

    res = 0
    for i in x_n_sum:
        if i in x_p_sum:
            res += (x_n_sum[i] * x_p_sum[i])
    res *= 1 << x_z
    res -= 1
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def main():
    N, A, *xlst = map(int, sys.stdin.read().split())
    x_p = []
    x_n = []
    x_z = 0
    for i in xlst:
        i = int(i)
        if A < i:
            x_p.append(i - A)
        elif i < A:
            x_n.append(A - i)
        else:
            x_z += 1
    x_p.sort()
    x_n.sort()
    x_p_sum = [defaultdict(int, {0: 1})]
    x_n_sum = [{0: 1}]
    for i in range(len(x_p)):
        x_p_sum.append(defaultdict(int, x_p_sum[-1]))
        for j in sorted(x_p_sum[-2]):
            x_p_sum[-1][j + x_p[i]] += x_p_sum[-2][j]

    for i in range(len(x_n)):
        x_n_sum.append(defaultdict(int, x_n_sum[-1]))
        for j in sorted(x_n_sum[-2]):
            x_n_sum[-1][j + x_n[i]] += x_n_sum[-2][j]

    res = 0
    for i in x_n_sum[-1]:
        if i in x_p_sum[-1]:
            res += (x_n_sum[-1][i] * x_p_sum[-1][i])
    res *= 1 << x_z
    res -= 1
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
l=list(map(int,input().split()))
dp=[0]*5300
dp[l[0]-a]=1

for x in l[1:]:
  b=x-a
  if b>=0:
    for i in range(2500,-2501,-1):
      dp[i+b]+=dp[i]
  else:
    for i in range(-2500,2501):
      dp[i+b]+=dp[i]
  dp[b]+=1
print(dp[0])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np

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

	base = 50*50
	dp = np.zeros(base*2+1,dtype=int)
	dp[base] = 1
	for num in x:
		if num == 0:
			use = dp.copy()
			dp += use
		elif num > 0:
			use = dp[:-num].copy()
			dp[num:] += use
		else:
			use = dp[-num:].copy()
			dp[:num] += use

	print(dp[base]-1)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def main():
    offset = 2500
    W = 2 * offset + 1
    N, A = list(map(int, input().split(' ')))
    x = list(map(int, input().split(' ')))
    y = [xx - A for xx in x]
    dp = [[0 for _ in range(W)] for _ in range(N)]
    dp[0][0 + offset] += 1
    dp[0][y[0] + offset] += 1
    for i in range(1, N):
        for j in range(W):
            dp[i][j] = dp[i - 1][j]
            if 0 <= j - y[i] <= W - 1:
                dp[i][j] += dp[i - 1][j - y[i]]
    print(dp[N - 1][0 + offset] - 1)  # remove the no card case


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

    # https://qiita.com/drken/items/dc53c683d6de8aeacf5a#%E9%A1%9E%E9%A1%8C-3
    
    INF = 10**10  # INF+INFを計算してもオーバーフローしない範囲で大きく
    
    I ,J,K=N,N,A*N
    # dpテーブル dp[i][j][k]:=i番目までからj枚選んで合計kとなる通り数
    dp = [[[0]*(K+1) for _ in range(J+1)]for _ in range(I+1)]
    # 初期条件
    for i in range(I+1):
        dp[i][0][0] = 1
    # ループ
    for i in range(1, I+1):
        for j in range(1,J+1):
            for k in range(K+1):
                if k>=X[i-1]:
                    dp[i][j][k]=dp[i-1][j-1][k-X[i-1]]+dp[i-1][j][k]
                else:
                    dp[i][j][k]=dp[i-1][j][k]

    print(sum([dp[I][j][A*j] for j in range(1,N+1)]))
    

    
resolve()

Submission status: Accepted

Solution code:
import sys

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

# iまでのカードをj枚使って、合計でkである組み合わせ数
MAX_N = N*50 + 1
dp = [[[0 for _ in range(MAX_N)] 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(MAX_N):
            if dp[i][j][k] > 0:
                # i+1番目のカードを選ばない
                dp[i+1][j][k] += dp[i][j][k]
                # i+1番目のカードを選ぶ
                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][A*i]
print(ans)

Submission status: Accepted

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

# DPテーブルを初期化
dp = [[0] * (50*N+1) for x in range(N+1)]
dp[0][0] = 1

# ループを回す
for i in range(N):
    for k in range(N, 0, -1):
        for pt in range(50*N, 0, -1):
            if pt >= X[i]:
                dp[k][pt] += dp[k-1][pt-X[i]]

# print(dp[3])

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

Submission status: Accepted

Solution code:
def main():
    N, A = map(int, input().split())
    x = [0]
    x.extend(list(map(int, input().split())))

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N, A = map(int, input().split())
    x = [0]
    x.extend(list(map(int, input().split())))

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, a, *x = map(int, read().split())
dp = [[0] * max(sum(x) + 1, a * n + 1) for _ in range(n + 1)]
dp[0][0] = 1
ans = 0
for i in range(n):
    for k in range(n - 1, -1, -1):
        for j in range(sum(x)):
            if dp[k][j] != 0:
                dp[k + 1][j + x[i]] += dp[k][j]
for i in range(1, n + 1):
    ans += dp[i][a * i]
print(ans)

Submission status: Accepted

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

    x.insert(0, 0)

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    x.insert(0, 0)

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    x.insert(0, 0)

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a):
    return [0 for i in range(a)]

def Zeros(a,b):
    if(b<=0):
        return Zeros(a)
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



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

dp = [Zeros(3000,n+1) for k in range(n+1)]

dp[0][0][0] = 1
for i in range(n):
    for j in range(2900):
        for k in range(n):
            dp[i+1][j+a[i]][k+1] += dp[i][j][k]
            dp[i+1][j][k] += dp[i][j][k]

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

Submission status: Accepted

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

ans = [[0]*5001 for _ in range(n)]  # -2500 ~ 2500

for i in range(n):
    if i == 0:
        ans[0][x[i]+2500] += 1
    else:
        for j in range(5001):
            if 5000 >= j-x[i] >= 0:
                ans[i][j] = ans[i-1][j] + ans[i-1][j-x[i]]
        ans[i][x[i]+2500] += 1

print(ans[n-1][2500])

Submission status: Accepted

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

from collections import defaultdict

dp = defaultdict(int)

for i in range(N+1):
    for j in range(min(-2500,x[i]-2500),max(2501,2501+x[i])):
        if i == 0 and j == 0:
            dp[(i,j)] = 1
        else:
            dp[(i,j)] = dp[(i-1,j)] + dp[(i-1,j-x[i])]
print(dp[(N,0)]-1)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, A = map(int, input().split())
intA = lambda x: int(x) - A
X = tuple(map(intA, input().split()))

d = defaultdict(int)
for x in X:
    new_d = d.copy()
    for k, v in d.items():
        new_d[k + x] += v
    new_d[x + 2500] += 1
    d = new_d
print(d[2500])

Submission status: Accepted

Solution code:
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

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

sum = 0
for i in range(N):
    sum += x[i]

dp = [[[0]*(3000) for _ in range(55)] for _ in range(55)]
dp[0][0][0] = 1
for i in range(N):
    for j in range(N+1):
        for k in range(2900):
            dp[i+1][j][k] += dp[i][j][k]
            if k >= x[i]:
                dp[i+1][j+1][k] += dp[i][j][k-x[i]]
ans = 0
for j in range(1, N+1):
    ans += dp[N][j][j*A]
print(ans)