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:
def main():
    N, A = map(int, input().split())
    X = list(map(int, input().split()))

    dp = [[0] * (A * N + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i, x in enumerate(X):
        for j in reversed(range(1, i + 2)):
            for a in range(x, A * N + 1):
                dp[j][a] += dp[j - 1][a - x]
    return sum(dp[i][A * i] for i in range(1, N + 1))

print(main())

Submission status: Accepted

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

Submission status: Accepted

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

s = sum(x)
dp = np.zeros((n, s+1), dtype = np.int64)
for i in range(n):
  for j in range(i)[::-1]:
    dp[j+1][x[i]:] += dp[j][:-x[i]]
  dp[0][x[i]] += 1
ans = 0
for i in range(n):
  if (i+1)*a <= s:
    ans += dp[i][(i+1)*a]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,a = map(int,input().split())
x = list(map(int,input().split()))
"""
平均がa <=> 集合をlとして, len(l)a = sum(l)
dp[i][j][k] := i番目までのカードを選んだとき, 選んだ枚数がkでの総和がちょうどjになる場合の数.
これだとメモリが足りないので, iを省略する.
"""
sumx = sum(x)
dp = np.zeros((n, sumx+1), dtype=np.int64)
for i in range(n):
	for j in range(i)[::-1]:
		dp[j+1][x[i]:] += dp[j][:-x[i]]
	dp[0][x[i]] += 1
ans = 0
for i in range(n):
	if (i+1)*a <= sumx:
		ans += dp[i][(i+1)*a]
print(ans)

Submission status: Accepted

Solution code:


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[i][j][k] - sum is i, j number of elements, first k elements
    OPT[i][j][k] = OPT[i-x[k]][j-1][k-1] if j-th element is taken
                   OPT[i][j][k-1]

    OPT[A*j][j][k] for all k
    """
    N, A = read_ints()
    x = read_ints()
    OPT = [[[0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N*max(x)+1)]
    for k in range(N+1):
        OPT[0][0][k] = 1
    for i in range(len(OPT)):
        for j in range(1, N+1):
            for k in range(j, N+1):
                if i-x[k-1] >= 0:
                    OPT[i][j][k] += OPT[i-x[k-1]][j-1][k-1]
                OPT[i][j][k] += OPT[i][j][k-1]
    T = 0
    for j in range(1, N+1):
        if A*j < len(OPT):
            T += OPT[A*j][j][N]
    return T


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[i][j][k] - sum is i, j number of elements, first k elements
    OPT[i][j][k] = OPT[i-x[k]][j-1][k-1] if j-th element is taken
                   OPT[i][j][k-1]

    OPT[A*j][j][k] for all k
    """
    N, A = read_ints()
    x = read_ints()
    OPT = [[[0 for _ in range(51)] for _ in range(51)] for _ in range(2501)]
    for k in range(N+1):
        OPT[0][0][k] = 1
    for i in range(len(OPT)):
        for j in range(1, N+1):
            for k in range(1, N+1):
                if i-x[k-1] >= 0:
                    OPT[i][j][k] += OPT[i-x[k-1]][j-1][k-1]
                OPT[i][j][k] += OPT[i][j][k-1]
    T = 0
    for j in range(1, N+1):
        T += OPT[A*j][j][N]
    return T


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
from numba import njit

@njit("i8(i8[:,:,:],i8[:],i8,i8,i8)",cache=True)
def f(dp,x,con,n,a):
    for i in range(n):
        for k in range(n):
            for j in range(con+1-50):
                #i枚目を選ぶ
                dp[i+1][j+x[i]][k+1]+=dp[i][j][k]

                #i枚目を選ばない
                dp[i+1][j][k]+=dp[i][j][k]
    ans=0
    for k in range(1,n+1):
        ans+=dp[n][k*a][k]

    return ans

def main():
    #入力
    readline=stdin.readline
    con=2500
    n,a=map(int,readline().split())
    x=list(map(int,readline().split()))
    x=np.array(x,dtype=np.int64)

    dp=[[[0]*(n+1) for _ in range(con+1)] for _ in range(n+1)]
    dp[0][0][0]=1
    dp=np.array(dp,dtype=np.int64)

    print(f(dp,x,con,n,a))

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    con=2500
    n,a=map(int,readline().split())
    x=list(map(int,readline().split()))

    dp=[[[0]*(n+1) for _ in range(con+1)] for _ in range(n+1)]
    dp[0][0][0]=1
    for i in range(n):
        for k in range(n):
            for j in range(con+1-50):
                #i枚目を選ぶ
                dp[i+1][j+x[i]][k+1]+=dp[i][j][k]

                #i枚目を選ばない
                dp[i+1][j][k]+=dp[i][j][k]

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

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n, a = LI()
	x_list = np.array(LI())
	nx = n*max(x_list+[a])
	y_list = x_list - a
	dp = np.full((n+1,2*nx+1),INF)

	def dfs(j,t):
		dp_value = dp[j,t]
		if dp_value == INF:
			if j == 0 and t == nx:
				dp_value = 1
			elif j >= 1 and (y_list[j-1] < t - 2*nx or y_list[j-1] > t):
				dp_value = dfs(j-1, t)
			elif j >= 1 and 0 <= t - y_list[j-1] <= 2*nx:
				dp_value = dfs(j-1, t) + dfs(j-1, t-y_list[j-1])
			else:
				dp_value = 0
			dp[j,t] = dp_value
		return int(dp_value)

	print(dfs(n, nx) -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
import numpy as np
dp=np.zeros((n+1,2501),int)
dp[0,0]=1
for xi in x:
  for i in range(n-1,-1,-1):
    dp[i+1][xi:]+=dp[i,:-xi]
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())
x = list(map(int, input().split()))

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

for i in range(n):
    for use in range(n):
        for total in range(n * a):
            if dp[i][use][total]:
                dp[i + 1][use][total] += dp[i][use][total]
                dp[i + 1][use + 1][total + x[i]] += dp[i][use][total]

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()))
for i in range(n):
    x[i] -= a
dp = [[0 for i in range(2*n*50+1)] for j in range(n+1)]
dp [0][n*50] = 1

for i in range(1,n+1):
    for j in range(2*n*50+1):
        if 0 <= j - x[i-1] < 2*n*50:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-x[i-1]]
        else:
            dp[i][j] = dp[i-1][j]
    #print(dp[i])
print(dp[n][n*50] - 1) #全て選ばないを除く

# 4 8
# 7 9 8 9 のとき
# i = 1 で -1 0 が 1
# i = 2 で -1 1 が 1, 0 が2
# i = 3 で -1 1 が 2, 0 が4
# i = 4 で -1 2 が 2, 0 1 が 6

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
x = [i - a for i in x]
dic = {0:1}
for i in x:
    for j, k in list(dic.items()):
        dic[i+j] = dic.get(i+j, 0) + k

print(dic[0] - 1)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
lst = [int(x) - A for x in input().split()]
dp = [[0] * (100 * N + 1) for _ 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 - lst[i]]
print(dp[N][50 * N] - 1)

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
Y = list(map(lambda x:int(x)-A,input().split()))
dp = {0:1}

for y in Y:
	for k,v in list(dp.items()):
		dp[k+y]=dp.get(k+y,0)+v

print(dp[0]-1)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  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

#####MakeDivisors######
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)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,A = IL()
X = IL()
X = [x-A for x in X]
X.sort()
pl = bisect.bisect_left(X,0)
pr = bisect.bisect_right(X,0)
MINUS = X[:pl]
ZERO = X[pl:pr]
PLUS = X[pr:]

dpM = [[0 for j in range(3000)] for i in range(len(MINUS)+1)]
dpP = [[0 for j in range(3000)] for i in range(len(PLUS)+1)]
dpM[0][0] = 1
dpP[0][0] = 1
for i in range(len(MINUS)):
  x = abs(MINUS[i])
  for j in range(3000):
    if j+x < 3000:
      dpM[i+1][j+x] = dpM[i][j]
    dpM[i+1][j] += dpM[i][j]
      
for i in range(len(PLUS)):
  x = abs(PLUS[i])
  for j in range(3000):
    if j+x < 3000:
      dpP[i+1][j+x] = dpP[i][j]
    dpP[i+1][j] += dpP[i][j]

ans = 0
for i in range(1,3000):
  ans += dpM[-1][i] * dpP[-1][i]

print(ans*pow(2,len(ZERO))+pow(2,len(ZERO))-1)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

    ret={0: 1}
    for xi in X:
        for y, cnt in list(ret.items()):
            ret[xi+y] = ret.get(xi+y, 0) + cnt
    print(ret[0]-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
Y = list(map(lambda x:int(x)-A,input().split()))
dp = {0:1}

for y in Y:
	for k,v in list(dp.items()):
		dp[k+y]=dp.get(k+y,0)+v

print(dp[0]-1)

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
from collections import Counter
X = [int(x) - a for x in input().split()]
d=Counter([0])
for i in X:
    tmp=Counter()
    for j,k in d.items():
        tmp[i+j]+=k
    d+=tmp
print(d[0]-1)

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
X = list(map(int,input().split()))
dp = [[[0 for _ in range(50*(N+2))] for _ in range(N+2)] for _ in range(N+2)]

dp[0][0][0] = 1
#kまでみた
for k in range(N):
    #used個使った
    for used in range(N):
        for i in range(50*N):
            #使う時
            dp[used+1][k+1][i+X[k]] += dp[used][k][i]
            dp[used][k+1][i] += dp[used][k][i]
ans = 0
for used in range(1,N+1):
    ans += dp[used][N][used*A]
print(ans)

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
X = list(map(int,input().split()))
dp = [[[0 for _ in range(50*(N+2))] for _ in range(N+2)] for _ in range(N+2)]

dp[0][0][0] = 1
#kまでみた
for k in range(N):
    #used個使った
    for used in range(N):
        for i in range(50*N):
            #使う時
            if dp[used][k][i] == 0: 
                continue
            dp[used+1][k+1][i+X[k]] += dp[used][k][i]
            dp[used][k+1][i] += dp[used][k][i]
ans = 0
for used in range(1,N+1):
    ans += dp[used][N][used*A]
print(ans)

Submission status: Accepted

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

slist=[0]
for x in xlist:
  slist.append(slist[-1]+x)
#print(slist)

dp=[[[0]*(sum(xlist)+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0]=1
for i in range(1,N+1):
  dp[i][0][0]=1
  for j in range(1,i+1):
    for k in range(1,slist[i]+1):
      dp[i][j][k]=dp[i-1][j][k]
      if k-xlist[i-1]>=0:
        dp[i][j][k]+=dp[i-1][j-1][k-xlist[i-1]]
#print(dp)

answer=0
for j in range(1,N+1):
  if j*A>sum(xlist):
    break
  answer+=dp[N][j][j*A]
  
print(answer)

Submission status: Accepted

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

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

answer=0
for j in range(1,N+1):
  if j*A>sum(xlist):
    break
  answer+=dp[N][j][j*A]
  
print(answer)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# DP

# https://atcoder.jp/contests/abc044/tasks/arc060_a

from itertools import combinations


n, a = map(int, input().split())
x = list(map(int, input().split()))
X = max(max(x), a)


# dp[j][k][s] (0 <= j <= N, 0 <= k <= N, 0 <= s <= NX)
# dp[j][k][s] = x1,...,xjまでからk枚使って，合計をsにする選び方の総数
# dp[0][0][0] = 1
# j >= 1, s < xjのとき，dp[j][k][s] = dp[j-1][k][s] (xjは使わない)
# j >= 1, k >= 1, s >= xjのとき，dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-xj]
# ... 1枚少なく使ってxjを入れる + 使わない
# それ以外 0

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

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

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
# dp[j][k][s]=(x1,...,xjからk枚選んでx[i]の合計をsにするような選び方の総数)
dp=[[[0]*2501 for i in range(51)] for j in range(51)]
dp[0][0][0]=1
for i in range(n):
    for j in range(n+1):
        for k in range(2501):
            if k<x[i]:
                dp[i+1][j][k]=dp[i][j][k]
            else:
                dp[i+1][j][k]=dp[i][j][k]+dp[i][j-1][k-x[i]]
ans=0
for i in range(1,n+1):
    ans+=dp[n][i][i*a]
print(ans)

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
for i in range(n):
    x[i]-=a
# dp[i][j] = i番目までで(j-2500)を何個作れるか
dp=[[0]*5001 for i in range(n+1)]
dp[0][2500]=1
for i in range(n):
    for j in range(5000):
        for k in range(2):
            if 0<=j-k*x[i]<=5000:
                dp[i+1][j]+=dp[i][j-k*x[i]]
print(dp[n][2500]-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
# dp[i][j] = i番目までで(j-2500)を何個作れるか
dp=[[0]*5001 for i in range(n)]
dp[0][x[0]+2500]=1
for i in range(1,n):
    dp[i][x[i]+2500]=1
    for j in range(5000):
        for k in range(2):
            if 0<=j-k*x[i]<=5000:
                dp[i][j]+=dp[i-1][j-k*x[i]]
print(dp[n-1][2500])

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
max_x = max(max(x), a)
dp = [[[0] * (n * max_x + 1) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n * max_x + 1):
            if i >= 1 and k < x[i - 1]:
                dp[i][j][k] = dp[i - 1][j][k]
            elif i >= 1 and j >= 1 and k >= x[i - 1]:
                dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - x[i - 1]]
            else:
                continue
ans = 0
for j in range(1, n + 1):
    ans += dp[n][j][j * a]
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

n, a = imap()
x = np.array(iarr()) - a
MAX = 50*50+1

dp = np.zeros((n+1, 2*MAX+1)).astype(int)
dp[0][MAX] = 1
for i in range(n):
    for j in range(2*MAX):
        if j-x[i] < 0 or j-x[i] > 2*MAX:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = dp[i][j] + dp[i][j-x[i]]
print(dp[n][MAX]-1)

Submission status: Accepted

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

# dp[i][j] : i枚目まで見て合計がj-2500のもの
dp = [[0]*5001 for _ in range(N+1)]
dp[0][y[0]+2500] = 1
dp[0][2500] += 1
for i in range(N-1):
    new = y[i+1]
    for j in range(5001):
        dp[i+1][j] += dp[i][j]
        if 0 <= j+new <= 5000:
            dp[i+1][j+new] += dp[i][j]
print(dp[N-1][2500]-1)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

n,a = imap()
x = np.array(iarr()) - a

# dp[i][和 + NA]
# 本来のSの範囲は、1N-NAから50N-NA
# 負の数はdp範囲外なのでNAたすと、1Nから50N
# 和０のときは dp[n][0+NA]
dp = np.zeros((n+1, 50*n+1)).astype(int)
dp[0][n*a] = 1

for i in range(n):
    for s in range(50*n+1):
        dp[i+1][s] = dp[i][s] + dp[i][s-x[i]] if 50*n>= s-x[i] >=0 else dp[i][s]

ans = dp[n][n*a] - 1 #実際は初期条件の０個選ぶパターンを除外
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

n,a = imap()
x = np.array(iarr()) - a

# dp[i][和 + NA]
# 本来のSの範囲は、1N-NAから50N-NA
# 負の数はdp範囲外なのでNAたすと、1Nから50N
# 和０のときは dp[n][0+NA]
dp = np.zeros((n+1, 50*n+100)).astype(int)
dp[0][n*a] = 1

for i in range(n):
    for s in range(50*n+1):
        dp[i+1][s] = dp[i][s] + dp[i][s-x[i]] if s-x[i]>=0 else dp[i][s]

ans = dp[n][n*a] - 1 #実際は初期条件の０個選ぶパターンを除外
print(ans)

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)
dp = [[[0]*(x_max*n+1) for k in range(n+1)] for i in range(n+1)]
ans = 0
dp[0][0][0] = 1
for i in range(n):
    for j in range(i+2):
        for k in range(x_max*n+1):
            if k>= x[i]:
                dp[i+1][j][k] = dp[i][j-1][k-x[i]] + dp[i][j][k]
            else:
                dp[i+1][j][k] = dp[i][j][k]
            
for k in range(x_max*n+1):
    for j in range(1,n+1):
        if a*j == k:
            ans += dp[n][j][k]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,avea=tuple(map(lambda x:int(x),input().split()))
x=list(map(lambda x:int(x), input().split()))
x=np.array(x)
x=x-avea
w=max(abs(min(x)),abs(max(x)))*n
dp=np.zeros((n+1,2*w+1),dtype=int)
dp[0,w]=1
for i in range(1,n+1):
    for j in range(2*w+1):
        if 0<=j-x[i-1]<=2*w:
            dp[i,j]=dp[i-1,j]+dp[i-1,j-x[i-1]]
        else:
            dp[i,j]=dp[i-1,j]
print(dp[n,w]-1)

Submission status: Accepted

Solution code:
import numpy as np
n,avea=tuple(map(lambda x:int(x),input().split()))
x=list(map(lambda x:int(x), input().split()))
x=np.array(x)
x=x-avea
w=max(abs(min(x)),abs(max(x)))*n
dp=np.zeros((n+1,2*w+1),dtype=int)
dp[0,w]=1
for i in range(n):
    for j in range(2*w+1):
        if 0<=j-x[i]<=2*w:
            dp[i+1,j]=dp[i,j]+dp[i,j-x[i]]
        else:
            dp[i+1,j]=dp[i,j]
print(dp[n,w]-1)

Submission status: Accepted

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

dp = [[[0] * n for i in range(n * a + 1)] for i in range(n)]
for i in range(n):
    for j in range(n * a + 1):
        for k in range(n):
            if i == 0 and x[0] < n * a + 1:
                dp[0][x[0]][0] = 1
                break
            else:
                if j == 0:
                    if k == 0 and x[i] < n * a + 1:
                        dp[i][x[i]][0] += 1
                    continue

                if dp[i - 1][j][k] == 0:continue
                dp[i][j][k] += dp[i - 1][j][k]
                if not(0 <= j + x[i] < n * a + 1):continue
                dp[i][j + x[i]][k + 1] += dp[i - 1][j][k]
cnt = 0
for i in range(n * a + 1):
    if i != 0 and i % a == 0:
        temp = i // a
        cnt += dp[-1][i][temp - 1]
print(cnt)

Submission status: Accepted

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

import sys
# import math
# from string import ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, a = mi()
    L = lmi()
    diff = [elm - a for elm in L]
    # dp[i][num] = (diff から i 番目までを使用して和を num - 2500 にする場合の数)
    dp = [[0] * 5001 for _ in range(n + 1)]
    dp[0][2500] = 1

    for i in range(n):
        for j in range(5001):
            if dp[i][j]:
                dp[i+1][j + diff[i]] += dp[i][j]
            dp[i+1][j] += dp[i][j]
    

    print(dp[n][2500] - 1)    # n 番目までを使用して和を 0 にするには？ 最初の何も選ばない 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] -= a

d = [0] * 6000
ans = 0
for dif in x:
  ans += d[-dif+3000]
  if dif == 0:
    ans += 1
  if dif < 0:
    for i in range(6000):
      if 0 <= i+dif < 6000:
        d[i+dif] += d[i]
  else:
    for i in range(5999, -1, -1):
      if 0 <= i+dif < 6000:
        d[i+dif] += d[i]
  d[dif+3000] = d[dif+3000] + 1
  
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

dp[0][n*50]=1

for i in range(n):
    for j in range(n*50*2):
        t=j-x[i]
        if 0<=t<n*50*2:
            dp[i+1][j]=dp[i][j]+dp[i][t]
        else:
            dp[i+1][j]=dp[i][j]
print(dp[n][n*50]-1)