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()))
y=[i-a for i in x]
y.sort()

ma=max(max(y),-1*min(y))*n
ny=ma*2
dp=[[0]*(ny+1) for _ in range(n+1)]
for i in range(n+1):
  for j in range(ny+1):
    if i==0 and j==ma:
      dp[i][j]=1
    elif i>=1:
      sa=j-y[i-1]
      if sa<0 or sa>ny:
        dp[i][j]=dp[i-1][j]
      else:
        dp[i][j]=dp[i-1][j]+dp[i-1][sa]
print(dp[n][ma]-1)

Submission status: Accepted

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

dp = [[[0 for _ in range(3010)] 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(2500+1):
            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 n in range(1, N+1):
    ans += dp[N][n][n*A]

print(ans)

Submission status: Accepted

Solution code:
N, A = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
dp = dict()
for cur in x:
    dp2 = dict()
    dp2[cur-A] = 1
    for val in dp:
        dp2[cur+val-A] = dp2.get(cur+val-A, 0) + dp[val]
    for val in dp2:
        dp[val] = dp.get(val, 0) + dp2[val]
print(dp.get(0, 0))

Submission status: Accepted

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

    cur = dict()
    cur[X[0]-A] = 1
    for i in range(1, N):
        temp = dict()
        temp[X[i]-A] = 1
        for v in cur:
            temp[v+X[i]-A] = temp.get(v+X[i]-A, 0) + cur[v]
        for v in temp:
            cur[v] = cur.get(v, 0) + temp[v]
    return cur.get(0, 0)

if __name__ == '__main__':

    print(main())

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

xn=[x[i]-A for i in range(len(x)) if x[i]<A]
xn.reverse()
x0=[0 for i in range(len(xn),len(x)) if x[i]==A]
xp=[x[i]-A for i in range(len(xn)+len(x0),len(x)) if x[i]>A]

sxn=[0]
sxn_n=[1]
for x in xn:
  sxn_add=[]
  sxn_n_i=[]
  for j in range(len(sxn)):
    sxn_tmp=sxn[j]+x
    for k in range(len(sxn)):
      if sxn[k]==sxn_tmp or k==len(sxn)-1:
        if sxn[k]==sxn_tmp:
          sxn_n_i.append([k,sxn_n[j]])
        else:
          sxn_add.append([sxn_tmp,sxn_n[j]])
        break
  for l in sxn_n_i:
    sxn_n[l[0]]+=l[1]  
  for k in sxn_add:
    sxn.append(k[0])
    sxn_n.append(k[1])
  

sxp=[0]
sxp_n=[1]
for x in xp:
  sxp_add=[]
  sxp_n_i=[]
  for j in range(len(sxp)):

    sxp_tmp=sxp[j]+x

    for k in range(j,len(sxp)):
      if sxp[k]==sxp_tmp or k==len(sxp)-1:

        if sxp[k]==sxp_tmp:
          sxp_n_i.append([k,sxp_n[j]])
        else:
          sxp_add.append([sxp_tmp,sxp_n[j]])
        break
  for l in sxp_n_i:
    sxp_n[l[0]]+=l[1]
  for k in sxp_add:
    sxp.append(k[0])
    sxp_n.append(k[1])




an=0
for i in range(1,len(sxp)):
  for j in range(1,len(sxn)):

    if sxp[i]==-sxn[j]:
      an+=sxp_n[i]*sxn_n[j]
      break


print(2**len(x0)-1+an*2**(len(x0)))

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = sorted([int(x) for x in input().split()])
from collections import defaultdict , Counter
dp = defaultdict(Counter)

dp[0] = Counter({0:1})

for i in range(1, N+1):
    x = X[i-1]
    k = 0
    update = []
    for s, counter in list(dp.items()):
        for nCard, count in counter.items():
            update.append((s+x, nCard+1, count))

    for key, value, diff in update:
        dp[key][value] += diff

def printCounter(counter):
    if len(counter) == 0:
        return ""
    return dict(counter)
if False:
    for s in range(0, max(X)*N):
        print("%2d" % s, "|", printCounter(dp[s]))

answer = 0
for s, counter in dp.items():
    q, r = divmod(s, A)
    if r != 0:
        continue
    answer += counter[q]
print(answer-1)

Submission status: Accepted

Solution code:
def C_TakandCards():
    from collections import Counter
    from collections import defaultdict
    N, A = map(int, input().split())
    x = list(map(int, input().split()))
    # 0からの差分を取る
    Y = [z - A for z in x]
    d = defaultdict(int)
    # 計算都合で合計値0は0個だが1個と置き後で引く
    d[0] = 1
    # xの全要素について、端から順に0からの差分をkeyとして、その個数をvalueに格納する
    for y in Y:
        for k, v in list(d.items()):
            d[k+y] += v
    print(d[0]-1)
    
if __name__ == "__main__":
    C_TakandCards()

Submission status: Accepted

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

dp = np.zeros((51, 5001), np.int64)  # 50 * 50 = 2500
dp[0, 2500] = 1   # 2500:0, 0:-2500, 5000:2500

for i in range(N):
    for j in range(5001):
        if dp[i, j] != 0:
            dp[i+1, j] += dp[i, j]
            dp[i+1, j+x[i]-A] += dp[i, j]
print(dp[N, 2500] - 1)  # 1つも選ばないパターンを引く

Submission status: Accepted

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

# dp[添え字][枚数][合計] = 選び方
total = sum(x)
dp = [[[0] * (total + 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(total + 1):
            if k + x[i] <= total:
                dp[i + 1][j + 1][k + x[i]] += dp[i][j][k]
            dp[i + 1][j][k] += dp[i][j][k]

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

Submission status: Accepted

Solution code:
num,ave = map(int,input().split())
numx = list(map(int,input().split()))

L = len(numx)
numy = [0] * L
for i in range(L):
    numy[i] = numx[i] - ave

if abs(min(numy)) < abs(max(numy)):
    maxX = max(numy)
else:
    maxX = abs(min(numy))

dp = [[0]*(2*maxX*L+1) for _ in range(L+1)]
dp[0][maxX*L] = 1
for i in range(L):
    for j in range(2*maxX*L+1):
        if (j-numy[i]) < 0 or (j - numy[i]) > 2*maxX*L:
          dp[i+1][j] = dp[i][j]
        else:
          dp[i+1][j] = dp[i][j] + dp[i][j-numy[i]]
print(dp[L][maxX*L]-1)

Submission status: Accepted

Solution code:
n,a = map(int,input().split())
*l, = map(int,input().split())
l = [i-a for i in l] #平均値からの差分に直す。
dp_ll = [[0]*5001 for _ in range(n+1)] #5001で-2500~2500までの範囲をカバー。 
dp_ll[0][2500] = 1 #2501番目がちょうど0となる。
for i in range(0,n):
  for j in range(0,5001):
    if j-l[i] >= 0 and j-l[i] < 5001: #範囲外を参照するのを防止
      dp_ll[i+1][j] = dp_ll[i][j-l[i]]+dp_ll[i][j] 
print(dp_ll[n][2500]-1)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

y = []
for xi in x:
    yi = xi - A
    y.append(yi)
X = max(x + [A])
NX = N * X

dp = defaultdict(int)
dp[(0, 0)] = 1
for i in range(N):
    for t in range(-NX, NX + 1):
        dp[(i + 1, t)] = dp[(i, t)] + dp[(i, t - y[i])]
print(dp[(N, 0)] - 1)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

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

    # dp[i][j][k] := 左からi枚目までに、j枚を選んで、選んだカードの総和がk
    dp = [[[0 for _ in range(50*50+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(0, N):
            for k in range(50*50+1):
                dp[i][j][k] += dp[i-1][j][k]
                if k+X[i] < 50*50+1:
                    dp[i][j+1][k+X[i]] += dp[i-1][j][k]
                    

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:

import collections
import itertools
import sys
import time

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

n,a=getints()
xs=getints()

def key(pos, s, c):
    return (pos * 2600 + s) * 55 + c

cache=[-1] * key(50, 2500, 50)

def solve(pos, s, c):
    if pos == n:
        if s == a * c and c:
            return 1
        else:
            return 0
    k = key(pos,s,c)
    res = cache[k]
    if res >= 0:
        return res
    res = 0
    res += solve(pos + 1, s + xs[pos], c + 1)
    res += solve(pos + 1, s, c)
    cache[k] = res
    return res

print(solve(0,0,0))

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

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

    # dp[i][j][k] := 左からi+1枚目までに、j枚を選んで、選んだカードの総和がkになる場合の数
    dp = [[[0 for _ in range(50*50+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(0, N):
            for k in range(0, 50*50+1):
                dp[i][j][k] += dp[i-1][j][k]  # カードを選ばない
                if k+X[i] < 50*50+1:
                    dp[i][j+1][k+X[i]] += dp[i-1][j][k] # カードを選ぶ
    
    ans = 0
    for j in range(1, N+1):
        ans += dp[N-1][j][A*j]

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
num, ave = map(int, input().split())
numx = list(map(int, input().split()))

L = len(numx)
numy = [0] * L
for i in range(L):
    numy[i]= numx[i] - ave

if abs(min(numy)) < abs(max(numy)):
    maxX = max(numy)
else:
    maxX = abs(min(numy))
dp = [[0] * (2 * maxX * L + 1) for i in range(L+1)]
dp[0][maxX*L] = 1
for i in range(L):
    for j in range(2*maxX*L+1):
        if (j-numy[i]) < 0 or (j-numy[i]) > 2*maxX*L:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = dp[i][j] + dp[i][j-numy[i]]
print(dp[L][maxX*L]-1)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

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

    dp = [[[0 for _ in range(50*50+1)] for __ in range(N+1)] for ___ in range(N+1)]
    dp[0][0][0] = 1  # 何も選んでない初期値

    """
    dp[i][j][k] := 左からi+1枚目までに、j枚のカードを選んで、選んだカードの総和がkになる選び方の総数
    i: 左からi+1枚目のカード
    j: j枚のカードを選んだ
    k: 選んだカードの総和
    """
    for i in range(0, N):
        for j in range(0, N):
            for k in range(50*50+1):
                dp[i+1][j][k] += dp[i][j][k]  # i枚目を選ばない
                if k-X[i] >= 0:
                    dp[i+1][j+1][k] += dp[i][j][k-X[i]]  # i枚目を選んだ

    ans = 0
    for j in range(1, N+1):  # 1枚以上選ぶ必要がある
        ans += dp[N][j][j*A]
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

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

    # dp[i][j] := 左からi+1枚目までにj枚を選んで、選んだカードの総和がkになるカードの選び方
    dp = [[[0 for _ in range(50*50+1)] for __ in range(N+1)] for ___ in range(N+1)]
    dp[0][0][0] = 1  # 何も選んでない初期値
    for i in range(0, N):
        for j in range(0, N):
            for k in range(50*50+1):
                #if dp[i][j][k] != 0:
                if 1:
                    dp[i+1][j][k] += dp[i][j][k]  # i枚目を選ばない
                if k-X[i] >= 0:
                    dp[i+1][j+1][k] += dp[i][j][k-X[i]]  # i枚目を選んだ

    ans = 0
    for j in range(1, N+1):  # 1枚以上選ぶ必要がある
        ans += dp[N][j][j*A]
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: int, x: "List[int]"):
    dp = [[0] * 2501 for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        for s in range(2500, -1, -1):
            for j in range(N):
                if dp[j][s] > 0:
                    dp[j + 1][s + x[i]] += dp[j][s]
    ret = 0
    for i in range(1, N + 1):
        for j in range(2501):
            if j % i == 0 and j // i == A:
                ret += dp[i][j]
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    x = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A, x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from  collections import Counter

def main():
    num, avg = map(int, input().split())
    data = list(map(int, input().split()))
    
    max_num = max(num, avg, max(data))
    dp = [[[0 for i in range(max_num ** 2 + 1)] for j in range(num + 1)] for k in range(num + 1)]
    dp[0][0][0] = 1

    for i in range(1, num + 1):
        now_card = data[i - 1]
        for j in range(num + 1):
            for k in range(max_num ** 2 + 1):
                # print(i, j, k)
                dp[i][j][k] += dp[i - 1][j][k]
                if k - now_card >= 0 and j - 1 >= 0:
                    dp[i][j][k] += dp[i - 1][j - 1][k - now_card]
        # print(dp[i][j])

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





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from  collections import Counter

def main():
    num, avg = map(int, input().split())
    data = list(map(int, input().split()))

    dp = [[[0 for i in range(6000)] for j in range(num + 1)] for k in range(num + 1)]
    dp[0][0][0] = 1

    for i in range(1, num + 1):
        now_card = data[i - 1]
        for j in range(num + 1):
            for k in range(6000):
                # print(i, j, k)
                dp[i][j][k] += dp[i - 1][j][k]
                if k - now_card >= 0 and j - 1 >= 0:
                    dp[i][j][k] += dp[i - 1][j - 1][k - now_card]
        # print(dp[i][j])

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





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
"""解説
dp[j][k][s] := x1,...,xjから k枚選んで xiの合計をsにするような選び方の総数

[@lilium氏]
https://atcoder.jp/contests/abc044/submissions/5887235
"""

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

    max_x = max(X)
    dp = [[[0 for _ in range(4000+1)] for __ in range(N+1)] for ___ in range(N+1)]

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

    # dp[i][j][k] := i枚のうちj枚を選んで、和がkになる組み合わせ
    for i in range(N):
        for j in range(N):
            for k in range(4000+1):
                if dp[i][j][k] != 0:
                    dp[i+1][j][k] += dp[i][j][k]  # i枚目を選ばなかった
                    dp[i+1][j+1][k+X[i]] += dp[i][j][k]  # i枚目を選んだ

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

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
x=list(map(lambda x:int(x)-a,input().split()))
m=min(0,min(x)*n)
M=max(0,max(x)*n)
dp=[1]+[0]*(M-m)
dp[x[0]]+=1
for i in range(n-1):
    l=range(m-x[i+1],M+1) if x[i+1]<0 else range(M-x[i+1],m-1,-1)
    for j in l:dp[j+x[i+1]]+=dp[j]
print(dp[0]-1)

Submission status: Accepted

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

Submission status: Accepted

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

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

n,a = map(int, input().split())
X = list(map(int,input().split()))
Y = list(map(lambda x:x-a, X))
d = defaultdict(int)
d[0] = 1
for y in Y:
    for k,v in list(d.items()):
        d[k+y] += v
print(d[0]-1)

Submission status: Accepted

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

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

n,a = map(int, input().split())
X = list(map(int,input().split()))
Y = list(map(lambda x:x-a, X))
d = defaultdict(int)
d[0] = 1
for y in Y:
    for k,v in list(d.items()):
        d[k+y] += v
print(d[0]-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    k = II()
    x = II()
    y = II()
    ans = 0
    for i in range(n):
        if i >= k:
            ans += y
        else:
            ans += x
    print(ans)
    return

#B
def B():
    w = S()
    d = defaultdict(int)
    for s in w:
        d[s] += 1
    for di in d.values():
        if di % 2:
            print("No")
            return
    print("Yes")
    return

#C
def C():
    n, a = LI()
    x = LI()
    sumx = [0] * n
    for i in range(n):
        sumx[i] = sumx[i - 1] + x[i]
    dp = [[[0] * (n+1) for i in range(sumx[-1] + 1)] for i in range(n)]
    for i in range(n):
        dp[i][x[i]][1] = 1
    for i in range(1, n):
        for s in range(sumx[i] + 1):
            for k in range(1, i + 2):
                if  s >= x[i]:
                    dp[i][s][k] += dp[i - 1][s - x[i]][k - 1]
                dp[i][s][k] += dp[i - 1][s][k]
    ans = 0
    for i in range(1, n + 1):
        if a * i > sumx[-1]:
            break
        ans += dp[-1][a * i][i]
    print(ans)
    return

#D
def D():
    return


#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n, a = li()
x = list(li())

dp = [[[0]*(50*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(n+1):
        for k in range(50*50 + 1):
            dp[i][j][k] += (dp[i-1][j-1][k-x[i-1]] if (j-1 >= 0 and k-x[i-1] >= 0) else 0)\
                            + dp[i-1][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()))
dp = []
for i in range(0, N+1):
	lst1 = []
	for j in range(0, N+1):
		lst2 = []
		for k in range(0, N*50+1):
			lst2.append(0)
		lst1.append(lst2)
	dp.append(lst1)
dp[0][0][0] = 1
for i in range(0, N):
	for j in range(0, N):
		for k in range(0, N*50):
			dp[i+1][j][k] += dp[i][j][k]
			if k+X[i] <= N*50:
				dp[i+1][j+1][k+X[i]] += dp[i][j][k]
ans = 0
for i in range(1, N+1):
	ans += dp[N][i][A*i]
print(ans)

Submission status: Accepted

Solution code:
n, avg = map(int, input().split())
a = list(map(int, input().split()))
mxsm = sum(a) + 5

dp = [[0] * mxsm for _ in range(n + 5)]

dp[0][0] = 1
rs = 0
for x in a:
    dp2 = [[it for it in lin] for lin in dp]
    for i in range(1, n + 1):
        for j in range(x, mxsm + 1):
            if dp[i - 1][j - x]:
                dp2[i][j] += dp[i - 1][j - x]
    dp = dp2

for i in range(1, n + 1):
    if len(dp[i]) > avg * i:
        rs += dp[i][avg * i]

print(rs)

Submission status: Accepted

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

ax = [i - A for i in x]
p, m = 0, 0

for i in ax :
    if i > 0 :
        p += i
    else :
        m -= i

dp = [[0] * (p + m + 1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(N) :
    for j in range(p + m + 1) :
        dp[i+1][(j+ax[i])%(p+m+1)] += dp[i][j]
        dp[i+1][j] += dp[i][j]

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

Submission status: Accepted

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

dp = [[[0 for _ in range(3000)] for _ in range(N+1)] for _ in range(N+1)]


dp[0][0][0] = 1
#iまでを使い、k枚使って、合計がsになる組み合わせ
for i in range(1, N+1):
    for k in range(N+1):
        for s in range(3000):
            dp[i][k][s] = dp[i-1][k][s]
            if s - x[i-1] >= 0 and k >= 1:
                dp[i][k][s] = dp[i-1][k][s] + dp[i-1][k-1][s-x[i-1]]

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

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N,A=map(int,input().split())
X=list(map(int,input().split()))
Y=[_-A for _ in X]
D=defaultdict(int)
D[0]=1
for y in Y:
    for k,v in list(D.items()):D[k+y]+=v
print(D[0]-1)

Submission status: Accepted

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

dp = []
for i in range(n+1):
    dp.append([0]*(2*n*X+1))
for j in range(n,-1,-1):
    for t in range(2*n*X+1):
        if j == n and t ==n*X:
            dp[j][t] = 1
        elif j == n:
            dp[j][t] = 0
        elif 0 <= t-y[j] <= 2*n*X:
            dp[j][t] = dp[j+1][t] + dp[j+1][t-y[j]]
        else:
            dp[j][t] = dp[j+1][t]
def main():
    print(dp[0][n*X]-1)
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]=X[i]-A
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:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, A = nl()
X = nl()

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

dp[0][0][0] = 1
for i in range(1, N+1):
    for j in range(0, N+1):
        for k in range(N*50+1):
            if k < X[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            elif 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]]

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

Submission status: Accepted

Solution code:
base = 2500
n,a = map(int, input().split())
dat_x = list(map(int, input().split()))
dat_x = list(map(lambda x: x - a, dat_x))

#print(dat_x)
dp = []
for i in range(50 + 12):
    dp.append([0] * 5002)

dp[0][base] = 1
#print(dp[0][2500 - 10: 2500 + 10])
for i in range(1, n + 1):
    for j in range(5001):
        dp[i][j] += dp[i - 1][j]

        #print(j + dat_x[i-1])
        if dp[i - 1][j] != 0:
            dp[i][j + dat_x[i-1]] += dp[i - 1][j]
    #print(dp[i][2500 - 10: 2500+10])
print(dp[n][base] - 1)

Submission status: Accepted

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

X = max(x)
if X < A:
    X = A
    
y = []
for i in x:
    y += [i-A]

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

def check(j, t):
    if dp[j][t] != -1:
        return dp[j][t]
    if  j == 0 and t == N * X:
        dp[j][t] = 1
        return 1
    if j >= 1 and (t-y[j-1] < 0 or t-y[j-1] > 2 * N * X):
        dp[j][t] = check(j-1, t)
        return dp[j][t]
    if j >= 1 and 0 <= t-y[j-1] and t-y[j-1] <= 2*N*X:
        dp[j][t] = check(j-1, t) + check(j-1, t- y[j-1])
        return dp[j][t]
    dp[j][t] = 0
    return 0

print (check(N, N*X)-1)

Submission status: Accepted

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

X = max(x)
if X < A:
    X = A

def check(j, k, s):
    if dp[j][k][s] != -1:
        return dp[j][k][s]
    if j == 0 and k == 0 and s == 0:
        dp[j][k][s] = 1
        return 1
    if j >= 1 and s < x[j-1]:
        a = check(j-1, k ,s)
        dp[j][k][s] = a
        return a
    if j >= 1 and k >= 1 and s >= x[j-1]:
        a = check(j-1, k, s) + check(j-1, k-1, s-x[j-1])
        dp[j][k][s] = a
        return a
    dp[j][k][s] = 0
    return 0
        
dp = [[[-1] * (N*X+1) for _ in range(N+1)] for _ in range(N + 1)]
# dp = np.array(dp)
# print (dp)
# for j in range(N+1):
#     for k in range(N+1):
#         for s in range(N*X + 1):
#             print (j, k, s)
#             dp[j][k][s] = check(j, k, s)

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

print (ans)

Submission status: Accepted

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

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

ma = max(X)

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

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

for i in range(1,N+1) :
    for k in range(i+1) :
        for s in range(ma*N+1) :
            if (k >= 1) and (s >= X[i-1]) :
                dp[i][k][s] = dp[i-1][k][s] + dp[i-1][k-1][s-X[i-1]]
            else :
                dp[i][k][s] = dp[i-1][k][s]

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
def sol():
    n,a=map(int,input().split())
    x=[int(i) for i in input().split()]
    ans=chk=0
    d=[[0]*2501 for j in range(51)]
    d[0][0]=1
    for i in x:
        for k in range(50,0,-1):
            for j in range(2500,i-1,-1):
                d[k][j]+=d[k-1][j-i]
    for i in range(1,51):
        ans+=d[i][i*a]
    print(ans)
 
if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
def sol():
    n,a=map(int,input().split())
    x=[int(i) for i in input().split()]
    ans=chk=0
    d=[[0]*2501 for j in range(51)]
    d[0][0]=1
    for i in x:
        for j in range(2500,i-1,-1):
            for k in range(50,0,-1):
                d[k][j]+=d[k-1][j-i]
    for i in range(1,51):
        ans+=d[i][i*a]
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
import numpy as np
import bisect
import itertools

#N, K = map(int, input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#LR = [list(map(int, input().split())) for _ in range(D)]

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

SIZE = N*50
## dp[i][SIZE+j]: i番目までの数字を使って、平均がjになる組み合わせの総数
## 初期化
dp = [[0 for i in range(2*SIZE+1)] for j in range(N+1)]
for i in range(2*SIZE+1): dp[0][i] = 0
dp[0][SIZE] = 1 ## dp[N][SIZE]が答え
  
## DP
for i in range(N):
  for j in range(2*SIZE+1):
    if j-X[i]<0 or j-X[i]>2*SIZE:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = dp[i][j] + dp[i][j-X[i]]

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

Submission status: Accepted

Solution code:
#復習用
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
maxn = max(max(X), A)
 
dp = [[0 for _ in range(2 * N * maxn + 1)] for _ in range(N + 1)]
dp[0][N * maxn] = 1
for i in range(N):
    for k in range(2 * N * maxn + 1):
        dp[i + 1][k] = dp[i][k]
        if 0 <= k - X[i] < 2 * N * maxn:
            dp[i + 1][k] += dp[i][k - X[i]] 
print(dp[N][N * maxn] - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

print(dp[0]-1)

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
l = []
for i in map(int, input().split()):
	l.append(i - a)
l.sort()
pl = sorted([i for i in l if i > 0])
ml = sorted([-i for i in l if i < 0])
M = min(sum(pl), sum(ml))
dpp = [0] * (M + 1)
dpm = [0] * (M + 1)
dpp[0],dpm[0]=1,1
s = 1
for i in pl:
	tmp=dpp[::]
	for j in range(s):
		if i + j <= M:
			dpp[i + j] += tmp[j]
		else:
			break
	s += i
s = 1
for i in ml:
	tmp=dpm[::]
	for j in range(s):
		if i + j <= M:
			dpm[i + j] += tmp[j]
		else:
			break
	s += i
ans=0
for i in range(1,M+1):
	ans+=dpp[i]*dpm[i]
z_cnt=l.count(0)
print(ans*pow(2,z_cnt)+pow(2,z_cnt)-1)