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: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

from collections import defaultdict
from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)


def _main():
    N, A = get_ints()
    xn = get_array()

    xn.sort()

    xna = [i - A for i in xn]
    xnn = [i for i in xna if i < 0]
    xnp = [i for i in xna if i > 0]
    xn0 = [i for i in xna if i == 0]

    xn0_p = 0
    for i in range(len(xn0)):
        xn0_p += combinations_count(len(xn0), i)

    n = defaultdict(list)
    p = defaultdict(list)

    xnn = list(map(abs, xnn))

    for j in range(1, sum(xnn) + 1):
        gen = subset_sum(xnn, j)
        try:
            while 1:
                nl = gen.__next__()
                n[j].append(nl)
        except StopIteration:
            pass

    for k in n.keys():
        gen = subset_sum(xnp, k)
        try:
            while 1:
                pl = gen.__next__()
                p[k].append(pl)
        except StopIteration:
            pass

    ss = set(n.keys()) & set(p.keys())
    xn_p = 0
    for s in ss:
        xn_p += len(n[s]) * len(p[s])

    if xnn and xnp:
        print(f"{(xn0_p+1) * (xn_p+1) - 1=}")
    else:
        print(f"{xn0_p=}")


if __name__ == "__main__":
    _main()

Submission status: Runtime Error

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

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

maxint = 50 * max(x)

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

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

for xi, xe in enumerate(x, 1):
    for j in range(xi+1):
        for k in range(maxint + 1):
            dp[xi][j][k] = dp[xi - 1][j][k]
            
            if j >= 0 and k >= xe:
                dp[xi][j][k] += dp[xi - 1][j - 1][k - xe]
                

res = 0

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

print(res)

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, A, *X = map(int, read().split())

    M = sum(X)
    dp = [[0] * (M + 1) for j in range(N + 1)]
    dp[0][0] = 1

    for i in range(N):
        for j in range(N, 0, -1):
            for k in range(X[i], M + 1):
                dp[j][k] += dp[j - 1][k - X[i]]

    ans = 0
    for j in range(1, min(50, M // A) + 1):
        ans += dp[j][A * j]

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, A, *X = map(int, read().split())

    M = sum(X)
    dp = [[0] * (M + 1) for j in range(N + 1)]
    dp[0][0] = 1

    for i in range(N):
        for j in range(N, 0, -1):
            for k in range(X[i], M + 1):
                dp[j][k] += dp[j - 1][k - X[i]]

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, A, *X = map(int, read().split())

    M = sum(X)
    dp = [[0] * (M + 1) for j in range(N + 1)]
    dp[0][0] = 1

    for i in range(N):
        for j in range(N, 0, -1):
            for k in range(X[i], M + 1):
                dp[j][k] += dp[j - 1][k - X[i]]

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

n,a=map(int,input().split())
cards=list(map(int,input().split()))


noz=[x-a for x in cards].count(0)
pl=[x-a for x in cards if x-a>0]
nl=[a-x for x in cards if x-a<0]
sl=[pl,nl][len(nl)<=len(pl)]
ll=[pl,nl][len(pl)<len(nl)]

sl.sort()
ll.sort()

sumfunc = lambda n, l: sum([l[x]*((n>>x)&1) for x in range(len(l))])

ssl=sum(sl)
sll=sum(ll)
sumsl=[0 for _ in range(ssl)]
sumll=[0 for _ in range(sll)]
sumsl[sl[-1]-1]=1
sumll[ll[-1]-1]=1
for i in range(1,2**(len(sl)-1)):
    s=sumfunc(i,sl)
    sumsl[s-1]+=1
    sumsl[s+sl[-1]-1]+=1
for i in range(1,2**(len(ll)-1)):
    s=sumfunc(i,ll)
    sumll[s-1]+=1
    sumll[s+ll[-1]-1]+=1
count=sum([x*y for x,y in zip(sumsl, sumll)])
# count=0
# p=sum([not sumsl[-1]<sumfunc(2**i,ll) for i in range(1,len(ll)+1)])
# q=sum([sumsl[0]>=sumfunc(2**i-1,ll) for i in range(1,len(ll)+1)])
# count=[sumfunc(j,ll) in sumsl for j in range(2**q-1,2**p)].count(True)

print((count+1)*(2**noz)-1)

Submission status: Runtime Error

Solution code:
from collections import deque

n,a=map(int,input().split())
cards=list(map(int,input().split()))


noz=[x-a for x in cards].count(0)
pl=[x-a for x in cards if x-a>0]
nl=[a-x for x in cards if x-a<0]
sl=[pl,nl][len(nl)<=len(pl)]
ll=[pl,nl][len(pl)<len(nl)]

sl.sort()
ll.sort()

sumfunc = lambda n, l: sum([l[x]*((n>>x)&1) for x in range(len(l))])

sumsl=[sumfunc(i,sl) for i in range(1,2**len(sl))]
sumll=[sumfunc(i,ll) for i in range(1,2**len(ll))]

# count=0
# p=sum([not sumsl[-1]<sumfunc(2**i,ll) for i in range(1,len(ll)+1)])
# q=sum([sumsl[0]>=sumfunc(2**i-1,ll) for i in range(1,len(ll)+1)])
# count=[sumfunc(j,ll) in sumsl for j in range(2**q-1,2**p)].count(True)
count=0
count=sum([x==y for x in sumsl for y in sumlll])

print((count+1)*(2**noz)-1)

Submission status: Runtime Error

Solution code:
from collections import deque

n,a=map(int,input().split())
cards=list(map(int,input().split()))


noz=[x-a for x in cards].count(0)
pl=[x-a for x in cards if x-a>0]
nl=[a-x for x in cards if x-a<0]
sl=[pl,nl][len(nl)<=len(pl)]
ll=[pl,nl][len(pl)<len(nl)]

sl.sort()
ll.sort()

sumfunc = lambda n, l: sum([l[x]*((n>>x)&1) for x in range(len(l))])

sumsl=[sumfunc(i,sl) for i in range(1,2**len(sl))]

count=0
p=sum([not sumsl[-1]<sumfunc(2**i,ll) for i in range(1,len(ll)+1)])
q=sum([sumsl[0]>=sumfunc(2**i-1,ll) for i in range(1,len(ll)+1)])

count=[sumfunc(j,ll) in sumsl for j in range(2**q-1,2**p)].count(True)

print((count+1)*(2**noz)-1)

Submission status: Runtime Error

Solution code:
from collections import deque

n,a=map(int,input().split())
cards=list(map(int,input().split()))


noz=[x-a for x in cards].count(0)
pl=[x-a for x in cards if x-a>0]
nl=[a-x for x in cards if x-a<0]
sl=[pl,nl][len(nl)<=len(pl)]
ll=[pl,nl][len(pl)<len(nl)]

sl.sort()
ll.sort()

nsl=len(sl)
nll=len(ll)

sumsl=[sum([sl[x]*((i>>x)&1) for x in range(nsl)]) for i in range(1,2**nsl)]
# print(sl,ll,sumsl)
count=0
for i in range(1,nll+1):
    if sumsl[-1]< sum([ll[x]*(((2**i)>>x)&1) for x in range(nll)]):
        continue

count=[sum([ll[x]*((j>>x)&1) for x in range(nll)]) in sumsl for j in range(1,2**i)].count(True)

print((count+1)*(2**noz)-1)

Submission status: Runtime Error

Solution code:
from collections import deque

n,a=map(int,input().split())
cards=list(map(int,input().split()))


noz=[x-a for x in cards].count(0)
pl=[x-a for x in cards if x-a>0]
nl=[a-x for x in cards if x-a<0]
sl=[pl,nl][len(nl)<=len(pl)]
ll=[pl,nl][len(pl)<len(nl)]

sl.sort()
ll.sort()

nsl=len(sl)
nll=len(ll)

sumsl=[sum([sl[x]*((i>>x)&1) for x in range(nsl)]) for i in range(1,2**nsl)]
# print(sl,ll,sumsl)
count=0
for i in range(1,nll+1):
    if sumsl[-1]< sum([ll[x]*(((2**i)>>x)&1) for x in range(nll)]):
        continue

for j in range(1,2**i):
    s=sum([ll[x]*((j>>x)&1) for x in range(nll)])
    count+=(s in sumsl)

print((count+1)*(2**noz)-1)

Submission status: Runtime Error

Solution code:
from collections import deque

n,a=map(int,input().split())
cards=list(map(int,input().split()))

def is2power(n):
    if n==1:
        return True 
    if n%1==1:
        return False
    else:
        is2power(n//2)

noz=[x-a for x in cards].count(0)
pl=[x-a for x in cards if x-a>0]
nl=[a-x for x in cards if x-a<0]
sl=[pl,nl][len(nl)<=len(pl)]
ll=[pl,nl][len(pl)<len(nl)]

sl.sort()
ll.sort()

nsl=len(sl)
nll=len(ll)

sumsl=[sum([sl[x]*((i>>x)&1) for x in range(nsl)]) for i in range(1,2**nsl)]

count=0
for i in range(1,2**nll):
    s=sum([ll[x]*((i>>x)&1) for x in range(nll)])
    if is2power(i) and s>sumsl[-1]:
        continue
    count+=(s in sumsl)

print((count+1)*(2**noz)-1)

Submission status: Runtime Error

Solution code:
from collections import deque

n,a=map(int,input().split())
cards=list(map(int,input().split()))

def is2power(n):
    if n==1:
        return True 
    if n%1==1:
        return False
    else:
        is2power(n//2)

noz=[x-a for x in cards].count(0)
pl=[x-a for x in cards if x-a>0]
nl=[a-x for x in cards if x-a<0]
sl=[pl,nl][len(nl)<=len(pl)]
ll=[pl,nl][len(pl)<len(nl)]

sl.sort()
ll.sort()

nsl=len(sl)
nll=len(ll)

sumsl=[]
for i in range(1,2**nsl):
    sumsl.append(sum([sl[x]*((i>>x)&1) for x in range(nsl)]))

count=0
for i in range(1,2**nll):
    s=sum([ll[x]*((i>>x)&1) for x in range(nll)])
    if is2power(i) and s>sumsl[-1]:
        continue
    count+=(s in sumsl)

print((count+1)*(2**noz)-1)

Submission status: Runtime Error

Solution code:
n, a = map(int, input().split())
X = tuple(map(int, input().split()))
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):
    # i枚目までで
    for j in range(n):
        # j枚のカードを選んで
        for s in range(n*max(X)+1):
            # 合計がsになるパターン
            if dp[i][j][s] == 0:
                continue
            # i枚目のカードが選ばれない場合
            dp[i+1][j][s] += dp[i][j][s]
            # i枚目のカードが選ばれる場合
            dp[i+1][j+1][s+X[i]] += dp[i][j][s]
ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]
print(ans)

Submission status: Runtime Error

Solution code:
#ABC044C
#重要
N,A=map(int,input().split())
a=list(map(int,input().split()))



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



for i in range(len(a)):
    for j in range(len(a)):
        for k in range(N*A):
            if k>=a[i]: 
                dp[i+1][j+1][k]+=dp[i][j][k-a[i]]

            else: 
                dp[i+1][j][k]+=dp[i][j][k]

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

Submission status: Runtime Error

Solution code:
#ABC044C
#重要
N,A=map(int,input().split())
a=list(map(int,input().split()))



dp=[]
dp=[[[0 for i in range(111)] for j in range(111)]for k in range(N*A)]
dp[0][0][0]=1



for i in range(N):
    for j in range(len(a)):
        for k in range(N*A):
            if k>=a[i]: #i+1番目の数字a[i]を足せるかも
                dp[i+1][j+1][k]+=dp[i][j][k-a[i]]

            else: #入る可能性はない
                dp[i+1][j][k]+=dp[i][j][k]

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

Submission status: Runtime Error

Solution code:
N,A=list(map(int,input().split()))
x = list(map(int,input().split()))
dp=[[[0 for _ in range(55)] for _ in range(55)] for _ in range(2555)]
dp[0][0][0]=1
for j in range(N):#x1～xjのカードから
  for k in range(N):#k枚選び
    for s in range(A*N):#xの合計をsになるようにしたい
      if dp[j][k][s] == 0:
        continue
      dp[j+1][k][s] += dp[j][k][s]
      dp[j+1][k+1][s+x[j]] += dp[j][k][s]  

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

Submission status: Runtime Error

Solution code:
N,A=list(map(int,input().split()))
x = list(map(int,input().split()))
dp=[[[0 for _ in range(55)] for _ in range(55)] for _ in range(2555)]
dp[0][0][0]=1
for j in range(N):#x1～xjのカードから
  for k in range(N):#k枚選び
    for s in range(A*N):#xの合計をsになるようにしたい
      dp[j+1][k][s] += dp[j][k][s]
      if s >= x[j]:
        dp[j+1][k+1][s] += dp[j][k][s-x[j]]  

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

Submission status: Runtime Error

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),None)

	def dfs(j,t):
		dp_value = dp[j,t]
		if dp_value == None:
			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: Runtime Error

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

dp = [[[0] * 3000 for _ in range(50)] for _ in range(50)]
dp[0][0][0] = 1

for i in range(n):
    for j in range(n):
        for k in range(n * a):
            dp[i + 1][j][k] += dp[i][j][k]
            dp[i + 1][j + 1][k + x[i]] += dp[i][j][k]

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

print(ans)

Submission status: Runtime Error

Solution code:
N, A = map(int, input().split())
lst = [int(x) - A for x in input().split()]
dp = [[0] * (2 * N + 1) for _ in range(N + 1)]
dp[0][1 * N] = 1
for i in range(N):
    for j in range(1, 2 * N + 1 - 1):
        dp[i + 1][j] = dp[i][j] + dp[i][j - lst[i]]
print(dp[N][1 * N] - 1)

Submission status: Runtime Error

Solution code:
N, A = map(int, input().split())
lst = [int(x) - A for x in input().split()]
dp = [[0] * (2 * N + 1) for _ in range(N + 1)]
dp[0][1 * N] = 1
for i in range(N):
    for j in range(1, 2 * N + 1 - 1):
        dp[i + 1][j] = dp[i][j] + dp[i][j - lst[i]]
print(dp[N][1 * N] - 1)

print(dp)

Submission status: Runtime Error

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


def main():
    N, A = map(int, input().split())
    x = list(map(int, input().split()))
    X = max(x)
    dp = [[[0]*(N*X +1) for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0][0] = 1
    for j in range(1,N+1):
        for k in range(N+1):
            for s in range(N*X+1):
                if s >= x[j-1] and k >= 1:
                    dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
                else:# x[j]を選ぶと合計sにできない
                    dp[j][k][s] = dp[j-1][k][s]
    ans = 0
    for i in range(N):
        ans += dp[N][i+1][(i+1)*A]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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]*2500 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(2500):
            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: Runtime Error

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: Runtime Error

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+3)).astype(int) #50*n+1だめ、なんで！？？？？？？
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: Runtime Error

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の範囲は、n*(1-a)からn*(50-a)
# 負の数はdp半以外なのでNAたすと、1*nから50*N
# 和０のときは 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 s-x[i]>=0 else dp[i][s]

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

Submission status: Runtime Error

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の範囲は、n*(1-a)からn*(50-a)
# 負の数はdp半以外なのでNAたすと、1*nから50*N
# 和０のときは 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(2*n*a+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: Runtime Error

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の範囲は、n*(1-a)からn*(50-a)
# 負の数はdp半以外なのでNAたすと、1*nから50*N
# 和０のときは 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(2*n*a+1):
        print(i,s)
        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: Runtime Error

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
xsum = sum(x)

# dp[i][和 + NA]
# 本来のSの範囲は、n*(1-a)からn*(50-a)
# 負の数はdp半以外なのでNAたすと、1*nから50*N
# 和０のときは 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(2*n*a+1):
        print(i,s)
        dp[i+1][s] = dp[i][s] + dp[i][s-x[i]] if s-x[i]>=0 else dp[i][s]

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

Submission status: Runtime Error

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

# 和は -49*nから49*nまでで、49たせば0 - 98の９９個
# 和０のときは49*nたして、dp[n][0+50*n]が答え
dp = np.zeros((n+1, 100))
dp[0, :] = 1

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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:
                        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: Runtime Error

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:
                dp[0][x[0]][0] = 1
                break
            else:
                if j == 0:
                    if k == 0:
                        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: Runtime Error

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)]
#print(*dp, sep='\n')
for i in range(n):
    for j in range(n * a + 1):
        for k in range(n):
            if i == 0:
                dp[0][x[0]][0] = 1
            else:
                if j == 0 and k == 0:
                    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
                for l in range(n - 1):
                    dp[i][j + x[i]][l + 1] += dp[i - 1][j][l]
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: Runtime Error

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

    def calc_pattern(seq, num):
        '''
        seq の要素を取り出して和を num にする場合の数
        '''
        cnt = 0
        n = len(seq)
        mid = n // 2
        left = seq[:mid]
        left_all = []
        for p in product([True, False], repeat=mid):
            left_all.append(sum([left[i] for i in range(mid) if p[i]]))
        right = seq[mid:]
        right_all = []
        for p in product([True, False], repeat=n-mid):
            right_all.append(sum([right[i] for i in range(n-mid) if p[i]]))
        right_all.sort()
        for i in left_all:
            if i <= num:
                cnt += bisect_right(right_all, num-i) - bisect_left(right_all, num-i)
        # debug
        # if num == 1:
        #     print(f"{seq} {left} {right} {left_all} {right_all}")
        return cnt

    
    n, a = mi()
    L = lmi()
    diff = [elm - a for elm in L]
    diff_neg = list(map(lambda x: - x, filter(lambda x: x < 0, diff)))
    diff_zero = list(filter(lambda x: x == 0, diff))
    diff_pos = list(filter(lambda x: x > 0, diff))


    ans = 0
    # pos, neg から 1 つも選ばない
    ans += pow(2, len(diff_zero)) - 1    # diff_zero の全てを選ばないのは許されぬ
    # pos, neg から 選ぶ ... diff_zero から選ぶものは 2 ^ len(diff_zero) 通り
    if len(diff_pos) != 0 or len(diff_neg) != 0:
        possible_max = min(sum(diff_pos), sum(diff_neg))
        possible_min = max(min(diff_pos), min(diff_neg))
        for i in range(possible_min, possible_max + 1):
            pattern_pos = calc_pattern(diff_pos, i)
            pattern_neg = calc_pattern(diff_neg, i)
            # debug
            # if pattern_pos > 0 and pattern_neg > 0:
            #     print(f"{i} {pattern_pos} {pattern_neg}")
            ans += pattern_pos * pattern_neg * pow(2, len(diff_zero))
    
    print(ans)



if __name__ == "__main__":
    main()