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
#x.sort()
#print(x)
#dp[i][j]: i枚目まで、値ｊ
dp = [[0]*5001 for _ in range(n+1)]
dp[0][2500]=1
for i in range(0,n):
    for j in range(0,5001):
        if (dp[i][j]!=0):
            dp[i+1][j] += dp[i][j]
            dp[i+1][j+x[i]] += dp[i][j]
print(dp[n][2500]-1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
    n,a=MI()
    lis=LI()
    for i in range(n):
        lis[i]-=a
    #print(lis)
    dp=[[0]*5001 for i in range(n+1)]
    dp[0][2500]=1
    for i in range(n):
        num=lis[i]
        for j in range(5001):
            dp[i+1][j]+=dp[i][j]
            if 0<=j+num<5001:
                dp[i+1][j+num]+=dp[i][j]
    #print(dp)
    print(dp[-1][2500]-1)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SLR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if args else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    N, A = LI()
    X = LI()
    Y = [xi - A for xi in X]
    z = max(A, max(X))

    dp = make_list(N+1, 2*z*N+1)
    dp[0][z*N] = 1

    for i in range(1, N+1):
        for s in range(2*z*N+1):
            if 0 <= s - Y[i-1] <= 2*z*N:
                dp[i][s] = dp[i-1][s] + dp[i-1][s - Y[i-1]]
            else:
                dp[i][s] = dp[i-1][s]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SLR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if args else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    N, A = LI()
    X = LI()

    dp = make_list(N+1, N+1, 2501)
    dp[0][0][0] = 1

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


for i in range(n):
    for k in range(n):
        for s in range(sum(x)+1):
                dp[i+1][k][s] += dp[i][k][s]
                dp[i+1][k+1][s+x[i]] += dp[i][k][s]

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

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n,a = i_map()
    x = i_list()
    x.insert(0,0)

    dp = [[[0]*(n*a+1) 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, n*a + 1):
                dp[i][j][k] = dp[i - 1][j][k]
                if k >= x[i]:
                    dp[i][j][k] += dp[i - 1][j - 1][k - x[i]]

    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())
from collections import defaultdict
dp=defaultdict(int)
dp[0]=1
for i in map(int,input().split()):
    i-=a

    for k in sorted(dp.keys(),reverse=(i>=0)):
        dp[k+i]+=dp[k]
print(dp[0]-1)

Submission status: Accepted

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

dp = [[[0] * 2550 for i in range(55)] for i in range(55)]

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

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

print(ans)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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

def main():
  n,a=LI()
  l=LI()

  dp=[[[0]*51 for _ in range(2501)] for __ in range(n+1)]
  dp[0][0][0]=1
  for i in range(n):
    nd=l[i]
    for j in range(2500):
      for k in range(50):
        ni=i+1
        nj=j
        nk=k

        dp[ni][nj][nk]+=dp[i][j][k]

        nj+=nd
        nk+=1

        if nj>2500:
          continue

        dp[ni][nj][nk]+=dp[i][j][k]

  # print(dp[2][9][1])
  # print(dp[3][9][1])
  # print(dp[4][9][1])

  ans=0
  for j in range(2501):
    for k in range(1,51):
      if j%k!=0:
        continue
      if j//k==a and dp[n][j][k]>0:
        ans+=dp[n][j][k]

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
from copy import deepcopy

def getval():
    n,a = map(int,input().split())
    x = list(map(int,input().split()))
    return n,a,x

def main(n,a,x):
    #DP: dp[ith card][j cards picked][sum k]
    dp = [[[0 for k in range(2500+1)] for j in range(n+1)]]
    dp[0][0][0] = 1
    for i in range(n):
        cur = x[i]
        temp = deepcopy(dp[-1])
        for j in range(1,n+1):
            prev = dp[-1][j-1]
            for k in range(1,2500+1):
                if cur<=k:
                    temp[j][k] += prev[k-cur]
        dp.append(temp)
    ans = 0
    for i in range(1,n+1):
        ans += dp[n][i][a*i]
    print(ans)
      
if __name__=="__main__":
    n,a,x = getval()
    main(n,a,x)

Submission status: Accepted

Solution code:
# 作れる数の最大は50 * 50 = 2500
# dp[i][j] = i枚使ってjを作れる場合の数

import sys
readline = sys.stdin.readline

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

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

for x in X:
  for i in range(len(dp) - 2, -1, -1):
    for j in range(len(dp[i]) - 1, -1, -1):
      if dp[i][j] == 0:
        continue
      dp[i + 1][j + x] += dp[i][j]
      
ans = 0
for i in range(1, len(dp)):
  for j in range(len(dp[i])):
    if j == i * A:
      ans += dp[i][j]
      
print(ans)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(lambda x:int(x)-A, input().split()))
dp = [0]*10000
dp[0] = 1
for i in range(N):
  new_dp = dp[:]
  for j in range(-3000,3000):
    if dp[j]>0:
      new_dp[j+X[i]] += dp[j]
  dp = new_dp
print(dp[0]-1)

Submission status: Accepted

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

ans = 0

dp = [[[0 for _ in range(N*A + 1)] for _ in range(N+1)] for _ in range(N+1)] # dp[i][num][j] : iこ目までみてnum個選んでjをつくる方法
dp[0][0][0] = 1
for i in range(1, N+1):
    for num in range(i+1):
        for j in range(N * A+1):
            dp[i][num][j] += dp[i-1][num][j]
            if j >= x[i]:
                dp[i][num][j] += dp[i-1][num-1][j-x[i]]

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

print(ans)

Submission status: Accepted

Solution code:
MAX=2500
n,a=map(int,input().split())
x=list(map(int,input().split()))
# dp[i][j][k] := x[0:i]のカードからj枚とって合計がkとなる取り方の数
dp = [[[0] * (MAX+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(0,n+1):
    for k in range(0, MAX+1):
      dp[i+1][j][k] += dp[i][j][k] # i番目のカードを取らない
  for j in range(1,n+1):
    for k in range(x[i], MAX+1):
      dp[i+1][j][k] += dp[i][j-1][k-x[i]] # i番目のカードを取る

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

Submission status: Accepted

Solution code:
import sys
import copy

readline = sys.stdin.buffer.readline


def main():
    N, A = map(int, readline().split())
    X = list(map(int, readline().split()))
    X = [x - A for x in X]

    dp = [0] * 5050
    dp[2525] = 1

    for i in range(N):

        next_dp = copy.copy(dp)
        for t in range(5050):
            if X[i] + t < 5050:
                next_dp[X[i] + t] += dp[t]

        dp = next_dp

    print(dp[2525] - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N, A = in_nn()
    X = in_nl()
    X = [x - A for x in X]

    dp = [0] * 5050
    dp[2525] = 1

    for i in range(N):

        next_dp = copy.copy(dp)
        for t in range(5050):
            if X[i] + t < 5050:
                next_dp[X[i] + t] += dp[t]

        dp = next_dp

    print(dp[2525] - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A, X):
    # dp[i][j][k] = i番目のカードまで見て、k枚使って合計がjになる組み合わせの数
    dp = [[[0] * (N + 1) for __ in range(A * N + 5)] for _ in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(1, N + 1):
        x = X[i - 1]
        for j in range(A * N + 1):
            for k in range(i + 1):
                dp[i][j][k] += dp[i - 1][j][k]
                if j >= x and k >= 1:
                    dp[i][j][k] += dp[i - 1][j - x][k - 1]

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

if __name__ == '__main__':
    input = sys.stdin.readline
    N, A = map(int, input().split())
    *X, = map(int, input().split())
    main(N, A, X)

Submission status: Accepted

Solution code:
n , a = map(int,input().split())
x = list(map(lambda x:int(x)-a,input().split()))
dp = [0 for i in range(4901)]
for i in x:
    if i < 0:
        for j in range(4901):
            if 0<=i+j<=4900:
                dp[j+i] += dp[j]
    elif i >= 0:
        for j in reversed(range(4901)):
            if 0<=i+j<=4900:
                dp[j+i] += dp[j]
    dp[i+2450] += 1
print(dp[2450])

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def search(arr):
    ret = [0] * 3000
    ret[0] = 1
    for num in arr:
        tmp = copy.copy(ret)
        for i in range(2700):
            tmp[i + num] += ret[i]
        ret = tmp
    return ret

def solve():
    n, k = getList()
    nums = getList()
    pos = []
    neg = []
    zero = 0
    for num in nums:
        if num == k:
            zero += 1
        if num < k:
            neg.append(k - num)
        if num > k:
            pos.append(num - k)

    posarr = search(pos)
    negarr = search(neg)

    ans = 0
    for i in range(2800):
        ans += posarr[i] * negarr[i]
    # print(posarr)
    # print(negarr)
    print(ans * pow(2, zero) - 1)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
import bisect

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

B=max(max(x),abs(min(x)))

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

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

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(lambda x: int(x)-A, input().split()))
X_MAX = max(max(X), -min(X))
NX = N * X_MAX
dp = [[0] * (X_MAX * (N+1) * 2 + 1)  for i in range(N+1)]
dp [0][NX] = 1
for i in range(1, N+1):
    for j in range(NX*2+1):
        dp[i][j] += dp[i-1][j]
        dp[i][j] += dp[i-1][j-X[i-1]]

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

Submission status: Accepted

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

print(sum(dp[NX][N]) - 1)

Submission status: Accepted

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

d = {}
d[0] = 1

for x in X:
    for k, v in tuple(d.items()):
        d[k+x] = d.get(k+x, 0) + v

print(d[0]-1)

Submission status: Accepted

Solution code:
OFS = 2500
MAX = 2*OFS + 1
N, A = map(int, input().split())
X = [x-A for x in map(int, input().split())]

dp = [[0]*MAX for _ in [0]*(N+1)]
dp[0][OFS] = 1

for i in range(1, N+1):
    x = X[i-1]
    for j in range(MAX-1, -1, -1):
        if 0 <= j-x < MAX:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-x]

print(dp[-1][OFS] - 1)

Submission status: Accepted

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

dp = [[0] * 5000 for _ in range(n+1)]
zero = 2500
dp[0][zero] = 1
for i in range(n):
    for j in range(5000):
        dp[i+1][j] += dp[i][j]
        if j + y[i] < 5000:
            dp[i+1][j+y[i]] += dp[i][j]

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

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
dp = [[0]*(A*N+2) for _ in range(N+2)]
dp[0][0] = 1
for i, x in enumerate(X,start=1):
    for n in reversed(range(i)):
        for k in range(A*N+1):
            if dp[n][k] == 0: continue
            dp[n+1][min(k+x,A*N+1)] += dp[n][k]
print(sum(dp[n][A*n] for n in range(1,N+1)))

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n, a = ns()
    x = na()
    l = 2500

    dp = [[0 for _ in range(l + 1)] for __ in range(n + 1)]
    dp[0][0] = 1

    for xi in x:
        for i in range(n - 1, -1, -1):
            for li in range(l):
                tmp = li + xi
                if dp[i][li] != 0 and tmp <= l:
                    dp[i + 1][tmp] += dp[i][li]
    ans = 0
    for i, dpi in enumerate(dp):
        if i == 0:
            continue
        ans += dpi[a * i]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,h=map(int,input().split())
A=list(map(int,input().split()))

A= [i-h for i in A]
dp=[[0]*5100 for i in range(n+1)]
dp[0][2500]=1

for i in range(n):
    for j in range(5100):
        if not dp[i][j]: continue
        dp[i+1][j] += dp[i][j]
        #if A[i]==0:continue
        dp[i+1][j+A[i]] +=dp[i][j]

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

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,a = map(int,ipt().split())
    x = [int(i) for i in ipt().split()]

    dpp = [0]*2501
    dpm = [0]*2501
    zeros = 0
    dpp[0] = 1
    dpm[0] = 1
    for i in x:
        if a > i:
            d = a-i
            for j in range(2500,d-1,-1):
                dpp[j] += dpp[j-d]
        elif a < i:
            d = i-a
            for j in range(2500,d-1,-1):
                dpm[j] += dpm[j-d]
        else:
            zeros += 1
    ans = 0
    for i in range(2501):
        ans += dpp[i]*dpm[i]
    ans *= 2**zeros
    print(ans-1)
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))

for i in range(N):  a[i] -= K
dp = [[0 for _ in range(5500)] for _ in range(N + 5)]
dp[0][2500] = 1
for i in range(N):
    for j in range(5010):
        if j - a[i] >= 0 :  dp[i + 1][j] += dp[i][j - a[i]]
        dp[i + 1][j] += dp[i][j] 
        
ans = dp[N][2500] - 1
print(ans)

Submission status: Accepted

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

dp = [0] * 5010
dp[2500] = 1

for y in Y:
    r = []
    if y >= 0:
        r = range(5009, -1, -1)
    else:
        r = range(5010)
    for i in r:
        if i - y < 0 or i - y >= 5010:
            continue
        dp[i] += dp[i - y]
print(dp[2500] - 1)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

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

dp[0][0] = 1
for i in range(N):
    x = X[i]
    for j in range(i, -1, -1):
        for k in range(2501):
            if k < x:
                continue
            dp[j + 1][k] += dp[j][k - x]
ans = 0
for i in range(1, 51):
    ans += dp[i][i * A]
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, A = mapint()
Xs = list(mapint())
Xs.sort()
dp = [[[0]*2501 for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

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

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

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

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

dp = [[defaultdict(lambda: 0) for j in range(50*N+1)] for i in range(N+1)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(50*N+1):
        for k, v in dp[i][j].items():
            dp[i+1][j][k] += v
        if j >= X[i]:
            for k, v in dp[i][j-X[i]].items():
                dp[i+1][j][k+1] += v

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

print(ans)

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
dic={}
dic2=dic.copy()
for i in range(n):
  for j in dic:
    if j+x[i]-a in dic2:
      dic2[j+x[i]-a]+=dic[j]
    else:
      dic2[j+x[i]-a]=dic[j]
  if x[i]-a in dic2:
    dic2[x[i]-a]+=1
  else:
    dic2[x[i]-a]=1
  dic=dic2.copy()
if 0 in dic:
  print(dic[0])
else:
  print(0)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n,a = lr()
x = lr()
sub = [x[i]-a for i in range(n)]
dp = [[0 for i in range(5001)] for j in range(n+1)] # 合計がi-2500となる数
# dp[0][2500] = 1 # 0となる数
for j,num in enumerate(sub):
    for i in range(5001):
        dp[j+1][i] = dp[j][i]
    dp[j+1][num+2500] += 1
    for i in range(5001):
        if dp[j][i] >= 1:
            dp[j+1][i+num] += dp[j][i]
print(dp[n][2500])

Submission status: Accepted

Solution code:
def solve():
  ans = 0
  N, A = map(int, input().split())
  X = list(map(int, input().split()))
  x = sum(X)
  dp = [[[0]*2550 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 k in range(x):
        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[-1][j][j*A]
  return ans
print(solve())

Submission status: Accepted

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

from collections import defaultdict
dp = [defaultdict(lambda: 0) for _ in range(N+1)]
dp[0][0] = 1
for i,x in enumerate(X):
    for j in range(i,-1,-1):
        for k,v in dp[j].items():
            dp[j+1][k+x] += v

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

Submission status: Accepted

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

memo = [[[0]*(A*N+1) for _ in range(N+1)] for _ in range(N+1)]

memo[0][0][0] = 1

for i in range(1,N+1):
  for j in range(N+1):
    for k in range(A*N+1):
      if k - Xs[i] >= 0:
        memo[i][j][k] = memo[i-1][j-1][k-Xs[i]] + memo[i-1][j][k]
      else:
        memo[i][j][k] = memo[i-1][j][k]
        
rlt = 0
for i in range(1,N+1):
  rlt += memo[N][i][i*A]
  
print(rlt)

Submission status: Accepted

Solution code:
n,a=list(map(int,input().split()))
x=list(map(lambda x:int(x)-a,input().split()))
d={0:1}
for i in range(n):
  nd={}
  for j in d:
    if j in nd:
      nd[j]+=d[j]
    else:
      nd[j]=d[j]
    if (j+x[i]) in nd:
      nd[j+x[i]]+=d[j]
    else:
      nd[j+x[i]]=d[j]
  d=nd
print(d[0]-1)

Submission status: Accepted

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

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

    for i in range(N):
        for j in range(5000):
            if dp[i][j] == 0 or j+x[i] >= 5000:
                continue
            dp[i+1][j+x[i]] += dp[i][j]
            dp[i+1][j] += dp[i][j]
    
    print(dp[N][GETA]-1)
        
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import collections
N, A = [int(_) for _ in input().split()]
X = [int(_) for _ in input().split()]
Y = X[:N // 2]
Z = X[N // 2:]


def calc(W):
    #dp[m][s]=m枚のカードの和がsとなるような選び方の総数
    M = len(W)
    dp = [collections.defaultdict(int) for _ in range(M + 1)]
    dp[0][0] = 1
    for i, w in enumerate(W):
        for j in range(i, -1, -1):
            for k, v in dp[j].items():
                dp[j + 1][k + w] += v
    return dp


dpy = calc(Y)
dpz = calc(Z)
ans = 0
for n in range(1, N + 1):
    B = A * n
    for l in range(n + 1):
        r = n - l
        if l >= len(dpy) or r >= len(dpz):
            continue
        for k, v in dpy[l].items():
            ans += v * dpz[r][B - k]
print(ans)