Problem:


Score : 300 points

Problem Statement

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

Constraints

1 \leq N \leq 50

1 \leq A \leq 50

1 \leq x_i \leq 50

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

Partial Score

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

Input

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

N A
x_1 x_2 ... x_N

Output

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

Sample Input 1

4 8
7 9 8 9

Sample Output 1

5

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

Select the 3-rd card.

Select the 1-st and 2-nd cards.

Select the 1-st and 4-th cards.

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

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

Sample Input 2

3 8
6 6 9

Sample Output 2

0

Sample Input 3

8 5
3 6 2 8 7 6 5 9

Sample Output 3

19

Sample Input 4

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

Sample Output 4

8589934591

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



Sample input:
4 8
7 9 8 9


Sample output:
5

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

input = sys.stdin.readline


ans = 0
X = []
A = 0

@lru_cache(maxsize=None)
def solve(i, selected, total):
    global X, ans

    if i == len(X):
        if selected != 0 and total == (selected * A):
            return 1
        return 0

    ret = 0
    ret += solve(i + 1, selected + 1, total + X[i])
    ret += solve(i + 1, selected, total)
    return ret


def main():
    global X, ans, A
    N, A = [int(x) for x in input().split()]
    X = [int(x) for x in input().split()]

    print(solve(0, 0, 0))

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,A=map(int,input().split())

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

dp=[[0]*2501 for i in range(50)]

for x in X:
    for i in range(49)[::-1]:
        for index,item in enumerate(dp[i]):
            if item!=0:
                dp[i+1][index+x]+=dp[i][index]
    dp[0][x]+=1

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

print(ans)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
S = max(N * A, sum(X))
DP = [[[0] * (S+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(S+1):
            if not DP[i][j][k]: continue
            DP[i+1][j][k] += DP[i][j][k]
            if j != N:
                DP[i+1][j+1][k+X[i]] += DP[i][j][k]
print(sum(DP[N][j][j*A] for j in range(1, N+1) if j * A <= S))

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
#dp[i][j] := iの数字まで考えたとき、jの数字になる個数
max_s = sum(x)
dp = [[[0 for i in range(max_s + 1)] for j in range(n+1)] for k in range(len(x) + 1)]
#init
dp[0][0][0] = 1
dp[1][0][0] = 1
for i in range(1,n+1):
    num = x[i-1]
    for j in range(len(x)+1):
        for k in range(max_s + 1):
            if k - num < 0:
                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-num]
ans = 0
for i in range(len(x)+1):
    if i * a <= max_s+1:
        ans += dp[-1][i][i*a]
print(ans-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
max_x = max(max(x), A)

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

for i in range(N):
    for k in range(2*N*max_x + 1):
        dp[i+1][k] = dp[i][k]
        if 0 <= k - x[i] and k - x[i] <= 2*N*max_x:
            dp[i+1][k] += dp[i][k - x[i]]

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

Submission status: Accepted

Solution code:
import numpy as np

n,a = map(int, input().split())
X = np.array(input().split(), dtype=np.int64)
Y = X-a
U = max(X.max(), a) * n
dp = np.zeros(2*U+1, dtype=np.int64)
dp[U] = 1
for i in range(n):
  y = Y[i]
  if y >= 0:
    dp[y:] = dp[y:] + dp[:2*U+1-y]
  else:
    dp[:y] = dp[:y] + dp[-y:]
print(dp[U]-1)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

print(dct[0]-1)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
for i in range(N):
  X[i] -= A
D = {0: 1}
for i in X:
  S = [[j, D[j]] for j in D]
  for j in S:
    if j[0] + i in D:
      D[j[0]+i] += j[1]
    else:
      D[j[0]+i] = j[1]
print(D[0]-1)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

dp = [[[0 for _ in range(51)] for __ in range(2501)] for ___ in range(51)]

def main():
    N, A = LI()
    X = LI()
    dp[0][0][0] = 1
    # for i in range(51):
    #     dp[i][0][0] = 1

    for i in range(N):
        for j in range(2501):
            for k in range(N+1):
                if j - X[i] >= 0 and k - 1 >= 0:
                    dp[i+1][j][k] += dp[i][j-X[i]][k-1]
                dp[i+1][j][k] += dp[i][j][k]
    cnt = 0
    for k in range(1, N+1):
        cnt += dp[N][k*A][k]
    print(cnt)
main()

Submission status: Accepted

Solution code:
MAX_INDEX = 51
MAX_SUM = 2505

dp = [[[-1 for _ in range(MAX_INDEX)] for _ in range(MAX_SUM)] for _ in range(MAX_INDEX)]

def waysutil(index, sum, count, arr, K) : 

	if (index < 0) : 
		return 0; 

	if (index == 0) : 

		if (count == 0) : 
			return 0; 
			
		remainder = sum % count; 

		if (remainder != 0) : 
			return 0; 
			
		average = sum // count; 

		if (average == K) : 
			return 1; 

	if (dp[index][sum][count] != -1) : 
		return dp[index][sum][count]; 

	dontpick = waysutil(index - 1, sum, count, arr, K); 


	pick = waysutil(index - 1, sum + arr[index], count + 1, arr, K); 
						
	total = pick + dontpick; 

	dp[index][sum][count] = total; 
	
	return total; 


def ways(N, K, arr) : 

	Arr = []; 

	Arr.append(-1); 
	for i in range(N) : 
		Arr.append(arr[i]); 

	answer = waysutil(N, 0, 0, Arr, K); 
	return answer; 


n, k = map(int, input().split())
arr = list(map(int, input().split()))
N = len(arr)

print("%d" % (ways(N, k, arr)))

Submission status: Accepted

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

# 2 ** 50 -> 全探索は厳しい -> DP
# dp[i][k][wa] = i枚まで見て、k枚選んだ時の合計値がwaとなるときの選び方の合計
# max wa = max(X) * N
max_wa = max(X) * N
dp = [[[0] * (max(X) * (N+1)) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for k in range(i+1):
        for wa in range(max_wa):
            # 選ぶとき
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            # 選ばないとき
            dp[i+1][k][wa] += dp[i][k][wa]

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

print(ans)

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
for i in range(len(x)):
    x[i]-=a
li=[[0]*5001 for i in range(n+1)]
for i in range(n):
    li[i+1][2500+x[i]]+=1
    for j in range(5001):
        if li[i][j]>=1:
            li[i+1][j+x[i]]+=li[i][j]
            li[i+1][j]+=li[i][j]
    # print(li[i+1][2490:2510])
print(li[n][2500])

Submission status: Accepted

Solution code:
import numpy as np


n, a = map(int, input().split())
X = np.array(list(map(int, input().split())))
X -= a

plus = X[X > 0]
zero = X[X == 0]
minus = abs(X[X < 0])

num_count = np.zeros(2551, dtype=np.int64)
num_count[0] = 1

for num in plus:
    num_count[num:] = num_count[:-num] + num_count[num:]

for num in minus:
    num_count[:-num] = num_count[:-num] + num_count[num:]

ans = 2 ** len(zero) * (num_count[0])

print(ans-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, A = map(int, input().split(' '))
import collections

X = [int(a) - A for a in input().split(' ')]
sum_positives = sum([x for x in X if x > 0])
sum_negatives = sum([x for x in X if x < 0])

dp = [dict([(i, 0) for i in range(sum_negatives, sum_positives+1)])
            for _ in range(N+1)]
dp[0][0] = 1

for i, x in enumerate(X):
    for j in range(sum_negatives, sum_positives+1):
        dp[i + 1][j] = dp[i][j]
        if (j - x) in dp[i]:
            dp[i + 1][j] += dp[i][j - x]

# for d in dp:
#     print(d)

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

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:
# -*- coding: utf-8 -*-

import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
# 総和0を平均KとするためKを引く
A = [a-K for a in LIST()]

# dp[i][j] := i番目まで見て、和がjとなる通り数
dp = [defaultdict(int) for i in range(N+1)]
dp[0][0] = 1
for i, a in enumerate(A):
    for k, v in dp[i].items():
        dp[i+1][k] += v
        dp[i+1][k+a] += v
# 部分和が0になった通り数から、1つも選ばない分の1を引く
print(dp[N][0] - 1)

Submission status: Accepted

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

def main():
    N,A = map(int,input().split())
    x = list(map(int,input().split()))
    S = sum(x)
    
    dp = [[[0 for _ in range(S+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):
            for k in range(S):
                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]

    M = S//A
    ans = 0
    for i in range(1,N+1):
        if i*A <= S:
            ans += dp[-1][i][i*A]
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [a[i]-k for i in range(n)]
DP = [[0 for i in range(5100)] for j in range(52)]
for i in range(52):
    DP[i][2530] = 1
for i in range(1,n+1):
    for j in range(5050):
        DP[i][j] = DP[i-1][j] + DP[i-1][j-a[i-1]]
print(DP[n][2530]-1)

Submission status: Accepted

Solution code:

N, M = map(int, input().split())
D = list(map(int, input().split()))
dp = [[0] * 2551 for i in range(51)]
dp[0][0] = 1
for k in D:
    for i in range(49, -1, -1):
        for j in range(2500, -1, -1):
            dp[i+1][j + k] += dp[i][j]

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

Submission status: Accepted

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

MAX_I = 5000
memo = [[0] * MAX_I for _ in range(N + 2)]


def cnv(v):
    return v - A + (MAX_I // 2)


X = [int(_) for _ in input().split()]
for i in range(N):
    offset = X[i] - A
    # print('x', offset)

    mm = memo[i]
    for j in range(MAX_I):
        if mm[j] > 0:
            memo[i + 1][j + offset] += mm[j]
        memo[i + 1][j] += mm[j]

    memo[i + 1][cnv(X[i])] += 1

print(memo[N][MAX_I//2])

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
# 予め-Kした状態で用意しておく
X = [A-int(x) for x in input().split()]
MAX = N*A*2
# dp[i][k] := i枚目までのカードで、合計をkにする通り数
dp = [[0]*(MAX+1) for _ in range(N+1)]
# 負の数を考慮して、N*K位置を0とする
dp[0][N*A] = 1
for i in range(N):
  x = X[i]
  for k in range(MAX+1):
    dp[i+1][k] += dp[i][k]
    if 0 <= k+x <= MAX:
      dp[i+1][k+x] += dp[i][k]
      
# N回終わって合計が0になっている通り数 - 1枚も取らないケース      
print(dp[N][N*A]-1)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
sum_X = sum(X)
dp = [[[0]*(sum_X+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):
    for k in range(sum_X):
      if dp[i][j][k] == 0: continue
      # not used
      dp[i+1][j][k] += dp[i][j][k]
      # used
      dp[i+1][j+1][k+X[i]] += dp[i][j][k]
ans = 0
for k in range(1, N+1):
  if k*A <= sum_X:
    ans += dp[N][k][k*A]
print(ans)

Submission status: Accepted

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

sx = max(abs(x[0]),abs(x[-1]))*n

dp = [[0 for _ in range(2*sx+2)] for _ in range(n+1)]
dp[0][0] = 1

for j in range(n):
    for t in range(-sx-1,sx+1):
        if -sx <= t-x[j] and t-x[j] <= sx: 
            dp[j+1][t] = dp[j][t] + dp[j][t-x[j]]
        else:
            dp[j+1][t] = dp[j][t]

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

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
lists=list(map(int,input().split()))
 
for i in range(n):
    lists[i]-=a
answer=0
dp=[[0 for i in range(5001)] for _ in range(51)]
#dp[i][j]で0からi枚目まで好きなように選択してそのそうわがｊ-2500となるような撮り方の総数
#最終的に求めるのはdp[i][0]である
 
for i in range(n+1):
    for j in range(4951):
        if i>=1 and j>=lists[i-1]:
            dp[i][j]=dp[i-1][j-lists[i-1]]+dp[i-1][j]
        if i>=1 and j<lists[i-1]:
            dp[i][j]=dp[i-1][j]
        else:
            if j==2500 and i==0:
                dp[i][j]=1
            elif j!=2500 and i==0:
                dp[i][j]=0
print(dp[n][2500]-1)

Submission status: Accepted

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

t = 50*n+1
dp = [[0]*t for _ in range(n+1)]

for i in range(n):
  x = l[i]
  for j in reversed(range(n+1)):
    for k in range(t):
      if dp[j][k] != 0:
        dp[j+1][k+x] += dp[j][k]
  dp[0][x] += 1

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

print(ans)

Submission status: Accepted

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

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

dp[0][0][0] = 1
for i in range(1, n+1):
    for s in range(2501):
        for k in range(i):
            # no use
            dp[i][s][k] += dp[i-1][s][k]

            # use
            if s + x[i-1] <= 2500:
                dp[i][s + x[i-1]][k+1] += dp[i-1][s][k]

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

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
import numpy as np
x=np.array(input().split(),dtype=int)
x-=a
pluslist=[]
minuslist=[]
zerocnt=0
for i in range(len(x)):
  if x[i]==0:
    zerocnt+=1
  elif x[i]>0:
    pluslist.append(x[i])
  else:
    minuslist.append(x[i]*(-1))

dpplus=np.full((sum(pluslist)+1),0,dtype=int)
dpminus=np.full((sum(minuslist)+1),0,dtype=int)
dpplus[0]=1
dpminus[0]=1
for v in pluslist:
  for i in range(len(dpplus)-1,-1,-1):
    if dpplus[i]!=0:
      dpplus[i+v]+=dpplus[i]
for v in minuslist:
  for i in range(len(dpminus)-1,-1,-1):
    if dpminus[i]!=0:
      dpminus[i+v]+=dpminus[i]

ans=2**zerocnt-1
for i in range(1,min(len(dpplus),len(dpminus))):
  ans+=dpplus[i]*dpminus[i]*(2**zerocnt)
  
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, A = map(int, input().split())
x = list(map(int, input().split()))
r = 0
l = 0
for y in x:
    y -= A
    if y < 0:
        l += y
    else:
         r += y

M = r-l+1
dp = np.zeros((N+1,M), dtype='i8')
dp[0][-l] = 1

for i in range(1, N+1):
    for j in range(M):
        dp[i][j] = dp[i-1][j]
        j2 = j-x[i-1]+A
        if 0 <= j2 and j2 < M:
            dp[i][j] += dp[i-1][j2]

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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

def main():
    for i in range(n):
        x[i] -= a
    
    c = defaultdict(int)
    c[0] = 1
    for i in x:
        nex = c.copy()
        for val, cnt in c.items():
            nex[val+i] += cnt
        c = nex
    ans = c[0] - 1
    return ans

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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

def main():
    for i in range(n):
        x[i] -= a
    
    c = defaultdict(int)
    c[0] = 1
    for i in x:
        for val, cnt in tuple(c.items()):
            c[val+i] += cnt
    ans = c[0] - 1
    return ans

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

Submission status: Accepted

Solution code:
import sys

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

def main():
    for i in range(n):
        x[i] -= a
    x.sort()

    res = [[0] * 99*n for _ in range(n+1)]
    # res[i][49*n]を中心とする。
    res[0][49*n] = 1
    for i in range(n):
        for j in range(99*n):
            res[i+1][j] += res[i][j]
            cur = x[i]
            if cur >= 0:
                if j >= cur:
                    res[i+1][j] += res[i][j-cur]
            else:
                if j - cur <= 99 * n - 1:
                    res[i+1][j] += res[i][j-cur]
    
    ans = res[n][49*n] - 1
    return ans
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

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

def main():
    ma = a * n
    res = [[[0] * (ma + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    res[0][0][0] = 1
    for i in range(n):
        cur = x[i]
        for j in range(i+2):
            for k in range(ma + 1):
                res[i+1][j][k] += res[i][j][k]
                if k >= cur:
                    res[i+1][j][k] += res[i][j-1][k-cur]
    
    ans = 0
    for j in range(1, n+1):
        ans += res[n][j][j*a]

    return ans

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

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, a = list(map(int, readline().split()))
    x = list(map(int, readline().split()))
    for i in range(n):
        x[i] -= a
    ls = [0] * 5010
    ls[2500] = 1
    for v in x:
        if v == 0:
            for i in range(5010):
                ls[i+v] += ls[i]
        elif v > 0:
            for i in range(5009 - v, -1, -1):
                ls[i+v] += ls[i]
        elif v < 0:
            for i in range(5009 + v):
                ls[i+v] += ls[i]
    print(ls[2500] - 1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np

N, A = map(int,input().split())
X = [int(x) for x in input().split()]
 
dp = np.zeros((N+1,N*A+1),dtype=np.int64)
dp[0,0] = 1
 
for x in X:
    dp[1:,x:] += dp[:-1,:-x].copy()
  
ans = 0
for n in range(1,N+1):
    ans += dp[n,n*A]

print(ans)

Submission status: Accepted

Solution code:
# N枚のカード
# 平均aにしたい
n, a = map(int, input().split())
# 手持ちのカード
x = list(map(int, input().split()))
 
# aとの差を記録してリストに入れなおす
# 「選んだカードの xi の平均が A」であることは，
# 「選んだカードの (xi − A) の合計が 0」と言い換えることができる．
x = list(map(lambda i: i-a, x))
#print(x)
 
# dp初期値(辞書型)
# dp[0] = 1という意味
dp = {0: 1}

#xから1枚取り出す
for i in x:
    #dpにあるすべてのkey,valueに対して、
    #すでにdpにkeyがi+kのデータがあればそのvalue、なければ,0を返し、
    #それ+vをdpとする。
    
    # k=key
    # v=dp[key]のvalue
    for k,v in list(dp.items()):
        dp[i+k]=dp.get(i+k,0)+v
    
    #print(dp)

#全部使わない選択肢だけ、回答から除外する
print(dp[0]-1)
#print(dp)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
*x, = map(int, input().split())
l = N * A + 1

# dp[n枚選ぶ][m枚目まで][総和]
dp = [[[0] * l for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1
for n in range(0, N + 1):
    for m in range(N):
        for s in range(0, l):
            dp[n][m + 1][s] += dp[n][m][s]
            if s >= x[m]:
                dp[n][m + 1][s] += dp[n - 1][m][s - x[m]]

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

Submission status: Accepted

Solution code:
def main():
    N, A = (int(i) for i in input().split())
    X = [int(i) for i in input().split()]
    dp = [[[0 for s in range(N*A + 1)] for k in range(N + 1)]
          for j in range(N + 1)]
    dp[0][0][0] = 1
    for j in range(1, N+1):
        for k in range(0, N+1):
            for s in range(N*A + 1):
                dp[j][k][s] = dp[j-1][k][s]
                if k >= 1 and s - X[j-1] >= 0:
                    dp[j][k][s] += dp[j-1][k-1][s-X[j-1]]
    ans = 0
    for k in range(1, N+1):
        ans += dp[N][k][k*A]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

temp = x + [A]

X = max(temp)

m = N * X

dp = [[[0 for s in range(m+1)] for k in range(N+1)] for j in range(N+1)]

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

res = 0

for j in range(N):
    for k in range(N):
        for s in range(m):
            if dp[j][k][s]:
                dp[j+1][k][s] += dp[j][k][s]
                dp[j+1][k+1][s+x[j]] += dp[j][k][s]

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

print(res)

Submission status: Accepted

Solution code:
import sys
n, a  = [int(i) for i in sys.stdin.readline().split()]
x_ls = [int(i) - a for i in sys.stdin.readline().split()]
#memo_ls[i][j] : i番目まででj - 50*50ができる通り数
memo_ls = [[0 for i in range(2 * 50 * 50 + 1)] for j in range(n+1)]
memo_ls[0][50*50] = 1
for i, x in enumerate(x_ls, 1):
    for j in range(2*50*50+1):
        memo_ls[i][j] =  memo_ls[i-1][j]
        if 0 <= j - x <= 2*50*50:
            memo_ls[i][j] += memo_ls[i - 1][j - x]
print(memo_ls[-1][50*50] - 1)

Submission status: Accepted

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

d = {0: 1}

for cur in X:
  for k, v in list(d.items()):
    d[cur + k] = d.get(cur + k, 0) + v
    
print(d[0]-1)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
s = [{} for i in range(N+1)]
s[0][0] = 1

for i in range(N):
  cur = X[i]
  for j in range(N, 0, -1):
    for k, v in s[j-1].items():
      s[j][cur + k] = s[j].get(cur + k, 0) + v

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

Submission status: Accepted

Solution code:
import numpy as np
hi = np.zeros((5000,60),np.int64)
hi[0,0]=1
n,a = map(int, input().split())
li = [int(it) for it in input().split()]
for i in li:
    hi_ = hi.copy()
    hi[i:-1,1:]+=hi_[:-1-i,:-1]
s = 0
for i in range(n):
  s+=hi[(i+1)*a,i+1]
print (s)

Submission status: Accepted

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

def card(n,a):
	dp=[[[0]*(n*a+1) for i in range(n+1)] for j in range(n+1)]
	dp[0][0][0]=1
	
	for i in range(n):
		for j in range(n):
			for k in range(n*a+1):
				if k<X[i]:
					dp[i+1][j][k]=dp[i][j][k]
				else:# k>=X[i]:
					dp[i+1][j+1][k]=dp[i][j+1][k]+dp[i][j][k-X[i]]
	
	r=0
	for i in range(1,n+1):
		r+=dp[n][i][i*a]
		
	return r
		
print(card(n,a))

Submission status: Accepted

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

#aとの差を記録してリストに入れなおす
x = list(map(lambda i: i-a, x))
#print(x)

#dp初期値
dp = {0: 1}

#dpにぶち込む値をxから取り出す
for num in x:
  #dpにあるすべてのkey,valueに対して、すでにdpにkeyがi+kのデータがあればそのvalueなければ,0を返し、それ+vをdpとする。
  for k,v in list(dp.items()):
    dp[num+k]=dp.get(num+k,0)+v
    
  #print(dp)
#全部使わない選択肢だけ引いておく  
print(dp[0]-1)
#print(dp)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,a=map(int,input().split())
    X=list(map(int,input().split()))
    M=sum(X)
    dp=[[0]*(M+1) for _ in range(n+1)]
    dp[0][0]=1

    from itertools import product
    for x in X:
        ndp=[y[:] for y in dp]
        for i,m in product(range(n),range(M+1)):
            if(m+x<=M):
                ndp[i+1][m+x]+=dp[i][m]
        dp=ndp

    ans=0
    for i in range(1,n+1):
        if(i*a<=M):
            ans+=dp[i][i*a]
    print(ans)
resolve()

Submission status: Accepted

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

# 初期化
max_num = max(max(x), a)
dp = [[[0 for _ in range(max_num * n + 1)]
       for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
 
n, k = map(int, input().split())
x = [int(i) for i in input().split()]
x = [i-k for i in x]
dic = defaultdict(int)

dic[0]=1
for i in x:
    for k,v in list(dic.items()):
        dic[k+i]+=v
print(dic[0]-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, fractions
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = count = 0

def counting(A):
    memo=[0]*2501
    memo[0]=1
    n=len(A)
    for ai in A:
        for i in range(2500,0,-1):
            if i-ai<0:continue
            memo[i]+=memo[i-ai]
    return memo


    

n,X=map(int,input().split())
A,B=[],[]
lis=list(map(int,input().split()))
for li in lis:
    li-=X
    if li<0:
        B.append(-li)
    elif li==0:
        count+=1
    else:
        A.append(li)
count=2**count
A.sort();B.sort()
A=counting(A)
B=counting(B)
for i in range(1,len(A)):
    ans+=A[i]*B[i]*count
ans+=count-1

print(ans)

Submission status: Accepted

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

for i in range(n):
    x[i]-=a
    
dp=[0]*(2*n*50+2)
dp[0]=1
for i in range(n):
    h=dp[:]
    for j in range(-(n-1)*50,(n-1)*50+1):
        h[j]+=dp[j-x[i]]
    dp=h
print(dp[0]-1)

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
x = list(map(lambda i: i-a, x))
dp = {0: 1}

for i in x:
  for k,v in list(dp.items()):
    dp[i+k]=dp.get(i+k,0)+v
print(dp[0]-1)

Submission status: Accepted

Solution code:
from collections import Counter

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

X2 = [0]*N

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

C = Counter([0, X2[0]])

for x in X2[1:]:
    C2 = Counter()
    for s, c in C.items():
        C2[s+x] += c
    C += C2

print(C[0]-1)

Submission status: Accepted

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

for i in range(n):
    lists[i]-=a
answer=0
dp=[[0 for i in range(5001)] for _ in range(51)]
#dp[i][j]で0からi枚目まで好きなように選択してそのそうわがｊ-2500となるような撮り方の総数
#最終的に求めるのはdp[i][0]である

for i in range(n+1):
    for j in range(4951):
        if i>=1 and j>=lists[i-1]:
            dp[i][j]=dp[i-1][j-lists[i-1]]+dp[i-1][j]
        if i>=1 and j<lists[i-1]:
            dp[i][j]=dp[i-1][j]
        else:
            if j==2500 and i==0:
                dp[i][j]=1
            elif j!=2500 and i==0:
                dp[i][j]=0
print(dp[n][2500]-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

offset = 3000

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

dp = [0] * 6000
dp[0 + offset] = 1

for item in x:
    if item < 0:
        for i in range(6000):
            if dp[i] == 0:
                continue 
            dp[i + item] += dp[i]
    else:
        for i in range(6000 - 1, -1, -1):
            if dp[i] == 0:
                continue 
            dp[i + item] += dp[i]
print(dp[offset] - 1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def examC():
    N, A = LI()
    x = LI()
    maxNX = max(x)*N
    dp = [[[0]*(maxNX+1) for _ in range(N+1)]for _ in range(N+1)]
    dp[0][0][0] = 1
    for i in range(1,N+1):
        cur = x[i-1]
        for l in range(N+1):
            for j in range(maxNX + 1):
                dp[l][i][j] += dp[l][i - 1][j]
        for l in range(1,N + 1):
            for j in range(cur, maxNX + 1):
                dp[l][i][j] += dp[l-1][i - 1][j - cur]
#    print(dp)
    ans = int(0)
    for i in range(1,min(maxNX//A+1,N+1)):
        ans += dp[i][N][i*A]
    print(ans)


import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

Submission status: Accepted

Solution code:
# python3 (3.4.3)
import sys
input = sys.stdin.readline

# main
N,A = map(int,input().split())
X = [0] + list(map(int,input().split()))

# dp[n][k][d] : n枚からk枚選んで合計dにする選び方
dp = [[[0 for _ in range(50*N+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for n in range(N+1):
    for k in range(n+1):
        for d in range(50*k+1):
            # 選んだ数がn枚目のカードより小さい場合, そのカードは使えない
            if d < X[n]:
                dp[n][k][d] = dp[n-1][k][d]
            # そうでない場合
            else:
                # k==0のときはカードを選べないことに注意
                if k >= 1:
                    dp[n][k][d] = dp[n-1][k][d] + dp[n-1][k-1][d-X[n]]

ans = 0
for i in range(1,N+1):
    # N枚からi枚選んで平均がA,つまり合計がA*i
    ans += dp[N][i][A*i]

print(ans)