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())
a=list(map(int, input().split()))
a.sort()

#部分点解法
if n<=16:
    ans=0
    for i in range(1, 2**n):
        B=bin(i)[2:].zfill(n)

        goukei=0
        ones=0
        for j,b in enumerate(B):
            if b=="1":
                ones+=1
                goukei+=a[j]
        if ones*A==goukei:
            ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:



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

for i in range(n):
    arr[i] = arr[i]%a

# print(arr)
tot = sum(arr)

dp = [[0 for i in range(a)] for j in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(a):
        dp[i+1][j] += dp[i][j]
        temp = j+arr[i]
        temp %= a
        dp[i+1][temp] += dp[i][j]

# print(dp)
print(dp[-1][0]-1)

Submission status: Wrong Answer

Solution code:



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

for i in range(n):
    arr[i] = arr[i]%a

print(arr)
tot = sum(arr)

dp = [[0 for i in range(a)] for j in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(a):
        dp[i+1][j] += dp[i][j]
        temp = j+arr[i]
        temp %= a
        dp[i+1][temp] += dp[i][j]

# print(dp)
print(dp[-1][0]-1)

Submission status: Wrong Answer

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

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

n,a = map(int, input().split())
X = list(map(int,input().split()))
Y = list(map(lambda x:x-a, X))
d = defaultdict(int)
d[0] = 1
print(Y)
for y in Y:
    for k,v in list(d.items()):
        d[k+y] += v
print(d[0]-1)

Submission status: Wrong Answer

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

cnt = 0
for i in range(n):
  for j in range(i, n):
    sm = sum(a[i:j + 1])
    if avg * (j - i + 1) == sm:
      cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
dp = [[[0 for k in range(3000)] for j in range(50 + 1)]for i in range(50 + 1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(i+1):
        for k in range(2500):
            dp[i+1][j+1][k+x[i]] = dp[i][j][k]
            dp[i+1][j][k] = dp[i][j][k]
ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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())


N,A = LI()
x = LI()

# i,j i: i文字目まで
# j: それまでのカウント
dp = [[0 for j in range(A)] for i in range(N+1)]

ans = 0

for i in range(N):
    for j in range(A):
        dp[i+1][j] = dp[i][j]
    for j in range(A):
        dp[i+1][(j + x[i]) % A] += dp[i][j]
    dp[i+1][x[i] % A] += 1

# print(dp)
print(dp[-1][0])

Submission status: Wrong Answer

Solution code:
n, a = map(int, input().split())
l = []
for i in map(int, input().split()):
	l.append(i - a)
l.sort()
pl = sorted([i for i in l if i > 0])
ml = sorted([-i for i in l if i < 0])
M = min(sum(pl), sum(ml))
dpp = [0] * (M + 1)
dpm = [0] * (M + 1)
s = 1
for i in pl:
	for j in range(s):
		if i + j <= M:
			dpp[i + j] += dpp[j] + 1
		else:
			break
	s += i
s = 1
for i in ml:
	for j in range(s):
		if i + j <= M:
			dpm[i + j] += dpm[j] + 1
		else:
			break
	s += i
ans=0
for i in range(1,M+1):
	ans+=dpp[i]*dpm[i]
z_cnt=l.count(0)
print(ans*pow(2,z_cnt)+int(pow(2,z_cnt))-1)

Submission status: Wrong Answer

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

ways = 0
def findNumOfWays(x, s, i, a, t):
	global ways
	try:
		if i >= len(x) or (s + x[i]) / (t + 1) > a:
			return
		else:
			avg = (s + x[i]) / (t + 1)
			if avg == a:
				ways += 1
				findNumOfWays(x, s, i + 1, a, t)
			elif avg < a:
				findNumOfWays(x, s + x[i], i + 1, a, t + 1)
				findNumOfWays(x, s, i + 1, a, t)

	except Exception as e:
		print(e)

	

findNumOfWays(x, 0, 0, a, 0)
print(ways)

Submission status: Wrong Answer

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
X = max(x)
y = [i - a for i in x]
dp = [[0 for t in range(2 * n * X + 10)] for j in range(n + 1)]
dp[0][n * X] = 1
for j in range(1, n + 1):
    for t in range(2 * n * X + 1):
        if 0 <= t - y[j - 1] <= 2 * n * X:
            dp[j][t] = dp[j - 1][t] + dp[j - 1][t - y[j - 1]]
        elif t - y[j - 1] < 0 and t - y[j - 1] > 2 * n * X:
            dp[j][t] = dp[j - 1][t]
print(dp[n][n * X] - 1)

Submission status: Wrong Answer

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
X = max(x)
y = [i - a for i in x]
dp = [[0 for t in range(2 * n * X + 10)] for j in range(n + 1)]
dp[0][n * X] = 1
for j in range(1, n + 1):
    for t in range(2 * n * X + 1):
        if 0 <= t - y[j - 1] <= 2 * n * X:
            dp[j][t] = dp[j - 1][t] + dp[j - 1][t - y[j - 1]]
        elif t - y[j - 1] < 0 and t - y[j - 1] > 2 * n * X:
            dp[j][t] = dp[j - 1][t]
print(dp[j][n * X] - 1)

Submission status: Wrong Answer

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
X = max(x)
y = [i - a for i in x]
dp = [[0 for t in range(2 * n * X + 1)] for j in range(n + 1)]
dp[0][n * X] = 1
for j in range(1, n + 1):
    for t in range(2 * n * X):
        if 0 <= t - y[j - 1] <= 2 * n * X:
            dp[j][t] = dp[j - 1][t] + dp[j - 1][t - y[j - 1]]
        elif t - y[j - 1] < 0 and t - y[j - 1] > 2 * n * X:
            dp[j][t] = dp[j - 1][t]
print(dp[j][n * X] - 1)

Submission status: Wrong Answer

Solution code:
def main():
	N, A = map(int, input().split())
	x = list(map(int, input().split()))
	pre_dp = [0 for _ in range(A)]
	for xi in x:
		dp = [0 for _ in range(A)]
		for i in range(A):
			if pre_dp[i] != 0:
				dp[(xi+i)%A] += pre_dp[i]
		for i in range(A):
			dp[i] += pre_dp[i]
		dp[xi%A] += 1
		pre_dp = list(dp)

	print(pre_dp[0])


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
def solve():
  n,a = (int(i) for i in input().split())
  x = list(int(i) for i in input().split())
  tp = max(x)
  if sum(x) < a*n:
    print(0)
    exit()
  
  dp = [[[0 for i in range(n*tp +1)] for j in range(n+1)] for k in range(n+1)]
  query = a*n
  dp[0][0][0] = 1
  for i in range(1,n+1):
    for j in range(n+1):
      for k in range(n*tp +1):
        #選ばない
        dp[i][j][k] = dp[i-1][j][k]
        if x[i-1] <= k and j > 0:
         dp[i][j][k] += dp[i-1][j-1][k-x[i-1]]
        
  ans = 0
  for j in range(1,n+1):
    ans += dp[n][j][j*a]
  #print(dp)
  print(ans)
  
  
  
  
  
  
solve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N, A = map(int, input().split())
    X = [int(c) - A for c in input().split()]
    d = defaultdict(lambda: 0)

    for x in X:
        keys = list(d.keys())
        for key in keys:
            d[key + x] += d[key]

        d[x] += 1

    return d[0]


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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N, A = map(int, input().split())
    X = [int(c) - A for c in input().split()]
    d = defaultdict(lambda: 0)

    for x in X:
        keys = list(d.keys())
        for key in keys:
            d[key + x] += d[key]

        d[x] += 1
        print(d)

    return d[0]


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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N, A = map(int, input().split())
    X = [int(c) - A for c in input().split()]
    d = defaultdict(lambda: 0)

    for x in X:
        keys = list(d.keys())
        for key in keys:
            d[key + x] += d[key]

        d[x] += 1
        print(d)

    print(X)    
    return d[0]


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

Submission status: Wrong Answer

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
stack=[0]*5001
stack[2500-a]=1
ans=0
for i in x:
  i-=a
for i in x:
  ans+=stack[2500-i+a]
  stack2=[i for i in stack]
  for j in range(5001):
    if 0<=j+i<=5000:
      stack2[j+i]+=stack[j]
  stack=[i for i in stack2]
print(stack[2500])

Submission status: Wrong Answer

Solution code:
#C問題  
N,A=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
X=max(max(x),A)
dp=[[[0 for i in range(N*X+1)] for j in range(N+1)] for k in range(N+1)]

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

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

Submission status: Wrong Answer

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

maxx = xlist[-1] if xlist[-1] > a else a
# dp[j][k][s]: x_1...x_jまでのなかからk枚選んで合計をsにする総数
dp = [[[0 for _ in range(maxx * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0][0] = 1  # 0枚選んで合計を0にするのは1通り
for j in range(n + 1):
  for k in range(n + 1):
    for s in range(maxx * k + 1):
      if j >= 1:  # x_0は選ばないのと同じなので0のまま更新しない
        if s < xlist[j-1]:
          dp[j][k][s] = dp[j-1][k][s]
        elif k >= 1 and s >= xlist[j-1]:
          dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-xlist[j-1]]

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

Submission status: Wrong Answer

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

maxx = xlist[-1] if xlist[-1] > a else a
# dp[j][k][s]: x_1...x_jまでのなかからk枚選んで合計をsにする総数
dp = [[[0 for _ in range(maxx * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0][0] = 1  # 0枚選んで合計を0にするのは1通り
for j in range(n + 1):
  for k in range(n + 1):
    for s in range(maxx * k + 1):
      if j >= 1 and s < xlist[j-1]:  # x_0は選ばないのと同じなので0のまま更新しない
        dp[j][k][s] = dp[j-1][k][s]
      elif j >= 1 and k >= 1 and s >= xlist[j-1]:
        dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-xlist[j-1]]

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

Submission status: Wrong Answer

Solution code:
N,A = map(int,input().split())
X = [int(e)-A for e in input().split()]
# dp[i][s]: i番目まで見て部分和がsとなるような場合の数
# 初期条件: dp[0][0] = 1
# 遷移: dp[i][s] += dp[i-1][s-X[i]] + dp[i-1][s]
# 答え: dp[N][0]
s_max = 5001
dp = [[0]*(s_max+1) for i in range(N+1)]
dp[0][2500] = 1
for i in range(1,N+1):
    for s in range(s_max+1):
        if 0 <= s-X[i-1] <= s_max:
            dp[i][s] += dp[i-1][s-X[i-1]]
        dp[i][s] += dp[i-1][s]
# 全てを選ばなかった1通りは除外
ans = dp[N][2500] - 1
print(X)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, A = map(int, input().split())
x = list(map(int, input().split()))
count = 0
x_all = []
for i in range(1, N+1):
    b = []
    a = list(itertools.combinations(x, i))
    for j in a:
        b.append(sum(list(j)))
    x_all.append(b)
base = 1
for i in x_all:
    for j in i:
        print(j)
        if j == A*base:
            count += 1
    base += 1
print(count)

Submission status: Wrong Answer

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

# dp[n][k][s] : n枚目までからk枚選んで合計をsにする場合の数
dp = [[[0 for _ in range(2501)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for n in range(N+1):
    for k in range(N+1):
        for s in range(A*k+1):
            if n>=1 and s<X[n-1]:
                dp[n][k][s] = dp[n-1][k][s]
            elif n>=1 and k>=1 and s>=X[n-1]:
                dp[n][k][s] = dp[n-1][k][s] + dp[n-1][k-1][s-X[n-1]]

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] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0]*(a*n+1) for k in range(n+1) ] for j in range(n)]


dp[0][0][0] = 1
if x[0]<= a*n:
    dp[0][1][x[0]] = 1
    
for j in range(n-1):
    for k in range(n+1):
        for s in range(a*n+1):
            if k == 0 and s == 0:
                dp[j+1][k][s] = 1
            if k>j+2:
                dp[j+1][k][s]=0
            elif s>=x[j+1] and k>= 1:
                dp[j+1][k][s]=dp[j][k][s] + dp[j][k-1][s-x[j+1]]
            else:
                dp[j+1][k][s]=dp[j][k][s]

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

print(1)

Submission status: Wrong Answer

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

#dp[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0 for s in range(a*n+1) ] for k in range(n+1) ] for j in range(n)]

for j in range(n):
    dp[j][0][0]=1
    if x[0]<= a*n:
        dp[j][1][x[0]] = 1

for j in range(n-1):
    for k in range(n+1):
        for s in range(a*n+1):
            if k>j+2:
                dp[j+1][k][s]=0
            elif s>=x[j+1] and k>= 1:
                dp[j+1][k][s]=dp[j][k][s] + dp[j][k-1][s-x[j+1]]
            else:
                dp[j+1][k][s]=dp[j][k][s]

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

print(1)

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
N, A = map(int, input().split())
x = list(map(int, input().split()))
MAX_X = 50

x.sort()

memo = [None] * (N * N * MAX_X * N)

def get(pos, tmp, cnt):
    # print("#", pos, tmp, cnt)
    # end
    if pos == N:
        if cnt > 0 and cnt * A == tmp:
            # print("##", pos, tmp, cnt, "end\tret=", 1)
            return 1
        else: return 0
    # read memo
    idx_memo = pos * (N * N * MAX_X) + cnt * (N * MAX_X) + tmp
    if memo[idx_memo] != None:
        # print("##", pos, tmp, cnt, "memo\tret=", memo[idx_memo])
        return memo[idx_memo]
    for cnt_sub in range(1, cnt):
        if tmp % cnt > 0: break
        tmp_sub = (tmp // cnt) * cnt_sub
        idx_memo = pos * (N * N * MAX_X) + cnt_sub * (N * MAX_X) + tmp_sub
        if memo[idx_memo] != None:
            # print("##", pos, tmp, cnt, "sub\tret=", memo[idx_memo])
            return memo[idx_memo]
    # process
    ret = 0
    ret += get(pos + 1, tmp + x[pos], cnt + 1) # take
    ret += get(pos + 1, tmp, cnt) # pass
    # write memo
    idx_memo = pos * (N * N * MAX_X) + cnt * (N * MAX_X) + tmp
    if memo[idx_memo] == None: memo[idx_memo] = ret
    # for cnt_sub in range(1, cnt):
    #     if tmp % cnt > 0: break
    #     tmp_sub = (tmp // cnt) * cnt_sub
    #     idx_memo = pos * (N * N * MAX_X) + cnt_sub * (N * MAX_X) + tmp_sub
    #     if memo[idx_memo] == None: memo[idx_memo] = ret
    return ret

print(get(0, 0, 0))

Submission status: Wrong Answer

Solution code:
N, A = [int(_) for _ in input().split()]
x = [int(i) for i in input().split()]

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

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

ans = 0
for i in range(1, N+1):
    if i*A <= sum(x):
        ans += dp[-1][i*A]

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, A = [int(_) for _ in input().split()]
X = [int(_) - A for _ in input().split()]
X_plus = [_ for _ in X if _ > 0]
X_minus = [-_ for _ in X if _ < 0]
l_plus = len(X_plus)
l_minus = len(X_minus)
l_zero = len(X) - l_plus - l_minus
s_plus = sum(X_plus)
s_minus = sum(X_minus)
dp_plus = {0: 1}
dp_minus = {0: 1}
for p in X_plus:
    for k, v in dp_plus.copy().items():
        dp_plus[p + k] = dp_plus.get(k, 0) + v
for m in X_minus:
    for k, v in dp_minus.copy().items():
        dp_minus[m + k] = dp_minus.get(k, 0) + v
c_zero = 2 ** l_zero
ans = c_zero - 1
for j in range(1, min(s_plus, s_minus) + 1):
    ans += c_zero * dp_plus.get(j, 0) * dp_minus.get(j, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
N, A = [int(_) for _ in input().split()]
X = [int(_) - A for _ in input().split()]
X_plus = [_ for _ in X if _ > 0]
X_minus = [-_ for _ in X if _ < 0]
l_plus = len(X_plus)
l_minus = len(X_minus)
l_zero = len(X) - l_plus - l_minus
s_plus = sum(X_plus)
s_minus = sum(X_minus)
dp_plus = [0] * (l_plus + 1)
dp_minus = [0] * (l_minus + 1)
for i in range(l_plus):
    dp_plus_old = dp_plus.copy()
    for j in range(l_plus + 1 - X_plus[i]):
        dp_plus[j + X_plus[i]] += dp_plus_old[j]
for i in range(l_minus):
    dp_minus_old = dp_minus.copy()
    for j in range(l_minus + 1 - X_minus[i]):
        dp_minus[j + X_minus[i]] += dp_minus_old[j]
ans = 2 ** l_zero - 1
for j in range(min(l_plus, l_minus) + 1):
    ans += dp_plus[j] * dp_minus[j]
print(ans)

Submission status: Wrong Answer

Solution code:
def generate_bin_list(num, target_list_len):
    flags = []
    for i in range(target_list_len):
        flags.append(0)
    b = list(bin(num))
    l_b = len(b)
    for j in range(0, l_b-2):
        flags[target_list_len-1-j] = int(b[l_b-1-j])
    print(flags)
    return flags


N, A = map(int, input().split())
X = list(map(int, input().split()))
l_X = len(X)
for i in range(l_X):
    X[i] -= A

length = pow(2, len(X))
cnt = 0
for i in range(1, length):
    flags = generate_bin_list(i, l_X)
    sum = 0
    for j in range(l_X):
        if flags[j] == 1:
            sum += X[j]
    if sum == 0:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
x = [t-a for t in x]
l = [0]*5005
m = [0]*5005
l[0] = 1
for t in x:
  for i in range(-2500,2500):
    m[i] = l[i] + l[i-t]
  l = m
print(l[0]-1)

Submission status: Wrong Answer

Solution code:
import itertools
N, A = map(int, input().split())
x = map(int, input().split())
ans = 0

for i in range(1, N+1):
    check = list(itertools.combinations(x,i))
    for j in check:
        if sum(j) % len(j) == 0 and (sum(j) // len(j)) == A:
            ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:

#ちょっと時間だけ計測してみる

iN,iA =[int(x) for x in input().split()]
aX = [int(x) - iA for x in input().split()]
#dX = {i:0 for i in range(-49,50)} #-49 - 49
dX = {}
for i in aX:
    if i not in dX:
        dX[i] = 1
    else:
        dX[i] += 1

def fnCr(iN,iR):
    if iN - iR < iR :
        iR = iN - iR
    if iN == 0 :
        return 0
    elif iR == 0:
        return 1
    elif iR == 1:
        return iN
    return iN / iR * fnCr(iN-1,iR-1)
aFr = [1]*(iN+1)
for i in range(1,iN+1):
    aFr[i] = aFr[i-1] * i

iRet = 0
iCZero = 0
if 0 in dX and 0 < dX[0]:
    iZ = dX[0]
    for i in range(1,iZ + 1):
        iCZero += int(aFr[iZ] / aFr[i] / aFr[iZ-i])
iRet += iCZero

iSumPlus = 0
iSumMinus = 0
for x in dX:
    iS = x * dX[x]
    if 0 <  x :
        iSumPlus += iS
    else:
        iSumMinus += iS
iUlim = min(iSumPlus , -1 * iSumMinus)

#for i in
#iSumPlus = sum([x for x in aX if 0 < x ])
#iSumMinus = -1 * sum([x for x in aX if x < 0  ])
#iUlim = min(iSumPlus,iSumMinus)
#for i in range(1,iUlim + 1):


print(iRet)

Submission status: Wrong Answer

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
X = max(max(x), a)
dp = [[[0] * (n * X + 1) for i in range(n + 1)] for j in range(n + 1)]
dp[0][0][0] = 1
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for s in range(n * X + 1):
            if s < x[i - 1]:
                dp[i][j][s] = dp[i - 1][j][s]
            elif x[i - 1] <= s:
                dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - x[i - 1]]

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

print(num)

Submission status: Wrong Answer

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
X = max(max(x), a)
dp = [[[0] * (n * X + 1) for i in range(n + 1)] for j in range(n + 1)]
dp[0][0][0] = 1
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for s in range(n * X + 1):
            if s < x[i - 1]:
                dp[i][j][s] = dp[i - 1][j][s]
            elif x[i - 1] <= s:
                dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - x[i - 1]]

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

print(num)

Submission status: Wrong Answer

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
X = max(max(x), a)
dp = [[[0] * (n * X + 1) for i in range(n + 1)] for j in range(n + 1)]
dp[0][0][0] = 1
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for s in range(n * X + 1):
            if s < x[i - 1]:
                dp[i][j][s] = dp[i - 1][j][s]
            elif x[i - 1] <= s:
                dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - x[i - 1]]

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

print(num)

Submission status: Wrong Answer

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
X = max(max(x), a)
dp = [[[0] * (n * X + 1) for i in range(n + 1)] for j in range(n + 1)]
dp[0][0][0] = 1
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for s in range(n * X + 1):
            if s < x[i - 1]:
                dp[i][j][s] = dp[i - 1][j][s]
            elif j >= 1 and x[i - 1] <= s:
                dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - x[i - 1]]

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

print(num)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

for i in range(N):
    x[i] -= A
X = max(max(x), A)

dp = [defaultdict(int) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for j in range(-X, X):
        if - N * X <= j - x[i] <= N * X:
            dp[i + 1][j] = dp[i][j] + dp[i][j - x[i]]
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[N][0] - 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

for i in range(N):
    x[i] -= A

dp = [defaultdict(int) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for j in range(-50, 50):
        dp[i + 1][j] = dp[i][j] + dp[i][j - x[i]]
print(dp[N][0] - 1)

Submission status: Wrong Answer

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

m = {}
def f(tgt, cv, cur, rest):
    if len(rest) == 0:
        if cv == tgt and cv != 0:
            return 1
        else:
            return 0
    if cv > tgt and rest[0] > A:
        return 0
    
    ans = 0
    
    cc = cur.copy()
    r = rest[1:]
    sig = (cv, len(cc), tuple(r))
    if sig in m:
        ans += m[sig]
    else:
        ret = f(tgt, cv, cc, r)
        m[sig] = ret
        ans += ret

    cc.append(rest[0])
    cv += rest[0]
    sig = (cv, len(cc), tuple(r))
    if sig in m:
        ans += m[sig]
    else:
        ret = f(tgt + A, cv, cc, r)
        m[sig] = ret
        ans += ret
    return ans

print(f(0, 0, [], X))

Submission status: Wrong Answer

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

m = {}
def f(tgt, cv, cur, rest):
    if len(rest) == 0:
        if cv == tgt:
            return 1
        else:
            return 0
    if cv > tgt and rest[0] > A:
        return 0
    
    ans = 0
    
    cc = cur.copy()
    r = rest[1:]
    sig = (cv, len(cc), tuple(r))
    if sig in m:
        ans += m[sig]
    else:
        ret = f(tgt, cv, cc, r)
        m[sig] = ret
        ans += ret

    cc.append(rest[0])
    cv += rest[0]
    sig = (cv, len(cc), tuple(r))
    if sig in m:
        ans += m[sig]
    else:
        ret = f(tgt + A, cv, cc, r)
        m[sig] = ret
        ans += ret
    return ans

print(f(0, 0, [], X) - 1)

Submission status: Wrong Answer

Solution code:
import itertools

n, a = map(int, input().split())
array = [int(x) for x in input().split()]

array2 = []
tmp = 0
for i in array:
    tmp += i
array2.append(tmp)
ans = 0

for pickup in range(1, n+1):
    tmp_gen = itertools.combinations(array, pickup)

for i in tmp_gen:
    if sum(i) == a*pickup:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from numpy import full
n, a = map(int, input().split())
x = [int(i) for i in input().split()]
X = max([a] + x)
dp = full((n+1, n+1, n*X+1), 0)
dp[0,0,0] = 1
for j in range(n+1):
    for k in range(n+1):
        for s in range(n*X+1):
            if j == k == s == 0: continue
            if j >= 1 and s < x[j-1]: dp[j, k, s] = dp[j-1, k, s]
            elif j >= 1 and k >= 1 and s >= x[j-1]: dp[j,k,s] = dp[j-1, k, s] + dp[j-1, k-1, s-x[j-1]]
            else: dp[j, k, s] = 0
print(sum([dp[n][k][k*a] for k in range(1, n+1)]))

Submission status: Wrong Answer

Solution code:
from numpy import full
n, a = map(int, input().split())
x = [int(i) for i in input().split()]
X = max(a, *x)
dp = full((n+1, n+1, n*X+1), 0)
dp[0,0,0] = 1
for j in range(n+1):
    for k in range(n+1):
        for s in range(n*X+1):
            if j == k == s == 0: continue
            if j >= 1 and s < x[j-1]: dp[j, k, s] = dp[j-1, k, s]
            elif j >= 1 and k >= 1 and s >= x[j-1]: dp[j,k,s] = dp[j-1, k, s] + dp[j-1, k-1, s-x[j-1]]
            else: dp[j, k, s] = 0
print(sum([dp[n][k][k*a] for k in range(1, n+1)]))

Submission status: Wrong Answer

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

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

# i番目までからj個選んで和をkにできる選び方の総数
# 選ばない状態も持ちたいから配列は1まわり大きく
dp = [[[0 for k in range(n*a+1)] for j in range(n+1)] for i in range(n+1)]

for i in range(n+1):
    for j in range(n+0):
        for k in range(n*a+1):
            # 初期条件
            if i == 0 and j == 0 and k == 0:
                dp[i][j][k] = 1

            # x_iが和を超過してしまう場合
            elif i > 0 and k < X[i-1]:
                dp[i][j][k] = dp[i-1][j][k]

            # 和を作れる場合
            # 加算する場合としない場合の両方を考える
            elif i > 0 and j > 0 and k >= X[i-1]:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

            # その他
            else:
                dp[i][j][k] = 0

# i枚選んだ時の合計がiAであればよい
ans = 0
for i in range(1, n+1):
    ans += dp[n][i][i*a]

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]

dp= np.zeros((n+1,n*a+1),dtype='int32')
dp[0][0]=1
ans=0
f=0
for k in range(1,n+1):
  kx=x[k-1]
  f+=kx
  for i in range(k,0,-1):
    for j in range(kx, n * a + 1):
      dp[i][j] += dp[i-1][j-kx]
      if j > f:
        break
      
for i in range(1,n+1):
  ans+=dp[i][a*i]

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]

dp= np.zeros((n+1,n*a+1),dtype='int32')
dp[0][0]=1
ans=0
f=0
for k in range(1,n+1):
  kx=x[k-1]
  f+=kx
  for i in range(k,0,-1):
    for j in range(kx , min(f,n*a) + 1):
      dp[i][j] += dp[i-1][j-kx]
      
      
for i in range(1,n+1):
  ans+=dp[i][a*i]

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]

dp= np.zeros((n+1,n+1,n*a+1),dtype=int)
dp[0][0][0]=1
ans=0

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

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]

dpa=[[[0]*(50*n+1)]*(n+1)]*(n+1)
dpa[0][0][0]=1
ans=0
t=0
dp=np.array(dpa)

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

Submission status: Wrong Answer

Solution code:
from itertools import compress
from statistics import mean

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

if N > 16:
    exit()

Sel = [0] * N
Cnt = 0

def func():
    global Cnt
    lst = list(compress(X, Sel))
    if not lst:
        return
    ave = mean(lst)
    if ave == A:
        Cnt += 1

def dfs(pos):
    if pos == N:
        func()
        return
    Sel[pos] = 0; dfs(pos + 1)
    Sel[pos] = 1; dfs(pos + 1)

dfs(0)
print(Cnt)