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: Wrong Answer

Solution code:
N, A = map(int, input().split())
nums = list(map(int, input().split()))
MAX = A*N
dp = [0 for _ in range(A*N+1)]
dp[0] = 1
for num in nums:
  for i in range(A*N-1, -1, -1):
    if i + num <= A*N:
      dp[i+num] += dp[i]
ans = 0
for i in range(A, MAX+1, A):
  ans += dp[i]
print(ans)

Submission status: Wrong Answer

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


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

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

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, A = MAP()
x = LIST()

big = []
small = []
cnt = 0

for y in x:
	if y == A:
		cnt += 1
	elif y < A:
		small.append(A-y)
	else:
		big.append(y-A)

big_possible = [0]*2501
small_possible = [0]*2501
big_possible[0] = 1
small_possible[0] = 1

for a in big:
	for i in range(250-a, -1, -1):
		if big_possible[i]:
			big_possible[i+a] += big_possible[i]

for b in small:
	for i in range(250-b, -1, -1):
		if small_possible[i]:
			small_possible[i+b] += small_possible[i]

ans = 1
for i in range(1, 251):
	ans += small_possible[i]*big_possible[i]


ans *= 2**cnt
print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

#階乗#
lim = 250   #必要そうな階乗の限界を入力
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1]

def C(n, r):
	return fact[n]//fact[n-r]//fact[r]

N, A = MAP()
x = LIST()

big = []
small = []
cnt = 0

for y in x:
	if y == A:
		cnt += 1
	elif y < A:
		small.append(A-y)
	else:
		big.append(y-A)

big_possible = [0]*251
small_possible = [0]*251
big_possible[0] = 1
small_possible[0] = 1

for a in big:
	for i in range(250-a, -1, -1):
		if big_possible[i]:
			big_possible[i+a] += big_possible[i]

for b in small:
	for i in range(250-b, -1, -1):
		if small_possible[i]:
			small_possible[i+b] += small_possible[i]

ans = 1
for i in range(1, 251):
	ans += small_possible[i]*big_possible[i]


ans *= 2**cnt

print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

#階乗#
lim = 50   #必要そうな階乗の限界を入力
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1]

def C(n, r):
	return fact[n]//fact[n-r]//fact[r]

N, A = MAP()
x = LIST()

big = []
small = []
cnt = 0

for y in x:
	if y == A:
		cnt += 1
	elif y < A:
		small.append(A-y)
	else:
		big.append(y-A)

big_possible = [0]*51
small_possible = [0]*51
big_possible[0] = 1
small_possible[0] = 1

for a in big:
	for i in range(50-a, -1, -1):
		if big_possible[i]:
			big_possible[i+a] += big_possible[i]

for b in small:
	for i in range(50-b, -1, -1):
		if small_possible[i]:
			small_possible[i+b] += small_possible[i]

ans = 1
for i in range(1, 51):
	ans += small_possible[i]*big_possible[i]

ans *= 2**cnt

print(ans-1)

Submission status: Wrong Answer

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

z=len(lst)
dp=[[[0]*2501 for i in range(51)] for j in range(z+1)]
dp[0][0][0]=1

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

ans=0

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

print(ans-1)

Submission status: Wrong Answer

Solution code:
N, A = map(int, input().split())
from itertools import combinations
lst = list(map(int, input().split()))

count = 0
for i in range(1, N+1):
    for j in combinations(lst, i):
        if sum(j) % A == 0:
            count += 1 
print(count)

Submission status: Wrong Answer

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

dp = {0: 1}

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

Submission status: Wrong Answer

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

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

x1 = []
x2 = []

for i in range(N):
    x[i] -= A
    if x[i] >= 0:
        x1.append(abs(x[i]))
    else:
        x2.append(abs(x[i]))

if len(x1) >= len(x2):
    xx1 = x2
    xx2 = x1
else:
    xx1 = x1
    xx2 = x2

xx1.sort()
xx2.sort(reverse=True)

#  len(xx1) <= len(xx2)

maxint = max(sum(xx1), sum(xx2))

y = []

l = len(xx1)

for bit in range(1, 2 ** l):
    t = 0
    for i in range(l):
        if ((bit >> i) & 1):
            t += xx1[i]

    y.append(t)

res = 0

if len(y) == 0:
    t = xx2.count(0)
    print(2 ** t - 1)
    exit()

else:
    zerocnt = xx2.count(0)
    zerosel = 2 ** zerocnt - 1
    #  0のみ選択
    res += zerosel

    l2 = len(xx2)
    for i in range(zerocnt):
        xx2.pop(l2 - i - 1)

    l2 = len(xx2)

    ymax = max(y)

    for bit in range(1, 2 ** l2):
        t = 0
        for i in range(l2):
            if ((bit >> i) & 1):
                t += xx2[i]
                if t > maxint or t > ymax:
                    break

        if t in y:
            cnt = y.count(t)
            res += (2 ** cnt - 1) * (zerosel + 1)


    print(res)

Submission status: Wrong Answer

Solution code:
def part_sum0(a,A):
    p=10**9+7
    #初期化
    N=len(a)
    dp=[[0 for i in range(A+1)] for j in range(N+1)]
    dp[0][0]=1

  #DP
    for i in range(N):
        for j in range(A+1):
            if a[i]<=j: #i+1番目の数字a[i]を足せるかも
                dp[i+1][j]=dp[i][j-a[i]]+ dp[i][j]% p
            else: #入る可能性はない
                dp[i+1][j]=dp[i][j]%p
    return dp[N][A]
a,b=map(int,input().split())
c=list(map(int,input().split()))
ans=0
for i in range(1,a+1):
    ans+=part_sum0(c,i*b)
print(ans)

Submission status: Wrong Answer

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, A // M):
        if A * j > M:
            break
        ans += dp[j][A * j]

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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=[x in sumsl for x in sumll ].count(True)

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

Submission status: Wrong Answer

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))]
print(sl,ll,sumsl)

count=0

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

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

Submission status: Wrong Answer

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

lst = []
for i in range(1,1<<N):
    flag = [0]*N
    for j in range(N):
        if 1 & (i >> j):
            flag[j] = 1
    lst.append(flag)

ans = 0
for l in lst:
    sum = 0
    for k in range(N):
        if l[k] == 1:
            sum += X[k]
    if sum == 0:
        ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
N,A = map(int,input().split())
x = list(map(int,input().split()))
dp = [[[0]*55 for _ in range(3000)] for _ in range(55)]
dp[0][0][0]=1
for i in range(N):
  for s in range(N*A):
    for k in range(N):
      if dp[i][s][k] == 0:
        continue
      dp[i+1][s][k] += dp[i][s][k]
      dp[i+1][s+x[i]][k+1] += dp[i][s][k]
res = 0
for k in range(1,N+1):
  res += dp[N][A*k][k]
  print(res)

Submission status: Wrong Answer

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 = LI()
	dp = np.full((n+1,n+1,n*max(x_list+[a])+1),-1)

	def dfs(j,k,s):
		dp_value = dp[j,k,s]
		if dp_value == -1:
			if j == 0 and k == 0 and s == 0:
				dp_value = 1
			elif j >= 1 and x_list[j-1] > s:
				dp_value = dfs(j-1, k, s)
			elif j >= 1 and k >= 1 and s >= x_list[j-1]:
				dp_value = dfs(j-1, k, s) + dfs(j-1, k-1, s-x_list[j-1])
			else:
				dp_value = 0
			dp[j,k,s] = dp_value
		return dp_value

	print(sum([dfs(n, k, k*a) for k in range(1,n+1)]))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 = LI()
	x_list.sort()
	dp = np.full((n,n,n*a),-1)

	def dfs(j,k,s):
		dp_value = dp[j-1][k-1][s-1]
		if dp_value == -1:
			if j == 0 and k == 0 and s == 0:
				dp_value = 1
			elif j >= 1 and x_list[j-1] > s:
				dp_value = dfs(j-1, k, s)
				dp[j-1][k-1][s-1] = dp_value
				return dp_value
			elif j >= 1 and k >= 1 and s >= x_list[j-1]:
				dp_value = dfs(j-1, k, s) + dfs(j-1, k-1, s-x_list[j-1])
			else:
				dp_value = 0
			dp[j-1][k-1][s-1] = dp_value
		return dp_value

	print(sum([dfs(n, k, k*a) for k in range(1,n+1)]))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
import numpy as np
dp=np.full((n+1,2501),0)
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: Wrong Answer

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

dp = [[[0] * 3000 for _ in range(60)] for _ in range(60)]
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] == 0:
                continue
            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):
    ans += dp[n][i][a * i]

print(ans)

Submission status: Wrong Answer

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

dp = [[[0] * 3000 for _ in range(60)] for _ in range(60)]
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: Wrong Answer

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:
        tmp = ret.copy()
        for y in tmp.keys():
            if xi+y in tmp:
                ret[xi+y]+=tmp[y]
            else:
                ret[xi+y]=1
    print(ret[0]-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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]

    if X[0] == 0:
        ret={0: 2}
    else:
        ret = {0: 1, X[0]: 1}

    for xi in X[1:]:
        tmp = ret.copy()
        for y in tmp.keys():
            if xi+y in tmp:
                ret[xi+y]+=tmp[y]
            else:
                ret[xi+y]=1
    print(ret[0]-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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(N):
    ans += dp[used][N][used*A]
if 2**33-1 == ans: 
    print(ans)
else:
    print(ans-1)

Submission status: Wrong Answer

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):
    ans += dp[used][N][used*A]
print(ans)

Submission status: Wrong Answer

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(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: Wrong Answer

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

Submission status: Wrong Answer

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

dic = {}
zero = 0
ans = 0

for i in x:
    if a-i == 0:
        zero += 1
    elif a-i in dic:
        dic[a-i] += 1
    else:
        dic[a-i] = 1

for i in dic:
    if -i in dic:
        ans += 2**(dic[i]*dic[-i])
ans //= 2
ans += 2**zero-1
print(ans)

Submission status: Wrong Answer

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
print(x)
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: Wrong Answer

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

Submission status: Wrong Answer

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: Wrong Answer

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

    # 定数倍高速化
    if len(diff_neg) > len(diff_pos):
        diff_neg, diff_pos = diff_pos, diff_neg


    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 and len(diff_neg) != 0:
        possible_max = min(sum(diff_pos), sum(diff_neg))
        possible_min = max(min(diff_pos), min(diff_neg))

        if possible_max - possible_min + 1 <= pow(2, len(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))
        # 定数倍高速化
        else:
            neg_all_pattern = []
            for p in product([True, False], repeat=len(diff_neg)):
                neg_all_pattern.append(sum([diff_neg[i] for i in range(len(diff_neg)) if p[i]]))
            for i in neg_all_pattern:
                pattern_pos = calc_pattern(diff_pos, i)
                ans += pattern_pos * pow(2, len(diff_zero))

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def add2(l):
    ys = []
    for i in range(len(l)):
        ys += [l[i] + x for x in l[i+1:]]
    return ys


def add(n, l):
    if not l:
        return []
    elif n == 2:
        return add2(l)
    else:
        ys = [x for x in add(n, l[1:])]
        ys += [l[0] + x for x in add(n-1, l[1:])]
        return ys


def main():
    n, a = (int(x) for x in input().split())
    xs = [int(x) for x in input().split()]

    # i == 1
    count = len(list(filter(lambda x: x == a, xs)))

    # i == 2 ~ n-2
    for i in range(2, n-1):
        ys = add(i, xs)
        count += len(list(filter(lambda x: x == a * i, ys)))

    # i == n-1
    ys = [sum(xs[:i]+xs[i+1:]) for i in range(n)]
    count += len(list(filter(lambda x: x == a * (n - 1), ys)))

    # i == n
    if sum(xs) == n * a:
        count += 1

    print(count)


if __name__ == '__main__':
    main()