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())
X = list(map(int,input().split()))
ans = 0

def make_array(dims,fill):
    if len(dims) == 1:
        return [fill]*dims[0]
    ret = []
    nxt = dims[1:]
    for i in range(dims[0]):
        ret.append(make_array(nxt,fill))
    return ret
S = sum(X)+1
dp = make_array([N+2,N+2,S],0)
dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for s in range(S-X[i]):
            dp[i+1][j+1][s+X[i]] += dp[i][j][s]
            dp[i+1][j][s] += dp[i][j][s]
ans = 0
for j in range(1,N+1):
    for s in range(1,S+1):
        if j*A == s:
            print(j,s,dp[-2][j][s])
            ans += dp[-2][j][s]
print(ans)

Submission status: Wrong Answer

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
s = sum(x)
m = max(x)
dp = [[[0] * (s + 1) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

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

ans = 0
for j in range(1, n + 1):
    if j * a <= s:
        ans += dp[n][j][j * a]

print(ans)

Submission status: Wrong Answer

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

def solve(N: int, A: int, x: "List[int]"):
    ## dp[i][j][k] = i番目までのカードからjマイ選んで合計kにする選び方の総数
    dp = [[[0]*2501 for _ in range(N+1)] for _ in range(N+1)]

    for i in range(N):
        dp[i][0][0] = 1

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

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

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from itertools import combinations
from statistics import mean


def main():
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
    comb = []
    for n in range(1, N):
        comb += [mean(c) == A for c in list(combinations(X, n))]
    print(sum(comb))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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

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

def main():
    N, A = LI()
    X = LI()
    dp[0][0][0] = 1
    # for i in range(51):
    #     dp[i][0][0] = 1

    for i in range(N):
        for j in range(2501):
            for k in range(N+1):
                if j - X[i] >= 0 and k - 1 >= 0:
                    dp[i+1][j][k] += dp[i][j-X[i]][k-1]
                dp[i+1][j][k] += dp[i][j][k]
    cnt = 0
    for k in range(1, N+1):
        print('k: ', k, ' k*A: ', k*A)
        print(dp[N][k*A][k])
        cnt += dp[N][k*A][k]
    print(cnt)
main()

Submission status: Wrong Answer

Solution code:
import itertools
from statistics import mean
import math

a = float(input().split(' ')[1])
x = [int(i)for i in input().split(' ')]
if mean(x) == a:
    print(math.factorial(len(x)))
else:
    select = sum([1 for i in x if i==int(a)])
    for i in range(2, len(x)+1):
        for j in itertools.combinations(x,i):
            if mean(j) == a:
                select += 1
     
    print(select)

Submission status: Wrong Answer

Solution code:
import itertools
from statistics import mean

a = int(input().split(' ')[1])
x = [int(i)for i in input().split(' ')]
select = 0
for i in range(1, len(x)):
    select = select + sum([1 for j in itertools.combinations(x,i) if mean(j)==float(a)])

print(select)

Submission status: Wrong Answer

Solution code:
import itertools
from statistics import mean

a = int(input().split(' ')[1])
x = [int(i)for i in input().split(' ')]
select = []
for i in range(1, len(x)):
    select = select + [1 for j in itertools.combinations(x,i) if mean(j)==float(a)]

print(sum(select))

Submission status: Wrong Answer

Solution code:
import numpy as np


n, a = map(int, input().split())
X = np.array(list(map(int, input().split())))
X -= a

plus = X[X > 0]
zero = X[X == 0]
minus = abs(X[X < 0])

num_count = np.zeros(2551, dtype=np.int32)
num_count[0] = 1

for num in plus:
    num_count[num:] = num_count[:-num] + num_count[num:]

for num in minus:
    num_count[:-num] = num_count[:-num] + num_count[num:]

ans = 2 ** len(zero) * (num_count[0])

print(ans-1)

Submission status: Wrong Answer

Solution code:
import numpy as np


n, a = map(int, input().split())
X = np.array(list(map(int, input().split())))
X -= a

plus = X[X > 0]
zero = X[X == 0]
minus = abs(X[X < 0])

num_count = np.zeros(2551, dtype=np.int32)
num_count[0] = 1

for num in plus:
    num_count[num:] += num_count[:-num]

for num in minus:
    num_count[:-num] += num_count[num:]

ans = 2 ** len(zero) * num_count[0]
print(ans-1)

Submission status: Wrong Answer

Solution code:
import numpy as np


n, a = map(int, input().split())
X = np.array(list(map(int, input().split())))
X -= a

plus = X[X > 0]
zero = X[X == 0]
minus = abs(X[X < 0])

num_count = np.zeros(2551, dtype=np.int32)

for num in plus:
    num_count[num:] += num_count[:-num]
    num_count[num] += 1

for num in minus:
    num_count[:-num] += num_count[num:]

ans = 2 ** len(zero) * (num_count[0]+1)

print(ans - 1)

Submission status: Wrong Answer

Solution code:
import numpy as np


n, a = map(int, input().split())
X = np.array(list(map(int, input().split())))
X -= a

over = X[X > 0]
zero = X[X == 0]
down = X[X < 0]
down = abs(down)

num_count = np.zeros(2551, dtype=np.int32)

for num in over:
    num_count = num_count + np.hstack([np.zeros(num, dtype=np.int32), num_count[:-num]])
    num_count[num] += 1

for num in down:
    num_count = num_count + np.hstack([num_count[num:], np.zeros(num, dtype=np.int32)])

ans = 2 ** len(zero) * (num_count[0]+1)

print(ans - 1)

Submission status: Wrong Answer

Solution code:
import numpy as np


n, a = map(int, input().split())
X = np.array(list(map(int, input().split())))
X -= a

over = X[X > 0]
zero = X[X == 0]
down = X[X < 0]
down = abs(down)

over_count = np.zeros(2551, dtype=np.int32)
down_count = np.zeros(2551, dtype=np.int32)

for num in over:
    over_count = over_count + np.hstack([np.zeros(num, dtype=np.int32), over_count[:-num]])
    over_count[num] += 1

for num in down:
    down_count = down_count + np.hstack([np.zeros(num, dtype=np.int32), down_count[:-num]])
    down_count[num] += 1

base = 2 ** len(zero)
ans = 2 ** len(zero)
for num in range(1, 2501):
    p1 = over_count[num]
    p2 = down_count[num]
    pattern = p1 * p2
    ans += pattern * base

print(ans - 1)

Submission status: Wrong Answer

Solution code:
import numpy as np


n, a = map(int, input().split())
X = np.array(list(map(int, input().split())))
X -= a

over = X[X > 0]
zero = X[X == 0]
down = X[X < 0]
down = abs(down)

over_count = np.zeros(2505, dtype=np.int32)
down_count = np.zeros(2505, dtype=np.int32)

for num in over:
    over_count = over_count + np.hstack([np.zeros(num, dtype=np.int32), over_count[:-num]])
    over_count[num] += 1

for num in down:
    down_count = down_count + np.hstack([np.zeros(num, dtype=np.int32), down_count[:-num]])
    down_count[num] += 1

base = 2 ** len(zero)
ans = 2 ** len(zero)
for num in range(1, 2501):
    p1 = over_count[num]
    p2 = down_count[num]
    pattern = p1 * p2
    ans += pattern * base

print(ans - 1)

Submission status: Wrong Answer

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
if n>=17:
    exit()
cnt=0
for i in range(1,1<<n):
    ans=0
    f=0
    for j in range(n):
        if i>>j&1:
            ans+=x[j]
            f+=1
    if ans==f*a:
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
N, A = map(int,input().split())
x = list(map(int,input().split()))
if N >= 17:
    print(0)
    exit(0)

ans = 0
for k in range(2**N):
    t = []
    for d in range(N):
        if (k>>d)&1 == 1:
            t.append(x[d])
    if len(t) > 0:
        if A-0.000001 < sum(t)/len(t) < A+0.000001 :
            ans += 1
print(ans)

Submission status: Wrong Answer

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

y= list(map(lambda i:i-a, x))

def dp(k,l):
  if k == 0:
    if l == 0:
      return 1
    elif l == y[k]:
      return 1
    else:
      return 0
  return dp(k-1,l) + dp(k-1,l-y[k])

print(dp(len(y)-1,0)-1)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
n, a = map(int, input().split())
l = list(map(int, input().split()))
c = 0
for r in range(1, n):
    temp = list(combinations(l, r))
    for item in temp:
        if sum(item)/len(item) == a:
            c += 1
print(c)

Submission status: Wrong Answer

Solution code:
import itertools
from statistics import mean, median,variance,stdev

N, A = map(int, (input().split()))
xn = list(map(int, input().split()))
ans = 0
for i in range(N+1):
  p = list(itertools.permutations(xn,i))
  for j in p:
    if len(j) == 1:
#      print("j is {}, j = A is {}".format(j,j[0]==A))
      if j[0] == A:
        ans += 1
    elif len(j) > 1 and len(j) < N:
      m = mean(j)
#      print("j is {}, mean(j) is {}".format(j,m))
      if m == A:
        ans += 1
    elif len(j) == N:
#      print("j is {}, mean(j) is {}".format(j,m))
      m = mean(j)
      if m == A:
        ans += 1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
from statistics import mean, median,variance,stdev

N, A = map(int, (input().split()))
xn = list(map(int, input().split()))
ans = 0
for i in range(N):
  p = list(itertools.permutations(xn,i))
  for j in p:
    if len(j) == 1:
      print("j is {}, j = A is {}".format(j,j[0]==A))
      if j[0] == A:
        ans += 1
    elif len(j) > 1:
      m = mean(j)
      print("j is {}, mean(j) is {}".format(j,m))
      if m == A:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
n, a = map(int, input().split())
l = list(map(int, input().split()))
r = 0
a = str(a) + '.0'


def avg(l):
    return sum(l)/len(l)


for i in range(1, n):
    temp = list(combinations(l, i))
    temp = [str(avg(s)) for s in temp]
    r += temp.count(a)
print(r)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
 
 

    
kai,av=[int(x) for x in input().rstrip().split()]
l=[int(x) for x in input().rstrip().split()]
l.sort()

for i in range(len(l)):
    if av<=l[i]:
        l=l[i:]
        break

ll=[i for i in range(1,kai+1)]
result=[]
count=0
    
    
for i in ll:
    for j in combinations(l,r=i):
        if av==(sum(j)/i):
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
n,a=map(int,input().split())
import numpy as np
x=np.array(input().split(),dtype=int)
x-=a
pluslist=[]
minuslist=[]
zerocnt=0
for i in range(len(x)):
  if x[i]==0:
    zerocnt+=1
  elif x[i]>0:
    pluslist.append(x[i])
  else:
    minuslist.append(x[i]*(-1))

dpplus=np.full((sum(pluslist)+1),0,dtype=int)
dpminus=np.full((sum(minuslist)+1),0,dtype=int)
dpplus[0]=1
dpminus[0]=1
for v in pluslist:
  for i in range(len(dpplus)-1,-1,-1):
    if dpplus[i]!=0:
      dpplus[i+v]+=dpplus[i]
for v in minuslist:
  for i in range(len(dpminus)-1,-1,-1):
    if dpminus[i]!=0:
      dpminus[i+v]+=dpminus[i]

ans=zerocnt
for i in range(1,min(len(dpplus),len(dpminus))):
  ans+=dpplus[i]*dpminus[i]*(zerocnt+1)
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n, a, *x = map(int, sys.stdin.read().split())

def main():
    res = [[[0] * (a * n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    res[0][0][0] = 1
    for i in range(n):
        cur = x[i]
        for j in range(i+2):
            for k in range(a * (i+1) + 1):
                res[i+1][j][k] += res[i][j][k]
                if k >= cur:
                    res[i+1][j][k] += res[i][j-1][k-cur]
    
    ans = 0
    for j in range(1, n+1):
        ans += res[n][j][j*a]

    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
N, A = map(int, input().split())
*x, = map(int, input().split())
l = N * A + 1

# dp[n枚選ぶ][m枚目まで][総和]
dp = [[[0] * l for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1
for n in range(0, N + 1):
    for m in range(N):
        for s in range(0, l):
            dp[n][m + 1][s] += dp[n][m][s]
            if s >= x[m]:
                dp[n][m + 1][s] += dp[n - 1][m][s - x[m]]

print(sum([dp[n][N][n * A] for n in range(1, N + 1)]) % 10**9)

Submission status: Wrong Answer

Solution code:
[n,a]=list(map(int,input().split()))
xlist=list(map(int,input().split()))
xlist.sort()
ans=0
for i in range(n):
	ave=a*i
	dp=[-1 for j in range(ave+1)]
	dp[0]=1
	for k in xlist:
		for l in range(len(xlist)):
			if l<=ave:
				if dp[l]!=-1 and l+k<=ave:
					if dp[l+k]==-1:
						dp[l+k]=0
					dp[l+k]+=dp[l]
	if dp[-1]==-1:
		dp[-1]=0
	ans+=dp[-1]
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

dp1 = [[0 for i in range(N + 1)] for j in range(50 * N + 1)] #[Sum, #Cards]
dp2 = [[0 for i in range(N + 1)] for j in range(50 * N + 1)] #[Sum, #Cards]
dp1[0][0]=1

for i in range(N):#Focus Card [x_i]
  for j in range(N):
    for k in range(50 * N + 1):
        dp2[k][j] = 0
  #Not Use x_i
  for j in range(N):
    for k in range(50 * N + 1):
        dp2[k][j] += dp1[k][j]
  #Use x_i
  for j in range(N):
    for k in range(50 * N + 1):
      if k + X[i] <= 50*N:
        dp2[k + X[i]][j+1] += dp1[k][j]
  for j in range(N):
    for k in range(50 * N + 1):
        dp1[k][j] = dp2[k][j]

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

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

max = sum(x_list)
coefficient = 1  # Aの係数
result = 0
while coefficient * A <= max or coefficient < N:
    for r in range(1, N):
        combis = combinations(x_list, r)
        for combi in combis:
            if sum(combi) == coefficient * A:
                result += 1
        coefficient += 1

print(result)

Submission status: Wrong Answer

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

def ls(j,k,s,x):
  if j==0 and k==0 and s==0:
    return 1
  elif j>=1 and s<x[j-1]:
    return ls(j-1,k,s,x)
  elif j>=1 and k>=1 and s>=x[j-1]:
    return ls(j-1,k,s,x)+ls(j-1,k-1,s-x[j-1],x)
  else:
    return 0
              
way=0
for k in range(N)[1:]:
    way+=ls(N,k,k*A,x)
print(way)

Submission status: Wrong Answer

Solution code:
import numpy as np


def main(n, a, x):
    X_MAX = max(a, max(x))
    dp = np.zeros(shape=(n + 1, X_MAX * 2 + 1), dtype=int)
    dp[0][X_MAX] = 1
    for j in range(1, len(dp)):
        for t in range(len(dp[j])):
            xj = x[j - 1]
            yj = xj - a
            if 0 <= t - yj <= X_MAX * 2:
                dp[j][t] = dp[j - 1][t] + dp[j - 1][t - yj]
            else:
                dp[j][t] = dp[j - 1][t]
    return dp[n][X_MAX] - 1


if __name__ == '__main__':
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
    print(main(N, A, X))

Submission status: Wrong Answer

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

def Count(j,k,s):
	if(j >= 1 and k==0 and s==0):
		return 1
	elif(j >= 1 and s < x[j-1]):
		return Count(j-1,k,s)
	elif(j >= 1 and k>=1 and s >= x[j-1]):
		return Count(j-1,k,s) + Count(j-1,k-1,s-x[j-1])
	elif(j < k):
		return 0
	else:
		return 0

sum=0
for i in range(1,n+1):
	sum += Count(n,i,i*a)
print(sum)

Submission status: Wrong Answer

Solution code:
import itertools
n, a = map(int, input().split())
x = list(map(lambda x: int(x) - a, input().split()))
cnt = 0
for i in range(1, n):
    l = list(itertools.combinations(x, i))
    for j in range(len(l)):
        if sum(l[j]) == 0:
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter

from operator import mul
from functools import reduce
def cmb(n,r):
	if n < r:return 0
	if r == 0 or n-r == 0:return 1
	r = min(n-r,r)
	u = reduce(mul, range(n, n-r, -1))
	d = reduce(mul, range(1,r+1))
	return u//d

n,a,*x = map(int,open(0).read().split())
dp = [[0]*2501 for _ in range(n+1)]
dp[0][0] = 1
lim1 = lim2 = 1
for k,v in Counter(x).items():
	for i in range(1,v+1):
		c = cmb(v,i)
		for j in range(lim1)[::-1]:
			for s in range(lim2)[::-1]:
				dp[j+i][s+k*i] += dp[j][s]*c
	lim1 += v
	lim2 += k*v
cnt = 0
for i in range(1,n+1):
	cnt += dp[i][i*a]
print(cnt)

Submission status: Wrong Answer

Solution code:
def f(n,x,i):
    if n == 0:
        if i != 0:
            if x/i == m:
                return 1
        return 0

    if memo[n-1][x] != -1:return memo[n-1][x]

    memo[n-1][x] = f(n-1,x,i)+f(n-1,x+a[n-1],i+1)
    return memo[n-1][x]

n, m= map(int,input().split())
a = list(map(int,input().split()))
memo = [[-1 for _ in range(sum(a)+1)]for i in range(n)]
print(f(n,0,0))

Submission status: Wrong Answer

Solution code:
N,A=list(map(int,input().split()))
x=list(map(int,input().split()))
count=0
if A in x:
    count+=1
if sum(x)==N*A:
    count+=1
for num in range(2,N):
    sum=0
    for i in range(N-num+2):
        def_sum=0
        if i==N-num+1 and num!=2:
            for k in range(num-1):
                def_sum+=x[i+k]
            for j in range(2,N-num+2):
                sum=def_sum+x[i-j]
                if sum / num ==A:
                    count+=1
        else:            
            for k in range(num-1):
                def_sum+=x[i+k]
            for j in range(num-1,N-i):
                sum=def_sum+x[i+j]
                if sum / num == A:
                    count+=1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

pair_memo = {}
def pair_pattern(a, b=None):
  if 0 in [a, b]:
    return 0
  
  if b in [None, 1]:
    return a
  
  if a == 1:
    return b
  
  key = "{a},{b}".format(**locals())
  if key in pair_memo:
    return pair_memo[key]
  
  pair_memo[key] = pair_pattern(a - 1, b) * pair_pattern(a, b - 1) - 1
  return pair_memo[key]

def sign_special(x):
  if x >= 0:
    return 0
  else:
    return 1
    
if __name__ == "__main__":
  n, a = map(int, input().split())
  list_x = list(map(int, input().split()))
  elem = lambda : [0, 0]
  x_group_by_abs = defaultdict(elem)
  x_group_by_abs[0] = [0]

  for x in list_x:
    x_group_by_abs[abs(x - a)][sign_special(x - a)] += 1 
    
  ans = 1
  for x_g in x_group_by_abs.values():
    p = pair_pattern(*x_g)
    # print(f"{x_g}: {p}")
    ans *= p + 1

  ans -= 1
  print(ans)

Submission status: Wrong Answer

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

X = max(x)

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

for j in range(N+1):
    for t in range(2*N*X):
        if j==0 and t==N*X:
            dp[j][t] = 1
        elif t-x[j-1] < 0 or t-x[j-1] > 2*N*X:
            dp[j][t] = dp[j-1][t]
        elif 0 < t-x[j-1] and t-x[j-1] < 2*N*X:
            dp[j][t] = dp[j-1][t] + dp[j-1][t-x[j-1]]
        else:
            dp[j][t] = 0

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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

  ans=0
  for i in range(1,n):
    for c in itertools.combinations(l,i):
      if sum(c)/len(c)==a:
        ans+=1
  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc044/tasks/arc060_a
# C - 高橋君とカード / Tak and Cards
import itertools


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

x_list = sorted(x_list)

c = 0

if N <= 16:
    p_gen = itertools.product([0, 1], repeat=N)
    for pattern in p_gen:
        total, n = 0, 0
        for p, x in zip(pattern, x_list):
            total += x * p
            n += p

        if n != 0:
            if total / n == A:
                c += 1

print(c)

Submission status: Wrong Answer

Solution code:
from statistics import mean
from itertools import combinations

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

applicable_count = 0

for i in range(1, len(x)):
  c = combinations(x, i)
  for j in c:
    if mean(j) == a:
      applicable_count += 1
print(applicable_count)

Submission status: Wrong Answer

Solution code:
[n,a]=list(map(int,input().split()))
xlist=list(map(int,input().split()))
xx=max(xlist)
saidai=max(xx, a)
dp=[[[0 for s in range(saidai*n)]for k in range(n)]for j in range(n)]
dp[0][0][0]=1
        
for k in range(1,n):
	for s in range(saidai*n):
		dp[0][k][s]=0
	
#それ以降漸化式
for j in range(1, n):
	for k in range(j):
		for s in range(saidai*n):
			if s>=xlist[j]:
				dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xlist[j]]
			else:
				dp[j][k][s]=dp[j-1][k][s]
goukei=0
for l in range(n):
    for m in range(l):
        goukei+=dp[l][m][a*m]
		
print(goukei)

Submission status: Wrong Answer

Solution code:
N, A = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
mat = {}
def dp(i, x):
  if i == N:
    if len(x) and sum(x) == A * len(x):
      return 1
    else:
      return 0
  if (i, sum(x)) in mat:
    return mat[(i, sum(x))]
  ret = dp(i + 1, x[:]) + dp(i + 1, x[:] + [X[i]])
  mat[i, sum(x)] = ret
  return int(ret)

print(dp(0, []))

Submission status: Wrong Answer

Solution code:
N, A = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
mat = {}
def dp(i, x):
  if i == N:
    if len(x) and sum(x) == A * len(x):
      return 1
    else:
      return 0
  if (i, sum(x)) in mat:
    return mat[(i, sum(x))]
  ret = dp(i + 1, x[:]) + dp(i + 1, x[:] + [X[i]])
  mat[i, sum(x)] = ret
  return ret

print(dp(0, []))

Submission status: Wrong Answer

Solution code:
N, A = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
mat = {}
def dp(i, x):
  if i == N:
    if len(x) and sum(x) == A * len(x):
      return 1
    else:
      return 0
  elif len(x) and (i, sum(x)) in mat:
    return mat[(i, sum(x))]
  ret = dp(i + 1, x[:]) + dp(i + 1, x[:] + [X[i]])
  if len(x):
    mat[i, sum(x)] = ret
  return ret

print(dp(0, []))

Submission status: Wrong Answer

Solution code:
N, A = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
mat = {}
def dp(i, x):
  if i == N:
    if len(x) and sum(x) == A * len(x):
      return 1
    else:
      return 0
  elif len(x) and (i, sum(x)) in mat:
    return mat[(i, sum(x))]
  ret = dp(i + 1, x) + dp(i + 1, x + [X[i]])
  if len(x):
    mat[i, sum(x)] = ret
  return ret

print(dp(0, []))

Submission status: Wrong Answer

Solution code:
N, A = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
mat = {}
def dp(i, x):
  if i == N:
    if len(x) and sum(x) == A * len(x):
      return 1
    else:
      return 0
  elif len(x) and (i, sum(x)/len(x)) in mat:
    return mat[(i, sum(x)/len(x))]
  ret = dp(i + 1, x) + dp(i + 1, x + [X[i]])
  if len(x):
    mat[i, sum(x)/len(x)] = ret
  return ret

print(dp(0, []))

Submission status: Wrong Answer

Solution code:
N, A = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
mat = {}
def dp(i, x):
  if i == N:
    if len(x) and sum(x)/len(x) == A:
      return 1
    else:
      return 0
  elif len(x) and (i, sum(x)/len(x)) in mat:
    return mat[(i, sum(x)/len(x))]
  ret = dp(i + 1, x) + dp(i + 1, x + [X[i]])
  if len(x):
    mat[i, sum(x)/len(x)] = ret
  return ret

print(dp(0, []))

Submission status: Wrong Answer

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

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

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

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

    sxp_tmp=sxp[j]+x

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

        if sxp[k]==sxp_tmp:
          sxp_n_i.append([k,sxp_n[j]])
        elif sxp[k]>sxp_tmp:
          sxp_add.append([k,sxp_tmp,sxp_n[j]])
        else:
          sxp_add.append([k+1,sxp_tmp,sxp_n[j]])
        break

  for k in range(len(sxp_add)):
    sxp.insert(k+sxp_add[k][0],sxp_add[k][1])
    sxp_n.insert(k+sxp_add[k][0],sxp_add[k][2])
  for l in sxp_n_i:
    sxp_n[l[0]]+=l[1]



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

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


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

Submission status: Wrong Answer

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

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

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

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

    sxp_tmp=sxp[j]+x

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

        if sxp[k]==sxp_tmp:
          sxp_n_i.append([k,sxp_n[j]])
        elif sxp[k]>sxp_tmp:
          sxp_add.append([k,sxp_tmp,sxp_n[j]])
        else:
          sxp_add.append([k+1,sxp_tmp,sxp_n[j]])
        break

  for k in range(len(sxp_add)):
    sxp.insert(k+sxp_add[k][0],sxp_add[k][1])
    sxp_n.insert(k+sxp_add[k][0],sxp_add[k][2])
  for l in sxp_n_i:
    sxp_n[l[0]]+=l[1]



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

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


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

Submission status: Wrong Answer

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

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

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

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

    sxp_tmp=sxp[j]+x

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

        if sxp[k]==sxp_tmp:
          sxp_n_i.append([k,sxp_n[j]])
        elif sxp[k]>sxp_tmp:
          sxp_add.append([k,sxp_tmp,sxp_n[j]])
        else:
          sxp_add.append([k+1,sxp_tmp,sxp_n[j]])
        break

  for k in range(len(sxp_add)):
    sxp.insert(k+sxp_add[k][0],sxp_add[k][1])
    sxp_n.insert(k+sxp_add[k][0],sxp_add[k][2])
  for l in sxp_n_i:
    sxp_n[l[0]]+=l[1]



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

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


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