Problem:


Score : 300 points

Problem Statement

Tak has N cards. On the i-th (1 \leq i \leq N) card is written an integer x_i.
He is selecting one or more cards from these N cards, so that the average of the integers written on the selected cards is exactly A.
In how many ways can he make his selection?

Constraints

1 \leq N \leq 50

1 \leq A \leq 50

1 \leq x_i \leq 50

N,\,A,\,x_i are integers.

Partial Score

200 points will be awarded for passing the test set satisfying 1 \leq N \leq 16.

Input

The input is given from Standard Input in the following format:

N A
x_1 x_2 ... x_N

Output

Print the number of ways to select cards such that the average of the written integers is exactly A.

Sample Input 1

4 8
7 9 8 9

Sample Output 1

5

The following are the 5 ways to select cards such that the average is 8:

Select the 3-rd card.

Select the 1-st and 2-nd cards.

Select the 1-st and 4-th cards.

Select the 1-st, 2-nd and 3-rd cards.

Select the 1-st, 3-rd and 4-th cards.

Sample Input 2

3 8
6 6 9

Sample Output 2

0

Sample Input 3

8 5
3 6 2 8 7 6 5 9

Sample Output 3

19

Sample Input 4

33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

Sample Output 4

8589934591

The answer may not fit into a 32-bit integer.



Sample input:
4 8
7 9 8 9


Sample output:
5

Submission status: Accepted

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

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

from collections import defaultdict

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

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

print(counter[0]-1)

Submission status: Accepted

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

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

for i in range(1,N+1):
    x = X[i-1]
    dp[i][1][x] += 1
    for j in range(1,i+1):
        for k in range(1,2501):
            if k-x > 0:
                dp[i][j][k] += dp[i-1][j-1][k-x] + dp[i-1][j][k]
            else:
                dp[i][j][k] += dp[i-1][j][k]

ans = 0

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

Submission status: Accepted

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

dp = [[[0 for _ in range(2555)] for _ in range(55)] for _ in range(55)]
dp[0][0][0]=1
for j in range(n):
    for k in range(n):
        for s in range(a*n+1):
            dp[j+1][k][s] += dp[j][k][s]
            dp[j+1][k+1][s+x[j]] += dp[j][k][s]

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,A = map(int, input().split())
xs = list(map(int, input().split()))
"""
dp[i][j][n] : i枚目において、j枚選んだときの合計がnになる場合の数
dp[i+1][j+1][n+x] = dp[i][j][n] * (x) + dp[i][j+1][n+x]
dp[0][0][0] = 1
"""
Nx = 2550
dp = [[[0]*Nx for i in range(N+10)] for j in range(N+10)]
dp[0][0][0] = 1

for i in range(N):
    x = xs[i]
    for j in range(N):
        for n in range(Nx):
            dp[i+1][j][n] = dp[i][j][n]
    for j in range(N):
        for n in range(Nx):
            if n + x >= Nx:continue
            dp[i+1][j+1][n+x] = dp[i][j][n] + dp[i][j+1][n+x]
    # print(i,dp[i])
cnts = dp[N]
ans = 0
for i in range(1,N+1):
    ans += cnts[i][A*i]
print(ans)

Submission status: Accepted

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

j = n
k = n
t = n * a
maxv = max(a, max(xlist))


dp = [[[0 for t in range(n*maxv + 1)] for k in range(k + 1)] for j in range(j + 1)]

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

# for d in dp:
#     print(d)
# print(dp[1][1][15])

for ji in range(0, j + 1):
    for ki in range(0, ji + 1):
        for ti in range(0, ki * maxv + 1):
            # print('now', ji, ki, ti)
            if ji == 0 and ki == 0 and ti == 0:
                # print('branch 1')
                dp[ji][ki][ti] = 1
            elif ji >= 1 and ti < xlist[ji - 1]:
                dp[ji][ki][ti] = dp[ji - 1][ki][ti]
                # print('branch 2')
            elif ji >= 1 and ki >= 1 and ti >= xlist[ji - 1]:
                # print('branch 3', ji - 1)
                dp[ji][ki][ti] = dp[ji - 1][ki][ti] + dp[ji - 1][ki - 1][ti - xlist[ji - 1]]
            # print(dp[ji][ki][ti])

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

print(count)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys

rl = sys.stdin.readline


def solve():
    N, A = map(int, rl().split())
    x = list(map(int, rl().split()))
    
    y = [xi - A for xi in x]
    dp = [[0] * 5001 for _ in range(N + 1)]
    dp[0][2500] = 1
    
    for i in range(N):
        for j in range(5001):
            if 0 <= j - y[i] < 5001:
                dp[i + 1][j] = dp[i][j] + dp[i][j - y[i]]
            else:
                dp[i + 1][j] = dp[i][j]
    print(dp[N][2500] - 1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools
from fractions import gcd
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in input().split()]
N,A = LI()
_LI = lambda : [int(x)-A for x in input().split()]
X = _LI()

m = [0 for _ in range(50*N)]
Base = 25 * N

for i in range(N):
    m2 = copy.copy(m)
    for j in range(len(m)):
        if m[j]:
            if 0<= j + X[i] < len(m2):
                m2[j+X[i]] += m[j]
    m = m2
    m[X[i] + Base] += 1
print (m[Base])

Submission status: Accepted

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

dp = [defaultdict(int) for _ in range(n+1)]
dp[0][a] += 1

for i, x_i in enumerate(x):
    for p in dp[i].keys():
        pk = p + a - x_i
        dp[i+1][pk] += dp[i][p]
        dp[i+1][p] += dp[i][p]

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

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
X=list(map(int,input().split()))
dp=[[[0]*55 for _ in range(2555)] for _ in range(55)]
ans=0
dp[0][0][0]=1
for i in range(n):
    for j in range(52+50*i):
        for k in range(n):
            ni=i+1
            nj=j+X[i]
            nk=k+1
            dp[ni][nj][nk]+=dp[i][j][k]
            dp[ni][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: Accepted

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

# dp[i枚目のカード][すでに何枚選んでいるか][値]
dp = [[[0] * (max_ + 1) for i in range(n + 1)] for i in range(n + 1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(n):
        for num in range(max_ + 1):
            # i枚目を選ぶ
            if num - x[i] >= 0:
                dp[i + 1][j + 1][num] += dp[i][j][num - x[i]]
            # i枚目を選ばない
            dp[i + 1][j][num] += dp[i][j][num]

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

Submission status: Accepted

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

x_m = []
x_0 = []
x_p = []
for i in range(n):
    tmp = x[i] - a
    if(tmp < 0):
        x_m.append(tmp * -1)
    elif(tmp == 0):
        x_0.append(tmp)
    else:
        x_p.append(tmp)

len_m = (len(x_m))
len_0 = (len(x_0))
len_p = (len(x_p))

dp_m = [[0] * 1300 for i in range(len_m+1)]
dp_p = [[0] * 1300 for i in range(len_p+1)]

dp_m[0][0] = 1
dp_p[0][0] = 1


for i in range(1,len_m+1):
    for j in range(1300):
        dp_m[i][j] = dp_m[i-1][j]
        if(j >= x_m[i-1]):
            dp_m[i][j] += dp_m[i-1][j-x_m[i-1]]

for i in range(1,len_p+1):
    for j in range(1300):
        dp_p[i][j] = dp_p[i-1][j]
        if(j >= x_p[i-1]):
            dp_p[i][j] += dp_p[i-1][j-x_p[i-1]]

ans = 0
for i in range(0,1300):
    ans += dp_m[-1][i] * dp_p[-1][i]

ans = ans * 2**len_0 -1

print(ans)

Submission status: Accepted

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
N,A=map(int,input().split())
X=list(map(int,input().split()))
G=2501
dp=[[0 for i in range((N+1)*G)] for n in range(N)]

X[0]

dp[0][G+X[0]]=1

for n in range(1,N):

    for i in range(len(dp[0])):
        if (X[n]+G)>=0:
            if dp[n-1][i-(X[n]+G)]:
                dp[n][i]=dp[n-1][i-(X[n]+G)]+dp[n-1][i]
            else:
                dp[n][i]=dp[n-1][i]
        else:
            dp[n][i]=dp[n-1][i]
    dp[n][G+X[n]]+=1
    #print([(dp[n][i],i//G,i%G,i%G//(i//G),i) for i in range(len(dp[0])) if dp[n][i]])

print(sum([dp[-1][i] for i in range(len(dp[0])) if i//G and (i%G)%(i//G)==0 and (i%G)//(i//G)==A]))

Submission status: Accepted

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

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

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

for i in range(1, N + 1):
    for j in range(-2500, 2501):
        if 5000 >= j + 2500 - x[i - 1] >= 0:
            dp[i][j + 2500] = dp[i - 1][j + 2500 - x[i - 1]] + dp[i - 1][j + 2500]
        else:
            dp[i][j + 2500] = dp[i - 1][j + 2500]

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

Submission status: Accepted

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

dp=[[[0]*(n*50+1) for i in range(n+1)] for i in range(n)]
#dp[i][j][k]=i番目まででj枚のカードを選んだ時の合計がkになる組み合わせ
dp[0][0][0]=1
dp[0][1][x[0]]=1
for i in range(1,n):
    for j in range(n+1):
        for k in range(n*50+1):
            if dp[i-1][j][k]==0:continue
            #入れるとき
            dp[i][j+1][k+x[i]]+=dp[i-1][j][k]
            #入れない時
            dp[i][j][k]+=dp[i-1][j][k]

ans=0
for j in range(1,n+1):
    for k in range(n*50+1):
        if a*j==k:
            ans+=dp[-1][j][k]
print(ans)
#print(*dp[-1],sep='\n')

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,a = inm()
x = inl()
d = [[[0]*(50*n+1) for i in range(n+1)] for j in range(n+1)]
d[0][0][0] = 1
for i in range(n):
    for j in range(n+1):
        for k in range(50*n+1):
            if d[i][j][k]>0:
                d[i+1][j][k] += d[i][j][k]
                if j<n:
                    d[i+1][j+1][k+x[i]] += d[i][j][k]
sm = 0
for j in range(1,n+1):
    sm += d[n][j][j*a]
print(sm)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

N,A = LI()
x = LI()

# dp[i][j][k]：i枚目まで見て，j枚のカードを使って，和がk
dp = [[[0]*(50*N+1) for _ in range(N+1)] for _ in range(N)]
dp[0][0][0] = 1
dp[0][1][x[0]] = 1

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

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

print(ans)

Submission status: Accepted

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

dp=[[[0]*(a*n+1) for i in range(n+1)] for i in range(n+1)]
dp[0][0][0]=1
#dp[i番目のカード][選んだ枚数][数の合計]=何組あるか
for i in range(n):
    for j in range(n):
        for k in range(a*n+1):
            if k+x[i]<=a*n:
                #i番目を入れる場合
                dp[i+1][j+1][k+x[i]]+=dp[i][j][k]
            #いれない場合
            dp[i+1][j][k]+=dp[i][j][k]
ans=0
cnt=0
#print(*dp,sep='\n')
for i in dp[-1]:
    ans+=i[cnt*a]
    cnt+=1
print(ans-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, A = lr()
X = np.array(lr()) - A
dp = np.zeros(3000, np.int64)
dp[1500] = 1 #1500を原点とする
for x in X:
    if x > 0:
        dp[x:] = dp[x:] + dp[:-x]
    elif x == 0:
        dp[:] = dp[:] + dp[:]
    else:
        dp[:x] = dp[:x] + dp[-x:]

print(dp[1500] - 1)
# 11

Submission status: Accepted

Solution code:
import sys
import numpy as np
from math import factorial

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, A = lr()
X = np.array(lr())
X.sort()
X -= A
pos = X[X>0]
zero = X[X==0]
neg = X[X<0]
limit = max(pos.sum(), neg.sum()) + 10
dp_pos = [0] * limit
dp_neg = [0] * limit
dp_pos[0] = 1
dp_neg[0] = 1
dp_pos = np.array(dp_pos)
dp_neg = np.array(dp_neg)

for p in pos:
    dp_pos[p:] = dp_pos[p:] + dp_pos[:-p]
for n in neg:
    dp_neg[-n:] = dp_neg[-n:] + dp_neg[:n]

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))

  
dp_pos = np.array(dp_pos)
dp_neg = np.array(dp_neg)
Y = dp_pos * dp_neg
if len(zero) + Y.sum() == 0:
    print(0)
    exit()
answer = 2 ** len(zero)
if Y.sum() > 0:
    answer *= np.sum(Y)
print(answer - 1)
#54

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
#dp[i][j][k] := i枚目までカードを選び、合計がjになり、k枚カードを選んだ選び方の総数
#合計のマックスは、xの総和で考える、高々2500なので間に合う
dp = [[[0 for i in range(n+1)] for j in range(sum(x)+1)] for k in range(n+1)]
dp[0][0][0] = 1
for i in range(1,n+1):
    for j in range(sum(x) + 1):
        for k in range(n+1):
            if j + x[i-1] < sum(x) + 1 and k < n:
                dp[i][j + x[i-1]][k+1] += dp[i-1][j][k]
            dp[i][j][k] += dp[i-1][j][k]
ans = 0
for j in range(sum(x)+1):
    for k in range(1,n+1):
        if j == a * k:
            ans += dp[-1][j][k]

print(ans)

Submission status: Accepted

Solution code:
N,A=map(int,input().split())
X=list(map(int,input().split()))
X=[X[i]-A for i in range(0,N)]
dp=[[0 for i in range(0,5000)] for i in range(0,N+1)]#i枚で和がj-2500のもの
dp[0][2500]=1
for i in range(1,N+1):
    for j in range(0,5000):
        if j>=X[i-1] and 4999>=j-X[i-1]:
            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][2500]-1)

Submission status: Accepted

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

offset = 300
dp = [[0]*600 for _ in range(n+1)]
dp[0][offset] = 1
for i in range(1,n+1):
    x = xl[i-1]-a
    for j in range(-300,300):
        dp[i][offset+j] = dp[i-1][offset+j]
        if 600>offset+j-x>=0:
            dp[i][offset+j] += dp[i-1][offset+j-x]

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

Submission status: Accepted

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

# i個のカードまで使って和がjの組み合わせ
dp = [[0 for i in range(50*50+1)] for j in range(51)]
dp[0][0] = 1

for i in range(n):
    for j in range(n-1, -1, -1):
        for k in range(50*50+1):
            if k+xl[i] < 50*50+1:
                dp[j+1][k+xl[i]] += dp[j][k]
ans = 0
for i in range(1,n+1):
    ans += dp[i][i*a]

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left, bisect
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, A = MAP()

x = LIST()

sum_x = sum(x)
dp = [[0]*(sum_x+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
	for j in range(N-1, -1, -1):
		for k in range(sum_x+1):
			if k-x[i] >= 0 and dp[j][k-x[i]]:
				dp[j+1][k] += dp[j][k-x[i]]

ans = 0
for i in range(1, N+1):
	if A*i <= sum_x:
		# print("{}こで総和が{}になる通り:{}".format(i, A*i, dp[i][A*i]))
		ans += dp[i][A*i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
x2 = list(map(int,input().split()))
x = [i-A for i in x2]
maxx = max(max(x2),A)
dp = [[0 for i in range(2*N*maxx+1)] for j in range(N+1)]
start = N*maxx
dp[0][start] = 1
for i in range(1,N+1):
    for j in range(2*start+1):
        if 2*start >= j - x[i-1] >= 0:
            dp[i][j] = dp[i-1][j-x[i-1]] + dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j]
print(dp[-1][start]-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
N, A = inpl()
x = inpl()
y = [ X-A for X in x ]
cur = defaultdict(int)
cur[0] = 1
cur[y[0]] += 1
for i in range(1,N):
    prev = cur
    cur = defaultdict(int)
    for k in prev.keys():
        cur[k] += prev[k]
        cur[k+y[i]] += prev[k]
print(cur[0]-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache
import heapq

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def lcm(a,b):
        return (a * b) // Math.gcd(a,b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3,d + 1,2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7

def main():
    N,A = cin.mapInt()
    X = cin.mapInt()
    dp = [[[0 for k in range(3000)] for j in range(51)]  for i in range(51)]
    dp[0][0][0] = 1
    ans = 0
    for i in range(N):
        for j in range(i + 1):
            for k in range(2500):
                dp[i + 1][j][k] += dp[i][j][k]  
                dp[i + 1][j + 1][k + X[i]] += dp[i][j][k]
    for j in range(1,N + 1):
        ans += dp[N][j][j * A]
    print(ans)
    return

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()))

    M = max(max(X), A)*N
    dp = [[[0 for k in range(M+1)] for j in range(N+1)] for i in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(N):
            for k in range(M):
                if dp[i][j][k]:
                    dp[i+1][j][k] += dp[i][j][k]
                    dp[i+1][j+1][k+X[i]] += dp[i][j][k]
    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()))
for i in range(N):
    X[i] -= A
dp = [[0 for i in range(5001)] for i in range(N+1)]
dp[0][2500] = 1
u = 2500
d = 2500
for i in range(1,N+1):
    x = X[i-1]
    if x <= 0:
        d += x
    else:
        u += x
    for j in range(d,u+1):
        dp[i][j] += dp[i-1][j-x] + dp[i-1][j]
print(dp[N][2500]-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
minans = inf ;ans = 0 ;count = 0 ;pro = 1

n,K=map(int,input().split())
X=list(map(int,input().split()))
# n,K=50,0
# X=[50]*2+[-50]*2
A=[0]*2600
B=[0]*2600
for xi in X:
    xi-=K
    if xi>0:
        for i in range(2599-xi,-1,-1):
            A[i+xi]+=A[i]
        A[xi]+=1
    elif xi==0:count+=1
    else:
        xi=-xi
        for i in range(2599-xi,-1,-1):
            B[i+xi]+=B[i]
        B[xi]+=1
count=2**count
for i in range(2600):
    ans+=A[i]*B[i]*(count)
ans+=count-1
print(ans)
# print(A[50],B[50])
# print(A[:20],B[:20],count,sep="\n")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n,a=map(int,input().split())
    dp=defaultdict(int)
    dp[0]=1

    for x in map(int,input().split()):
        x-=a
        ndp=dp.copy()
        for key,val in dp.items():
            ndp[key+x]+=val
        dp=ndp

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
from copy import copy
def resolve():
    n,a=map(int,input().split())
    X=list(map(lambda x:int(x)-a,input().split()))
    dp=defaultdict(int)
    dp[0]=1
    for x in X:
        ndp=copy(dp)
        for key,val in dp.items():
            ndp[key+x]+=val
        dp=ndp

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n,a=map(int,input().split())
    X=list(map(lambda x:int(x)-a,input().split()))
    dp=defaultdict(int)
    dp[0]=1
    for x in X:
        ndp=defaultdict(int)
        for key,val in dp.items():
            ndp[key]+=val
            ndp[key+x]+=val
        dp=ndp

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

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,a = LI()
    x = LI()
    m = 2501
    d = [[0]*m for i in range(n+1)]
    d[0][0] = 1
    for xi in x:
        for i in range(n)[::-1]:
            ni = i+1
            for j in range(m):
                if not d[i][j]:
                    continue
                k = j+xi
                if k >= m:
                    break
                d[ni][k] += d[i][j]
    ans = 0
    for i in range(1,n+1):
        k = a*i
        if k < m:
            ans += d[i][k]
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
l=list(map(int,input().split()))
for i in range(n):
    l[i]-=a
u=[0]*(3001)
d=[0]*(3001)
ul=[]
dl=[]
z=0
for i in l:
    if i==0:
        z+=1
    elif i<0:
        dl.append(-i)
    else:
        ul.append(i)
        
for i in ul:
    for j in range(3000,-1,-1):
        if u[j]>0 or j==0:
            u[j+i]+=max(1,u[j])
for i in dl:
    for j in range(3000,-1,-1):
        if d[j]>0 or j==0:
            d[j+i]+=max(1,d[j])
ans=0
for i in range(3001):
    ans+=u[i]*d[i]
if ans==0 and z==0:
    print(0)
elif z==0:
    print(ans)
elif ans==0:
    print(2**z-1)
else:
    print((1+ans)*(2**z)-1)

Submission status: Accepted

Solution code:
# dp[i][j][k] i枚処理した　j枚選んだ　和がk の場合の数
n,a = map(int,input().split())
dp = [[[0 for _ in range(3000)] for _ in range(n+1)] for _ in range(n+1)]
l = list(map(int,input().split()))
dp[0][0][0] = 1
s = 0
for i in range(n):
    for j in range(i+1):
        for k in range(s+1):
            if dp[i][j][k]!=0:
                dp[i+1][j][k]+=dp[i][j][k]
                dp[i+1][j+1][k+l[i]]+=dp[i][j][k]
    s+=l[i]
res = 0
for i in range(1,n+1):
    res+=dp[n][i][a*i]
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A, X):
    ans = 0
    Y = [x - A for x in X]
    M = 2*N*50 + 1
    dp = [[0]*M for _ in range(N+1)]

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


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


def main():
    N, A = read_int_n()
    X = read_int_n()
    print(slv(N, A, X))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, A = map(int,input().split())
x = list(map(int,input().split()))
MOD = 5500
DP = [[0]*(MOD) for i in range(N+1)]
DP[0][0] = 1
for i in range(N):
    for j in range(MOD):
        DP[i+1][j] = DP[i][j] + DP[i][(j-A+x[i])%MOD]
print(DP[-1][0] - 1)

Submission status: Accepted

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

p=[];z=0;n=[]
for xi in x:
    if xi>A:
        p.append(xi-A)
    elif xi==A:
        z+=1
    elif xi<A:
        n.append(A-xi)

K=min(sum(p),sum(n))

Pa=[0 for j in range(K+1)];Pa[0]=1
Na=[0 for j in range(K+1)];Na[0]=1

for pi in p:
    for j in range(K,pi-1,-1):
        Pa[j]+=Pa[j-pi]
for ni in n:
    for j in range(K,ni-1,-1):
        Na[j]+=Na[j-ni]

ans=2**z-1 # zのみ
for j in range(1,K+1):
    ans+=2**z*Pa[j]*Na[j]

print(ans)

Submission status: Accepted

Solution code:
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)]
dp[0][0][0]=1

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

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

print(ans)

Submission status: Accepted

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,A=map(int,input().split())
X=[x-A for x in map(int,input().split())]
dp=[0]*(N*100+1)
dp[0]=1
for x in X:
    if x>0:
        for i in range(N*50,-N*50-1,-1):
            if dp[i]>0:
                dp[i+x]+=dp[i]
    else:
        for i in range(-N*50,N*50+1):
            if dp[i]>0:
                dp[i+x]+=dp[i]
print(dp[0]-1)