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 bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

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

def sums(arr):
    cntr = Counter([0])
    for v in arr:
        tmps = tuple(cntr.items())
        for u, cnt in tmps:
            cntr[u + v] += cnt
    del cntr[0]
    return cntr

lsums = sums(low)
hsums = sums(high)

ans = sum(hsums[a] * b for a, b in lsums.items())

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

print(ans)

Submission status: Accepted

Solution code:
def inpl():
    return list(map(int, input().split()))


N, A = inpl()
X = inpl()
maxX = max(X)

dp = [[[0 for _ in range(N * maxX + 1)] for j in range(i + 1)]
      for i in range(51)]

dp[0][0][0] = 1
for i in range(N):
    x = X[i - 1]
    for j in range(i + 1):
        for k in range(N * maxX + 1):
            # print(i, j, k)
            if dp[i][j][k] == 0:
                continue
            dp[i + 1][j][k] += dp[i][j][k]
            dp[i + 1][j + 1][k + x] += dp[i][j][k]

ans = 0
for j in range(1, N + 1):
    if j * A > N * maxX:
        continue
    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()))
p=max(max(x),a)
s=[i-a for i in x]
dp=[[0]*(2*n*p+1) for i in range(n+1)]
dp[0][n*p]=1
for i in range(1,n+1):
    for j in range(2*n*p+1):
        if j-s[i-1]<0 or j-s[i-1]>2*p*n:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=dp[i-1][j]+dp[i-1][j-s[i-1]]
print(dp[n][n*p]-1)

Submission status: Accepted

Solution code:
def makelist2(n,m):
    return[[0 for k in range(m)]for i in range(n)]

n,a = map(int,input().split())
x = list(map(int,input().split()))
X = max(x)
X = max(X,a)
b=[]
for i in range(n):
    b.append(x[i]-a)


dp =makelist2(n+1,2*n*X+1)
dp[0][n*X] = 1
for j in range(n+1):
    for t in range(2*n*X+1):
        if j>=1 and (t-b[j-1] < 0 or t-b[j-1]>2*n*X):
            dp[j][t] = dp[j-1][t]
        elif j>= 1:
            dp[j][t] = dp[j-1][t] + dp[j-1][t-b[j-1]]
print(dp[n][n*X]-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 終了後に自力AC 
#
# カードを「Aより小さい」「Aに等しい」「Aより大きい」に分ける。
#
# 「Aより小さい」カードで「和がSになる組み合わせの数」は容易に計算できる。
# 「Aより大きい」カードで「和がTになる組み合わせの数」も計算できる。
#
# あとはこれらを組み合わせるだけ

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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

lower = []
same = 0
upper = []
for x in Xs:
    if x < A:
        lower.append(A - x)
    elif x == A:
        same += 1
    else:
        upper.append(x - A)

def make_counter(nums):
    counter = Counter({0: 1})
    for n in nums:
        new_counter = Counter()
        for k, v in counter.items():
            # 使う場合、使わない場合それぞれの場合の数を増やす
            new_counter[k] += v
            new_counter[k + n] += v
        counter = new_counter
    return counter

lower_counter = make_counter(lower)
upper_counter = make_counter(upper)

ans = 0
for lk, lv in lower_counter.items():
    # (i) Aに等しい数だけ使う
    if lk == 0:
        # ひとつも選ばれない場合を除くために-1
        ans += 2 ** same - 1
    # (ii) それ以外
    else:
        # Aより小さい数たちと、Aより大きい数たちとの集合の平均がちょうどA
        if lk in upper_counter:
            ans += (2 ** same) * lv * upper_counter[lk]

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# ありえる平均は1..50のいずれか

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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

lower = []
same = 0
upper = []
for x in Xs:
    if x < A:
        lower.append(A - x)
    elif x == A:
        same += 1
    else:
        upper.append(x - A)

def make_counter(nums):
    counter = Counter({0: 1})
    for n in nums:
        # 使う場合、使わない場合
        new_counter = Counter()
        for k, v in counter.items():
            new_counter[k] += v
            new_counter[k + n] += v
        counter = new_counter
    return counter

lower_counter = make_counter(lower)
upper_counter = make_counter(upper)

ans = 0
for lk, lv in lower_counter.items():
    # (i) Aに等しい数だけ使う
    if lk == 0:
        # ひとつも選ばれない場合を除くために-1
        ans += 2 ** same - 1
    # (ii) それ以外
    else:
        # Aより小さい数たちと、Aより大きい数たちとの集合の平均がちょうどA
        if lk in upper_counter:
            ans += (2 ** same) * lv * upper_counter[lk]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

na = n*a

DP = [[0]*(na+1) for i in range(n+1)]
DP[0][0] = 1

for _ in range(n):
    x = xs[_]
    next = [[0]*(na+1) for i in range(n+1)]
    for i in range(_+1):
        for j in range(na+1):
            # xを使わないとき
            next[i][j] += DP[i][j]
            if j+x <= na:
                next[i+1][j+x] += DP[i][j]
    DP = next

# i枚使ったとき合計がi*aである場合の数
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())
cards = list(map(lambda x: int(x)-A, input().split()))

X = max(cards)
X = max(X, A)

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

dp[0][N*X] = 1
for i in range(N):
    for j in range(2*N*X+1):
        c = cards[i]
        if j - c < 0 or j-c > 2*N*X:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = dp[i][j]+dp[i][j-c]


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(max(x), A)

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

dp[0][N*X] = 1

y = []

for i in range(N):
    tmp = x[i]-A
    y.append(tmp)

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

Submission status: Accepted

Solution code:
# coding: utf-8

II = lambda: int(input())
MI = lambda: map(int, input().split())


def sumcnt(values):
    sc = [0] * (50 * 50 + 1)
    sc[0] = 1
    max_sc = 0
    for v in values:
        for i in range(max_sc, -1, -1):
            sc[i + v] += sc[i]
        max_sc += v
    return sc, max_sc


def main():
    N, A = MI()
    ds = [x-A for x in MI()]

    count0 = 0
    dp, dm = [], []
    for d in ds:
        if d == 0: count0 += 1
        elif d > 0: dp.append(d)
        else: dm.append(-d)
    dp.sort()
    dm.sort()

    scp, scpmax = sumcnt(dp)
    scm, scmmax = sumcnt(dm)

    ans = 0
    for i in range(1, min(scpmax, scmmax) + 1):
        ans += scp[i] * scm[i]
    ans = ans * (2**count0) + 2**count0 - 1
    return ans


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

Submission status: Accepted

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

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

L=[0 for i in range(5001)]
L[2500]=1

for i in range(N):
    if x[i]>=0:
        for j in range(5001):
            if L[5000-j]>0:
                L[5000-j+x[i]]+=L[5000-j]
    elif x[i]<0:
        for j in range(5001):
            if L[j]>0:
                L[j+x[i]]+=L[j]
print(L[2500]-1)

Submission status: Accepted

Solution code:
N, A = map(int, input().split(' '))
X = list(map(int, input().split(' ')))
# ans_map[x][y] x+1枚選んで和がyになる組み合わせの数
ans_map = [[0 for i in range(50*(j+1)+1)] for j in range(N)]
count = 0
for n in X:
    count += 1
    for x in range(0, count)[::-1]:
        for y in range(len(ans_map[x])):
            if ans_map[x][y] != 0:
                ans_map[x+1][y+n] += ans_map[x][y]
    ans_map[0][n] += 1
ans = 0
for i in range(N):
    ans += ans_map[i][A*(i+1)]
print(ans)

Submission status: Accepted

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

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


X = max(max(x), A)

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

dp[0][N*X] = 1

y = []

for i in range(N):
    tmp = x[i]-A
    y.append(tmp)

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

Submission status: Accepted

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

dp = [[[0 for i in range(2555)] for j in range(55)] for k in range(55)]

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

for i in range(N):
    for j in range(N):
        for k in range(2501):
            if dp[i][j][k] <= 0:
                continue
            dp[i+1][j][k] += dp[i][j][k]
            dp[i+1][j+1][k+x[i]] += dp[i][j][k]

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

Submission status: Accepted

Solution code:
from collections import defaultdict
H = defaultdict(lambda: 0)
H[0] = 1
def inpl(): return [int(i) for i in input().split()]
N, A = inpl()
x = inpl()
x = [i-A for i in x]
H[0]= 1
for i in x:
    for ni,nv in H.copy().items():
        H[ni+i] += nv
print(H[0]-1)

Submission status: Accepted

Solution code:
(n, a) = list(map(int, input().split()))
x = list(map(int, input().split()))
plus = []
minus = []
zero = 0
for i in range(n):
    x[i] -= a
    if x[i] > 0:
        plus.append(x[i])
    elif x[i] < 0:
        minus.append(x[i])
    else:
        zero += 1


map_plus = {}
map_minus = {}

for i in plus:
    tmp_map = map_plus.copy()
    if i in map_plus:
        tmp_map[i] += 1
    else:
        tmp_map[i] = 1
    for j in map_plus:
        if j + i in map_plus:
            tmp_map[j + i] += map_plus[j]
        else:
            tmp_map[j + i] = map_plus[j]
    map_plus = tmp_map

for i in minus:
    tmp_map = map_minus.copy()
    if i in map_minus:
        tmp_map[i] += 1
    else:
        tmp_map[i] = 1
    for j in map_minus:
        if j + i in map_minus:
            tmp_map[j + i] += map_minus[j]
        else:
            tmp_map[j + i] = map_minus[j]
    map_minus = tmp_map

count = 1
for i in map_minus:
    if i * -1 in map_plus:
        count += map_minus[i] * map_plus[i * -1]

print(count * 2 ** zero - 1)

Submission status: Accepted

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
x = [t-a for t in x]
p = [0]*5010
p[0] = 1
q = [0]*5010
for t in x:
  for i in range(5010):
    q[i] = p[i] + p[(i-t)%5010] 
  for i in range(5010):
    p[i] = q[i]
print(p[0]-1)

Submission status: Accepted

Solution code:
n,a=map(int, input().split())
x=list(map(int, input().split()))
x=[i-a for i in x]
d={0:1}
for i in x:
    for j,k in list(d.items()):
        d[i+j]=d.get(i+j,0)+k
print(d[0]-1)

Submission status: Accepted

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

sumX = sum(xs)

# dp[i][j]: i枚で合計jとなる選び方の個数
dp = [[0] * (sumX + 1) for _ in range(N + 1)]
dp[0][0] = 1
for k, x in enumerate(xs):
    for i in reversed(range(k + 1)):
        for j in range(sumX + 1):
            if dp[i][j] == 0: continue
            dp[i + 1][j + x] += dp[i][j]

# 平均A = i枚で合計(A*i)
ans = 0
for i in range(1, min(N, sumX // A) + 1):
    ans += dp[i][A * i]
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 for _  in range(n * 2 * max_x + 1)] for _ in range(n + 1)]

dp[0][n * max_x] = 1
for i in range(1, n + 1):
    for j in range(1, n * 2 * max_x + 1):
        if 0 <= j + a - x[i - 1] <= 2 * n * max_x:
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j + a - x[i - 1]]
        else:
            dp[i][j] = dp[i - 1][j]

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

# dp[i][j]: i番目, j合計
dp = [defaultdict(int) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for key in dp[i]:
        dp[i + 1][key + x[i]] += dp[i][key]
        dp[i + 1][key] += dp[i][key]

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

Submission status: Accepted

Solution code:
f = lambda: list(map(int,input().split()))

n,a = f()
x = [int(x)-a for x in input().split()]
w = max(max(x),abs(min(x)),a)*n
dp = [[0 for _ in range(2*w + 1)] for _ in range(n+1)]
dp[0][w] = 1
for i in range(n):
    for j in range(2*w + 1):
        if 0 <= j-x[i] <= 2*w:
            dp[i+1][j] = dp[i][j-x[i]] + dp[i][j]
        else:
            dp[i+1][j] = dp[i][j]

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
dd[0]+=1
for i in range(N):
    dd1=defaultdict(int)
    for s,v in dd.items():
        dd1[s+A[i]-K]+=v
        dd1[s]+=v
    dd=dd1
print(dd[0]-1)

Submission status: Accepted

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

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

Submission status: Accepted

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

d = {}
d[0] = 1
for i in x:
    for j,k in list(d.items()):
        d[j+i] = d.get(j+i,0)+k
print(d[0]-1)

Submission status: Accepted

Solution code:
# 通らなかった

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

for j in range(1, n+1):
  for k in range(n+1):
    for s in range(n*m+1):
      if s<x[j-1]:
        dp[j][k][s] = dp[j-1][k][s]
      elif k>=1:
        dp[j][k][s] = dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]
ans = 0
for i in range(1, n+1):
  ans += dp[n][i][i*a]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

x = [x - A for x in x]

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

for x_i in x:
    copy = dict(counter)
    for d, c in copy.items():
        counter[d+x_i] += c

print(counter[0]-1)

Submission status: Accepted

Solution code:
n, a = map(int, raw_input().split())
f = [0 for i in range(6000)]
f[0] = 1
for x in map(int, raw_input().split()):
	x -= a
	g = f[::]
	for i in range(-3000, 3000):
		g[i + x] += f[i]
	f = g
print g[0] - 1

Submission status: Accepted

Solution code:
#ARC060 C
#すごいdpを思いつく人もいるものだと思う
'''
直感的には？
- dp[i][t] = dp[i-1][t]+dp[i-1][t-X[i-1]]
    取らなかった場合の数＋取ってこの値にした場合の数
    t=0で-2を取るか取らないかを迫られた時、取ればt=+2から2引いてt=0に来て、取らねばt=0はt=0から来る
- dp[i][t] = dp[i-1][t]
    取らなかった場合の数で、
    「起こり得ない数からの遷移はしない」と考えた場合dp[i-1][t-X[i-1]]が不要になるというだけ
    無理に取ろうとすると配列外参照となる
- dp[0][N*MX] = 1
    初期状態では当然、平均は0なので
- それ以外
    i=0の時しかないが、初期状態で平均が他の値になることはない
'''

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

MX = max(X+[0])

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

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

Submission status: Accepted

Solution code:
from copy import deepcopy

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

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

cnt = [0] * 5000

for x in X:
    cnt2 = [0] * 5000
    for i in range(-2500, 2500):
        cnt2[i + x] += cnt[i]
    cnt2[x] += 1
    for i in range(5000):
        cnt2[i] += cnt[i]
    cnt = deepcopy(cnt2)

print(cnt[0])

Submission status: Accepted

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

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

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
X.sort()

p = { 0: 1 }
for x in X:
  for n, count in list(p.items()):
    if n+x <= 0:
      p[n+x] = p.get(n+x, 0) + count

print(p[0] - 1)

Submission status: Accepted

Solution code:
N,A=map(int,input().split())
x=list(map(int,input().split()))
X=max(max(x),A)
y=[x[i]-A for i in range(N)]
dp=[[0 for i in range(2*N*X+1)] for j in range(N+1)]
dp[0][N*X]=1
for j in range(1,N+1):
  for k in range(2*N*X+1):
    dp[j][k]=dp[j-1][k]
    if 0<= k-y[j-1] and k-y[j-1]<=2*N*X:
      dp[j][k]+=dp[j-1][k-y[j-1]]
print(dp[N][N*X]-1)

Submission status: Accepted

Solution code:
N,A=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0 for i in range(50*50+1)] for j in range(N+1) ]for k in range(N+1)]
dp[0][0][0]=1
for i in range(1,N+1):
  for j in range(N+1):
    for k in range(50*50+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(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
n, a = map(int, input().split())
l_a = list(map(lambda x: int(x) - a, input().split()))

dic = dict()
dic[0] = 1
for x in l_a:
    for key, value in list(dic.items()):
        dic[x + key] = value + dic.get(x+key,0)

print(dic[0] - 1)

Submission status: Accepted

Solution code:
# coding: utf-8
num_N, num_A = map(int, input().split())
l_card = list(map(int, input().split()))

l_card_ave = [i - num_A for i in l_card]

dict_ans = dict()
dict_ans[0] = 1
for card in l_card_ave:
    for key, value in list(dict_ans.items()):
        dict_ans[key + card] = dict_ans.get(key + card, 0) + value

print(dict_ans[0] - 1)

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import defaultdict

num_card, num_ave = map(int, input().split())
l_card = map(lambda x: int(x) - num_ave, input().split())

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

for card in l_card:
    for d, c in list(counter.items()):
        counter[d + card] += c

print(counter[0] - 1)

Submission status: Accepted

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

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

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

print(f())

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

Submission status: Accepted

Solution code:
N, A = map(int, raw_input().split())
a = sorted(map(lambda x:int(x)-A, raw_input().split()))
mem = {}

def rec(p, acm):
    if (p, acm) in mem:
        return mem[(p, acm)]
    if p >= N:
        return 0
    if a[p] > 0 and acm > 0:
        return 0
    mem[(p, acm)] = rec(p+1, acm+a[p]) + rec(p+1, acm)
    if acm+a[p] == 0:
        mem[(p, acm)] += 1
    return mem[(p, acm)]

print rec(0, 0)

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
x=[0]+[i-a for i in map(int,input().split())]
d={}
def f(i):
    if i==n+1:
        return {0:1}
    if i in d:
        return d[i]
    d[i]={}
    for j in range(i+1,n+2):
        for k,v in f(j).items():
            d[i].setdefault(x[i]+k,0)
            d[i][x[i]+k]+=v
    return d[i]
print(f(0)[0]-1)

Submission status: Accepted

Solution code:
def makelist(n, m, p):
	return [[[0 for k in range(p)] for i in range(m)] for j in range(n)]

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

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

d = dict()
d[0] = 1
for x in xs:
    for s, v in list(d.items()):
        d[s + x] = d.get(s + x, 0) + v

print(d[0]-1)

Submission status: Accepted

Solution code:
def solve():
	N,A = map(int,raw_input().split())
	x = map(int,raw_input().split())
	ofs = N*50; M = ofs*2 + 1
	DP = [[0]*M for i in xrange(N+1)]
	DP[0][ofs] = 1
	for i in xrange(N):
		for j in xrange(M):
			if DP[i][j] == 0: continue
			DP[i+1][j+x[i]-A] += DP[i][j]
			DP[i+1][j] += DP[i][j]
	print DP[N][ofs] - 1
solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
def solve():
	N,A = map(int,raw_input().split())
	x = map(int,raw_input().split())
	DP = [defaultdict(int) for i in xrange(N+1)]
	DP[0][0] = 1
	for i in xrange(N):
		for k,v in DP[i].iteritems():
			DP[i+1][k+x[i]-A] += v
			DP[i+1][k] += v
	print DP[N][0] - 1
solve()

Submission status: Accepted

Solution code:

from collections import defaultdict
N, A = map(int, input().split())

X = map(lambda s: int(s) - A, input().split())

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

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

print(counter[0]-1)

Submission status: Accepted

Solution code:
from sys import exit

def reads():
  return [int(x) for x in input().split()]

(N, A) = reads()
x = reads()

d = dict()

d[0] = 1

for i in range(N):
  for (s, N) in list(d.items()):
    k = s + x[i] - A
    d[k] = d.get(k, 0) + N

print(d[0]-1)

Submission status: Accepted

Solution code:
n,a=map(int,raw_input().split())
x=map(int,raw_input().split())
x.sort()
dp=[[[0]*(n+1) for i in xrange(n*a+1)] for j in xrange(n+1)]
for i in xrange(n+1):
    dp[i][0][0]=1
ans=0
for i in xrange(n):
    for j in xrange(1,n*a+1):
        for k in xrange(1,n+1):
            if i+1<k:break
            if j<x[i]:
                dp[i+1][j][k]=dp[i][j][k]
                continue
            dp[i+1][j][k]=dp[i][j][k]+dp[i][j-x[i]][k-1]
for j in xrange(1,n*a+1):
    for k in xrange(1,n+1):
        if j==a*k:
            ans+=dp[n][j][k]
print(ans)

Submission status: Accepted

Solution code:
import collections

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

x = [int(s) for s in input().split()]

S = [collections.Counter() for _ in range(51)]

S[0][0] = 1
for i, xi in enumerate(x):
    prev = [(k,s,c) for k in range(i+1) for s,c in S[k].items()]
    for (k,s,c) in prev:
        S[k+1][s+xi] += c
    #print(sum(sum(S[k].values()) for k in range(i+1)))

ans = 0
for (k, s, c) in ((k,s,c) for k in range(1,N+1) for s,c in S[k].items()):
    if A*k == s:
        ans += c

print(ans)

Submission status: Accepted

Solution code:

line1=input().split()
n=int(line1[0])
a=int(line1[1])
nums=input().split()
for i in range(n):
    nums[i]=int(nums[i])-a

works={}

works[0]=1
s=0
for x in nums:

    if x>=0:
        for i in range(50*(n+1),-50*(n+1), -1):
            try:
                works[i]+=works[i-x]
            except:
                try:
                    works[i]=works[i-x]
                except:
                    pass
    else:
        for i in range (-50*(n+1),50*(n+1)):
            try:
                works[i+x]+=works[i]
            except:
                try:
                    works[i+x]=works[i]
                except:
                    pass

print (works[0]-1)

Submission status: Accepted

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

X = map(int, input().split(' '))
X = [x - A for x in X]

from collections import defaultdict
counter = defaultdict(int)
counter[0] = 1

for x in X:
	copy = dict(counter)
	for d,c in copy.items():
		counter[d+x] += c

print(counter[0]-1)

Submission status: Accepted

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

INF = float('inf')

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

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

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

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

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

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

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

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

###########

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

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

print ans

Submission status: Accepted

Solution code:
n, a = map(int, raw_input().split())
values = sorted(map(lambda s: int(s) - a, raw_input().split()))
counts = {}
for x in values:
    items = counts.items()
    for a, count in items:
        y = x + a
        counts[y] = counts.setdefault(y, 0) + count
    counts[x] = counts.setdefault(x, 0) + 1
print(counts[0] if 0 in counts else 0)

Submission status: Runtime Error

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

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

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

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

print(ans)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import bisect

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


dp=[[0]*(2*N*A+1) for _ in [0]*(N+1)]
dp[0][N*A]=1
# dp[n][k]:n番目までの整数でkが作れる場合の数
    
for n in range(1,N+1):
    for k in range(-N*A,N*A+1):
        dp[n][k]+=dp[n-1][k-x[n-1]]+dp[n-1][k]

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