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:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))

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


DP = [0]*(5001)
DP[2500] = 1

for x in X:
    DP2 = [0]*(5001)
    for i in range(50, 4950):
        DP2[i+x] += DP[i] + DP[i+x]
    DP = DP2

print(DP[2500] - 1)

Submission status: Accepted

Solution code:
def larger(x, y):
	if x > y: return x
	else: return y

N, A = map(int, raw_input().split())
x = map(int, raw_input().split())
x = map(lambda a: a-A, x)
max = larger(x[-1], A)
dp = []

for i in range(0, N+1):
	tmp = []
	for j in range(0, 2*N*max+1):
		tmp.append(0)
	dp.append(tmp)

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

print dp[N][N*max]-1

Submission status: Accepted

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

X = [int(i)-a for i in input().split()]
dp = [[0]*(100*n+1) for i in range(n+1)]
#print(dp)
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]]
        
ans = dp[n][n*50]-1
    
print(ans)

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(lambda x: int(x) - a, input().split()))
dp = [[0 for j in range(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:
def main():
    N, A = map(int, input().split())
    X = tuple(map(int, input().split()))

    x = [i - A for i in X]
    nx = max(A, max(x)) * N
    dp = [[0] * (2 * nx + 1) for _ in [0] * (N + 1)]
    for i in range(N + 1):
        for j in range(2 * nx + 1):
            if not i:
                if j == nx:
                    dp[i][j] = 1
            elif j - x[i-1] < 0 or j - x[i-1] > 2 * nx:
                dp[i][j] = dp[i-1][j]
            elif 0 <= j - x[i-1] <= 2 * nx:
                dp[i][j] = dp[i-1][j] + dp[i-1][j - x[i-1]]
    print(dp[N][nx] - 1)

main()

Submission status: Accepted

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

    x = [i - A for i in X]
    nx = max(X) * N
    dp = [[0] * (2 * nx + 1) for _ in [0] * (N + 1)]
    for i in range(N + 1):
        for j in range(2 * nx + 1):
            if not i:
                if j == nx:
                    dp[i][j] = 1
            elif j - x[i-1] < 0 or j - x[i-1] > 2 * nx:
                dp[i][j] = dp[i-1][j]
            elif 0 <= j - x[i-1] <= 2 * nx:
                dp[i][j] = dp[i-1][j] + dp[i-1][j - x[i-1]]
    print(dp[N][nx] - 1)

main()

Submission status: Accepted

Solution code:
import collections

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

for i in range(n):
    num[i] -= a
sums = collections.Counter([0, num[0]])

for i in num[1:]:
    c = collections.Counter()
    for p, q in sums.items():
        c[i + p] += q
    sums += c
print(sums[0] - 1)

Submission status: Accepted

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

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

for j in range(N+1):
    for t in range(2*N*x_max+1):
        if j >= 1 and 0 <= t - Y[j-1] <= 2*N*x_max:
            dp[j][t] = dp[j-1][t] + dp[j-1][t-Y[j-1]]
        elif j >= 1:
            dp[j][t] = dp[j-1][t]

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

Submission status: Accepted

Solution code:
from collections import Counter

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

sums = Counter([0])

for i in x:
    sums2 = Counter()
    for sm, cnt in sums.items():
        sums2[sm + i] += cnt
    sums += sums2
        
print(sums[0] - 1)

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
x = list(map(int,input().split()))
X = max(max(x),A)
x = [0]+x
dp = [[0 for i in range(2*N*X+1)] for i in range(N+1)]
for j in range(N+1):
    y = x[j]-A
    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)<0 or (t-y>2*N*X)):
            dp[j][t] = dp[j-1][t]
        elif j>=1 and 0<=t-y and t-y<=2*N*X:
            dp[j][t] = dp[j-1][t]+dp[j-1][t-y]
        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) for i in input().split()]
cache = {}
def s(v, k, i):
    if i == n: return int(v > 0 and v == k * a)
    if v > a * n: return 0
    key = (v, k, i)
    if key in cache: return cache[key]
    cache[key] = s(v, k, i + 1) + s(v + x[i], k + 1, i + 1)
    return cache[key]

print(s(0, 0, 0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc044/tasks/arc060_a

"""
import sys
from sys import stdin
input = stdin.readline


def solve(N, A, cards):
    ans = 0
    cards.append(0)
    cards.sort()
    W = sum(cards)

    # dp[j][k][s]: j番目までのカードをk枚使って合計をsにする組み合わせ
    dp = [[[0] * (W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0] = 1

    for j in range(1, N+1):
        card = cards[j]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s < card:
                    dp[j][k][s] = dp[j-1][k][s]
                else:
                    dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-card]

    for k in range(1, N+1):
        if k*A <= W:
            ans += dp[N][k][k*A]
    return ans


def main(args):
    N, A = map(int, input().split())
    cards = [int(x) for x in input().split()]
    ans = solve(N, A, cards)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def c_Tak_and_Cards(N, A, S):
    X = max(S + [A])
    y = [0] + [x - A for x in S]
    dp = [[0 for _ in range(2 * N * X + 1)] for _ in range(N + 1)]
    dp[0][N * X] = 1
    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] < 0 or t - y[j] > 2 * N * X):
                dp[j][t] = dp[j - 1][t]
            elif j >= 1 and 0 <= t - y[j] <= 2 * N * X:
                dp[j][t] = dp[j - 1][t] + dp[j - 1][t - y[j]]
            else:
                dp[j][t] = 0
    return dp[N][N * X] - 1
N,A = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
print(c_Tak_and_Cards(N, A, S))

Submission status: Accepted

Solution code:
N,A=map(int,raw_input().split())
x=[0]+map(int,raw_input().split())
#print x
y=map(lambda i:i-A, x)
#print y

max_x=max(max(x),A)
#print max_x

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

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

print dp[N][N*max_x]-1

Submission status: Accepted

Solution code:
dp = [[0]*6000 for n in range(55)]

# dp[i][0]: -2500をつくれる

dp[0][2500]=1

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

for n, x in enumerate(X):
  t = x - A
  for i in range(6000):
    dp[n+1][i] = dp[n][i]
  for i in range(6000):
    if i+t < 6000 and i+t >= 0:
      dp[n+1][i+t] += dp[n][i]

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

Submission status: Accepted

Solution code:
from collections import defaultdict


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

    dp = [[None] * (50 * 50 + 1) for _ in range(51)]
    dp[0][0] = 1
    for x in x_list:
        for i in range(len(dp) - 2, -1, -1):
            for j in range(len(dp[i])):
                if dp[i][j] is not None:
                    if dp[i + 1][j + x] is None:
                        dp[i + 1][j + x] = 0
                    dp[i + 1][j + x] += dp[i][j]

    ans = 0
    for i in range(1, len(dp)):
        for j in range(len(dp[i])):
            if j == A * i and dp[i][j] is not None:
                ans += dp[i][j]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

N,A = map(int, raw_input().split())
cards = map(int, raw_input().split())

class CardSet:
  def __init__(self, n):
    self.cards = []
    self.combis = [defaultdict(lambda:0) for i in range(n+1)]

  def add_card(self, card):
    self.cards.append(card)
    for n in range(len(self.cards)-1,0,-1):
      for k, v in self.combis[n].items():
        self.combis[n+1][k+card] += v
    self.combis[1][card] += 1

  def avg_count(self, average):
    count = 0
    for n in range(1,len(self.cards)+1):
      count += self.combis[n][n*average]
    return count

  def __str__(self):
    return '\n'.join([str(cs) for cs in self.combis])

cardset = CardSet(N)
for card in cards:
  cardset.add_card(card)
print cardset.avg_count(A)

Submission status: Accepted

Solution code:
N, A = map(int, raw_input().split())
x = [v - A for v in map(int, raw_input().split())]
dp = {}
def dfs(i, W):
    if i < 0:
        return int(W == 0)
    if (i, W) in dp:
        return dp[i, W]
    dp[i, W] = dfs(i-1, W) + dfs(i-1, W-x[i])
    return dp[i, W]
print dfs(N-1, 0) - 1

Submission status: Accepted

Solution code:
def solve():
    N, A = map(int, input().split())
    x = [int(i) for i in input().split()]
     
    lim = sum(x)
    dp = [[0]*(lim + 1) for i in range(N + 1)]
     
    dp[0][0] = 1
     
    for i in range(N):
        for k in range(N, 0, -1):
            for v in range(lim, -1, -1):
                if v - x[i] < 0:
                    break
                dp[k][v] += dp[k - 1][v - x[i]]
     
    ans = 0
     
    for k in range(1, N + 1):
        if k*A > lim:
            break
        ans += dp[k][k*A]
     
    print(ans)
 
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def solve():
    N, A = map(int, input().split())
    x = [int(i) for i in input().split()]
     
    lim = sum(x)
    dp = [[0]*(lim + 1) for i in range(N + 1)]
     
    dp[0][0] = 1
     
    for i in range(N):
        for k in range(i + 1, 0, -1):
            for v in range(lim, x[i] - 1, -1):
                dp[k][v] += dp[k - 1][v - x[i]]
     
    ans = 0
     
    for k in range(1, N + 1):
        if k*A > lim:
            break
        ans += dp[k][k*A]
     
    print(ans)
 
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def solve():
    N, A = map(int, input().split())
    x = [int(i) for i in input().split()]
 
    # 3d DP
    max_x = max(x)
 
    dp = [[[0] * (max_x * N + 1) for j in range(N + 1)]
                                 for i in range(N + 1)]
 
    dp[0][0][0] = 1
 
    for i in range(0, N):
        for k in range(0, N + 1):
            for y in range(max_x * N + 1):
                if dp[i][k][y]:
                    dp[i + 1][k][y] += dp[i][k][y]
                    dp[i + 1][k + 1][y + x[i]] += dp[i][k][y]
                    
    cnt = 0
    for k in range(1, N + 1):
        for y in range(1, max_x * N + 1):
            if y // k == A and y % k == 0:
                cnt += dp[N][k][y]
 
    print(cnt)
 
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

# 3d DP
max_x = max(x)

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

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

for i in range(0, N):
    for k in range(0, N + 1):
        for y in range(max_x * N + 1):
            if dp[i][k][y]:
                dp[i + 1][k][y] += dp[i][k][y]
                dp[i + 1][k + 1][y + x[i]] += dp[i][k][y]
    
cnt = 0
for k in range(1, N + 1):
    for y in range(1, max_x * N + 1):
        if y // k == A and y % k == 0:
            cnt += dp[N][k][y]

print(cnt)

Submission status: Accepted

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

for k in range(1, N + 1):
    if k*A > lim:
        break
    ans += dp[k][k*A]

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

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

    # 3d DP
    max_x = max(x)

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

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

    for i in range(0, N):
        for k in range(0, N + 1):
            for y in range(max_x * N + 1):
                if dp[i][k][y]:
                    dp[i + 1][k][y] += dp[i][k][y]
                    dp[i + 1][k + 1][y + x[i]] += dp[i][k][y]

            # print(dp[i][k])
        # print()

    cnt = 0
    for k in range(1, N + 1):
        for y in range(1, max_x * N + 1):
            if y // k == A and y % k == 0:
                cnt += dp[N][k][y]

    print(cnt)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3

import itertools


def solve(n, a, xs0):
    xs = sorted(xs0)
    xs.insert(0, 0)
    y = max(a, *xs)
    dp = [[[0 for _ in range(n * y + 1)]
          for _ in range(n + 1)] for _ in range(n + 1)]
    g = itertools.product(range(n + 1), range(n + 1), range(n * y + 1))
    for j, k, s in g:
        if j == k == s == 0:
            dp[j][k][s] = 1
        elif j >= 1 and s < xs[j]:
            dp[j][k][s] = dp[j - 1][k][s]
        elif j >= 1 and k >= 1 and s >= xs[j]:
            dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - xs[j]]
    ans = sum(dp[n][k][k * a] for k in range(1, n + 1))
    return ans


def main():
    n, a = (int(x) for x in input().split())
    xs = [int(x) for x in input().split()]
    ans = solve(n, a, xs)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

dp = [[0] * (sum(x)+1) for j in range(N+1)]

dp[0][0] = 1
for i in range(1, N+1):
    for j in list(range(1, N+1))[::-1]:
        for k in list(range(x[i-1], sum(x[:i])+1))[::-1]:
            dp[j][k] += dp[j-1][k - x[i-1]]

print(sum([dp[i][i*A] for i in range(1, N+1) if i*A <= sum(x)]))

Submission status: Accepted

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

MX = max(X)
Y = [0] + [x - A for x in X]
dp = [[0 for _ in range(2 * N * MX + 1)] for _ in range(N+1)]

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

print dp[N][N*MX] - 1

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter


def main():
    n, a = map(int, input().split())
    y = [0] + [int(i) - a for i in input().split()]
    x = max(max(y) + a, a)
    dp = [[0] * (2 * n * x + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        for j in range(2 * n * x + 1):
            if i == 0 and j == n * x:
                dp[i][j] = 1
            elif i >= 1 and (j - y[i] < 0 or j - y[i] > 2 * n * x):
                dp[i][j] = dp[i - 1][j]
            elif i >= 1 and 0 <= j - y[i] and j - y[i] <= 2 * n * x:
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - y[i]]
            else:
                dp[i][j] = 0

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

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

ans = 0
sums = collections.Counter([0, x[0]])

for i in x[1:]:
    temp = collections.Counter()
    for s, c in sums.items():
        temp[s + i] += c
    sums += temp
    #print(sums)

print(sums[0] - 1)

Submission status: Accepted

Solution code:
import sys
import itertools

N, A = map(int, sys.stdin.readline().split())
x = map(lambda x: int(x) - A, sys.stdin.readline().split())
maxX = max(x) + A
dp = [[0 for _a in xrange(N * maxX * 2 + 1)] for _b in xrange(N + 1)]

for j in xrange(N + 1):
    for k in xrange(N * maxX * 2 + 1):
        if j == 0 and k == N * maxX:
            dp[j][k] = 1
        elif j >= 1 and (k - x[j - 1] < 0 or k - x[j - 1] >= 2 * N * maxX):
            dp[j][k] = dp[j - 1][k]
        elif j >= 1 and 0 <= k - x[j - 1] <= 2 * N * maxX:
            dp[j][k] = dp[j - 1][k] + dp[j - 1][k - x[j - 1]]
        else:
            dp[j][k] = 0

print dp[N][N * maxX] - 1

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
dp = [[0 for j in range(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:
N, A = map(int, raw_input().split())
x = map(lambda x: int(x) - A, raw_input().split())
tmp = {}
for xi in x:
    new_tmp = {}
    for k, v in tmp.items():
        new_tmp[k + xi] = v
    new_tmp[xi] = new_tmp.get(xi, 0) + 1
    for k, v in new_tmp.items():
        tmp[k] = tmp.get(k, 0) + v
print tmp.get(0, 0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N, A = map(int, raw_input().split())
x = map(int, raw_input().split())
dp = [[0]*2505 for i in xrange(55)]
for xi in x:
    for i in xrange(2505 - xi - 1, -1, -1):
        for j in xrange(N, 0, -1):
            dp[j + 1][i + xi] += dp[j][i]
    dp[1][xi] += 1

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

Submission status: Accepted

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

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

def well_method(N, A, x):
  dp = [[[1 for a in range(N*50)] for b in range(N+1)] for c in range(N+1)]
  for j in range(N+1):
    for k in range(N+1):
      for s in range(N*50):
        if j == 0 and k == 0 and s == 0:
          dp[j][k][s] = 1
        elif j >= 1 and s < x[j-1]:
          dp[j][k][s] = dp[j-1][k][s]
        elif j >= 1 and k >= 1 and s >= x[j-1]:
          dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
        else:
          dp[j][k][s] = 0

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

def good_method(N, A, x):
  y = {}
  for i in range(len(x)):
    y[i] = x[i] - A
  dp = [[0 for a in range(N*50*2+1)] for b in range(N+1)]
  for j in range(N+1):
    for t in range(N*50*2+1):
      if j == 0 and t == N*50:
        dp[j][t] = 1
      elif j >= 1 and (t - y[j-1] < 0 or t - y[j-1] > N*50*2):
        dp[j][t] = dp[j-1][t]
      elif j >= 1 and 0 <= t - y[j-1] and t - y[j-1] <= N*50*2:
        dp[j][t] = dp[j-1][t] + dp[j-1][t-y[j-1]]
      else:
        dp[j][t] = 0

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

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

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

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:
#ABC044C

n,a=map(int,raw_input().split())
x=map(int,raw_input().split())
dp=[[0 for i in xrange(n*a+1)] for j in xrange(n+1)]
dp[0][0]=1
for k in xrange(n):
 for i in xrange(k,-1,-1):
  for j in xrange(n*a,x[k]-1,-1):
   dp[i+1][j]+=dp[i][j-x[k]]
res=0
for i in xrange(1,n+1):
 res+=dp[i][a*i]
print res

Submission status: Accepted

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

Submission status: Accepted

Solution code:
R=range;(N,A),(*X,)=(map(int,input().split())for _ in R(2));C=[51*N*[0]for _ in R(N+1)];C[0][0]=1
for I in R(N):
	for J in R(N)[::-1]:
		for K in R(50*N)[::-1]:
			if C[J][K]:C[J+1][K+X[I]]+=C[J][K]
print(sum(C[I][I*A]for I in R(1,N+1)))

Submission status: Accepted

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

dp = [0 for _ in range(5050)]

def getdp(i):
    return dp[2550+i]
def setdp(i,val):
    dp[2550+i]=val

setdp(0,1)
for i in range(N):
    diff = X[i]-A
    #print(diff)
    #print(dp[2530:2570])
    #for j,val in enumerate(dp):
    tmpdp = [0 for _ in range(5050)]
    for j in range(5050):
        val = dp[j]
        if val and 0 <=j+diff<5050:
            #print(i,j,val)
            tmpdp[j+diff]+=val
    for i in range(5050):
        dp[i]+=tmpdp[i]


print(dp[2550]-1)

Submission status: Accepted

Solution code:
import collections

n, a = [int(x) for x in input().split()]
X = [int(x) - a for x in input().split()]
ans = 0
sums = collections.Counter([0, X[0]])
for x in X[1:]:
    sums2 = collections.Counter()
    for s, c in sums.items():
        sums2[s + x] += c
    sums += sums2

print(sums[0] - 1)

Submission status: Runtime Error

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

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

ans=0
i=1

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

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

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

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

ans=0

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

print(ans-1)

Submission status: Runtime Error

Solution code:
def function(b, n):
    if n < b:
        return n
    else:
        return function(b, n//b) + n % b
from math import sqrt
def divs(n):
  d=[]
  for x in range(1,int(sqrt(n))+1):
    if n%x==0:
      d.extend([x,n//x])
  d=list(set(d))
  d.sort()
  return d

def main():
    n = int(input())
    s = int(input())

    if n < s:
        return("-1")
    elif n == s:
        return(n+1)
    else:
        ds = divs(n - s)
        for x in ds:
            if s == function(x+1,n):
                return(x+1)
        else:
            return("-1")

print(main())

Submission status: Runtime Error

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

max_X = max(X)
dp = [[[0 for k in range((N + 1) * max_X)]
       for j in range(N + 1)] for i in range(N + 1)]
for i in range(N + 1):
    dp[i][0][0] = 1

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, a = LI()
x = LI()

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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, a = map(int, input().split())
    X = list(map(int, input().split()))
    MAX = sum(X) + 1

    dp = [[[0] * MAX for _ in range(n + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 1
    for i in range(1, n + 1):
        x = X[i - 1]
        for j in range(n):
            for k in range(MAX):
                dp[i][j][k] += dp[i - 1][j][k]
                if k + x < MAX:
                    dp[i][j + 1][k + x] += dp[i - 1][j][k]
    res = 0
    for j in range(1, n + 1):
        res += dp[-1][j][a * j]
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
N,A= list(map(int,input().split()))
l=list(map(int,input().split()))
max_l=max(l)
DP=[[[0]*(max_l*N+1) for _ in range(N+1)] for j in range(N+1)]
DP[0][0][0]=1
for i in range(0,N+1):#カード全体の枚数
   for j in range(0,N+1):
      for k in range(0,N*max_l+1):
         if i >= 1 and k<l[i-1]:
            DP[i][j][k]=DP[i-1][j][k]
         elif j >= 1 and i>=1 and k>=l[i-1]:
            DP[i][j][k]=DP[i-1][j][k]+DP[i-1][j-1][k-l[i-1]]
ans=0
for j in range(1,i):
   ans+=DP[N][j][j*A]
print(ans)

Submission status: Runtime Error

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

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