Problem:


Score : 300 points

Problem Statement

Tak has N cards. On the i-th (1 \leq i \leq N) card is written an integer x_i.
He is selecting one or more cards from these N cards, so that the average of the integers written on the selected cards is exactly A.
In how many ways can he make his selection?

Constraints

1 \leq N \leq 50

1 \leq A \leq 50

1 \leq x_i \leq 50

N,\,A,\,x_i are integers.

Partial Score

200 points will be awarded for passing the test set satisfying 1 \leq N \leq 16.

Input

The input is given from Standard Input in the following format:

N A
x_1 x_2 ... x_N

Output

Print the number of ways to select cards such that the average of the written integers is exactly A.

Sample Input 1

4 8
7 9 8 9

Sample Output 1

5

The following are the 5 ways to select cards such that the average is 8:

Select the 3-rd card.

Select the 1-st and 2-nd cards.

Select the 1-st and 4-th cards.

Select the 1-st, 2-nd and 3-rd cards.

Select the 1-st, 3-rd and 4-th cards.

Sample Input 2

3 8
6 6 9

Sample Output 2

0

Sample Input 3

8 5
3 6 2 8 7 6 5 9

Sample Output 3

19

Sample Input 4

33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

Sample Output 4

8589934591

The answer may not fit into a 32-bit integer.



Sample input:
4 8
7 9 8 9


Sample output:
5

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
for i in range(n):
    x[i] -= a
dp = [[0 for i in range(100 * n + 1)] for j in range(n + 1)]
dp[0][50 * n] = 1
for i in range(n):
    for j in range(100 * n + 1):
        j2 = j - 50 * n
        num = x[i]
        if -50 * n <= j2 - num <= 50 * n:
            dp[i + 1][j] = dp[i][j] + dp[i][j - num]
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[n][50 * n] - 1)

Submission status: Accepted

Solution code:
N,A = (int(T) for T in input().split())
X = [int(T)-A for T in input().split()]
DP = [[0]*(2*(50*N)+1) for TI in range(0,N+1)]
DP[0][50*N] = 1
for TI in range(0,N):
    for TS in range(0,2*50*N+1):
        if DP[TI][TS]!=0:
            DP[TI+1][TS] += DP[TI][TS]
            DP[TI+1][TS+X[TI]] += DP[TI][TS]
print(DP[N][50*N]-1)

Submission status: Accepted

Solution code:
N,A = (int(T) for T in input().split())
X = [int(T) for T in input().split()]
DP = [[[0]*(N+1) for TS in range(0,50*N+1)] for TI in range(0,N+1)]
DP[0][0][0] = 1
for TI in range(0,N):
    for TS in range(0,50*N+1):
        for TK in range(0,N+1):
            if DP[TI][TS][TK]!=0:
                DP[TI+1][TS][TK] += DP[TI][TS][TK]
                DP[TI+1][TS+X[TI]][TK+1] += DP[TI][TS][TK]
print(sum(DP[N][A*TA][TA] for TA in range(1,N+1)))

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
ls1 = [0] + list(map(int,input().split()))

dp = [[[0 for k in range(2600)] for j in range(51) ] for i in range(51)]
for i in range(51):
    dp[i][0][0] = 1
for j in range(1,N+1):
    for k in range(1,j+1):
        for s in range(2600):
            if s < ls1[j]:
                dp[j][k][s] = dp[j-1][k][s]
            elif s >= ls1[j]:
                dp[j][k][s] = dp[j-1][k-1][s-ls1[j]] + dp[j-1][k][s]
ans = 0
for k in range(1,N+1):
    ans += dp[N][k][k*A]
print(ans)

Submission status: Accepted

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

for i in range(n):
    x[i] -= a

x.sort()

if x[0] > 0 or x[-1] < 0:
    print(0)
    exit()

num_zero = x.count(0)

if x[0] == 0 or x[-1] == 0:
    print(pow(2, num_zero) - 1)
    exit()

xp = [i for i in x if i > 0]
xm = [-i for i in x if i < 0]

sum_xp = sum(xp) + 1
dp = [0] * sum_xp
dp[0] = 1
for i in xp:
    new_dp = [0] * sum_xp
    for j in range(sum_xp - i):
        new_dp[i + j] += dp[j]
    for j in range(sum_xp):
        dp[j] += new_dp[j]

for i in xm:
    new_dp = [0] * sum_xp
    for j in range(i, sum_xp):
        new_dp[j - i] += dp[j]
    for j in range(sum_xp):
        dp[j] += new_dp[j]

print(dp[0] * pow(2, num_zero) - 1)

Submission status: Accepted

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

dp = [[[0]*(sum_x+1) for _ in range(n+1)] for _ in range(n+1)]
#dp[i][j][k]はi番目までのカードの中からj枚選んで、合計がkになるときの選び方の総数
dp[0][0][0] = 1

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, a = map(int, input().split())
x = list(map(int, input().split()))
s = sum(x)
dp = [[[0] * (s+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(1, n+1):
    xi = x[i-1]
    for j in range(s+1):
        for k in range(i):
            dp[i][k][j] = dp[i-1][k][j]
    for j in range(xi, s+1):
        for k in range(1, i+1):
            dp[i][k][j] += dp[i-1][k-1][j-xi]

ans = 0
for i in range(1, n+1):
    if i*a > s:
        break
    ans += dp[n][i][i*a]
print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, a = LI()
x = LI()

# dp[i][j][k] := i番目まで見たときj個使用してkを作る場合の数
dp = [[[0] * (2500+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n+1):
    xi = x[i-1]
    for j in range(2500+1):
        for k in range(i):
            dp[i][k][j] = dp[i-1][k][j]
    for j in range(xi, 2500+1):
        for k in range(1, i+1):
            dp[i][k][j] += dp[i-1][k-1][j-xi]
ans = 0
for i in range(1, n+1):
    ans += dp[-1][i][i*a]
print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, a = LI()
x = LI()

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

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
def ncr(n,r):
    ret = 1
    if n<r:
        return 0
    if n-r <r:
        r = n-r
    for i in range(1,r+1):
        ret*=(n-r+i)
        ret//=i
    return ret

n,a = ma()
X = lma()
for i in range(n):
    X[i] -= a
co = collections.Counter(X)
ans = 0
mx = 49*n #ずれの最大はA=1,x=50 2*mx +1この配列
dp = [[0 for j in range(-mx,mx+1)] for i in range(n+1)]# dp[i][j] iまで使って値をjにする組み合わせ
dp[-1][0] = 1 #一個も使わない組み合わせ
for i in range(n):
    x = X[i]
    #print(x)
    for j in range(-mx,mx+1,1):
        dp[i][j] += dp[i-1][j] + dp[i-1][j-x] #選ばない/ぶ
        #if j==0:print(i,j,dp[i-1][j] , dp[i-1][j-x])
print(dp[n-1][0]-1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, a = map(int, input().split())
    X = list(map(int, input().split()))
    MAX = 50 * 50 + 1

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, A = map(int, readline().split())
X = list(map(int,readline().split()))
Y = [x-A for x in X]
dp = {0:1}

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, A = map(int, readline().split())
X = list(map(int,readline().split()))
Y = [x-A for x in X]
dp = {0:1}

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

Submission status: Accepted

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[0] - 1)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
X = list(map(int,input().split()))
Y = [x-A for x in X]
dp = {0:1}

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

print(dp[0]-1)

Submission status: Accepted

Solution code:
def abc044_c():
    #値入力
    _, A = map(int, input().split())
    X = list(map(lambda x : int(x)-A,input().split()))
    #初期値
    d = {0:1}
    for x in X:
        for k,v in list(d.items()):
            d[k + x] = d.get(k + x,0) + v #差分の合計
    ans = d[0] - 1 #差分合計0で初期値を除く
    print(ans)

if __name__ == '__main__':
    abc044_c()

Submission status: Accepted

Solution code:

NMAX = 55
T = 2500
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))

dp = [[0]*5001 for i in range(NMAX)]  # i時点で総和がSになるものの個数

dp[0][T] = 1

for i in range(N):
    for s in range(5001):
        if s+X[i] > 5001 or dp[i][s] == 0:
            continue
        dp[i+1][s] += dp[i][s]
        dp[i+1][s+X[i]] += dp[i][s]

print(dp[N][T]-1)

Submission status: Accepted

Solution code:

NMAX = 55

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

dp = [[[0] * NMAX for s in range(3000)] for i in range(NMAX)]

dp[0][0][0] = 1 # dp[i][s][k]: i個からk個選ぶとき、総和がsのものの個数
for i in range(N): # N-1時点でNが更新されるのでここまでで十分
    for s in range(3000):
        for k in range(N+1):
            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]

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

print(ans)

Submission status: Accepted

Solution code:

NMAX = 55

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

dp = [[[0] * NMAX for s in range(3000)] for i in range(NMAX)]

dp[0][0][0] = 1 # dp[i][s][k]: i個からk個選ぶとき、総和がsのものの個数
for i in range(N): # N-1時点でNが更新されるのでここまでで十分
    for s in range(N*A+1):
        for k in range(N+1):
            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]

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

print(ans)

Submission status: Accepted

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

dp=[[[0]*(2550) for _ in range(55)] for _ in range(55)]
dp[0][0][0]=1
for i in range(n):
    for j in range(n+1):
        for sm in range(n*a+1):
            if dp[i][j][sm]==0:
                continue
            dp[i+1][j][sm]+=dp[i][j][sm]
            dp[i+1][j+1][sm+x[i]]+=dp[i][j][sm]

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

Submission status: Accepted

Solution code:
def solve():
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
 
    dp = [[0] * (A * N + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i, x in enumerate(X):
        for j in reversed(range(1, i + 2)):
            for a in range(x, A * N + 1):
                dp[j][a] += dp[j - 1][a - x]
    print(sum(dp[i][A * i] for i in range(1, N + 1)))
 
solve()

Submission status: Accepted

Solution code:
def abc044_c():
    N, A = map(int, input().split())
    X = list(map(lambda x: int(x) - A, input().split()))  # 平均ターゲットを引いた状態
    dp = [dict() for _ in range(N+1)]  # 負の値を取り得るため、配列でなく辞書で持つ
    dp[0][0] = 1  # 0枚時点で何も選ばない、を初期値とする
    for i, x in enumerate(X):
        dp[i+1] = dp[i].copy()  # 前の状態を引き継ぐ
        for val, cnt in dp[i].items():
            dp[i+1][val + x] = dp[i].get(val + x, 0) + cnt  # 前のターンのxシフト分を加算
    ans = dp[N][0] - 1
    print(ans)

if __name__ == '__main__':
    abc044_c()

Submission status: Accepted

Solution code:
def abc044_c():
    ''' 過去提出を参考に '''
    _, A = map(int, input().split())
    X = list(map(lambda x: int(x) - A, input().split()))
    d = {0: 1}  # 負の値を取り得るため、配列でなく辞書で持つ
    for x in X:
        prev = list(d.items())  # 前のターンのぶんを保持しておく
        for val, cnt in prev:
            d[val + x] = d.get(val + x, 0) + cnt
    ans = d[0] - 1
    print(ans)

if __name__ == '__main__':
    abc044_c()

Submission status: Accepted

Solution code:
def abc044_c():
    import numpy as np
    n, a = map(int, input().split())
    x = list(map(lambda x: int(x) - a, input().split()))  # 平均ターゲット値を引いておく
    x = np.array(x, dtype=np.int64)

    vrange = n * (a + np.max(x))  # 取りうる値の幅(片側), 広めにとってもかまわない
    dp = np.zeros((n+1, 2*vrange+1), dtype=np.int64)  # DPテーブル
    dp[0, vrange] = 1  # 0枚時点で何も選ばずに総和0(平均ターゲット)になる場合を初期値にセット

    for i in np.arange(n):
        # 1つ前のターンを引き継ぐ
        dp[i+1, :] += dp[i, :]
        if 0 < x[i]:
            # x[i]が正の値、1つ前のx[i]個ぶん左側をスライドして持ってくる
            dp[i+1, x[i]:] += dp[i, :-x[i]]
        elif x[i] < 0:
            # x[i]が負の値、1つ前のx[i]個ぶん右側をスライドして持ってくる
            dp[i+1, :x[i]] += dp[i, -x[i]:]
        else:
            # x[i]がゼロ
            dp[i+1, :] += dp[i, :]

    ans = dp[n, vrange] - 1  # 初期値(何も選ばない)の1通りを除く
    print(ans)

if __name__ == '__main__':
    abc044_c()

Submission status: Accepted

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

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

maxint = 50 * N

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

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

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

res = 0

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

print(res)

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros((n + 1, MAX + 1), np.int64)
dp[0][0] = 1

for e in x:
    dp[1:, e:] += dp[:-1, :-e]

cnt = np.arange(1, n + 1)
sm = cnt * a
ans = dp[cnt, sm].sum()

print(ans)

Submission status: Accepted

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

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

for i, e in enumerate(x, 1):
    for j in range(i):
        for k in range(MAX + 1):
            dp[i][j][k] += dp[i-1][j][k]

    for j in range(i):
        for k in range(MAX - e + 1):
            dp[i][j+1][k+e] += dp[i-1][j][k]

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

print(ans)

Submission status: Accepted

Solution code:
import collections
N, A = [int(_) for _ in input().split()]
X = [int(_) for _ in input().split()]


def calc(W):
    #dp[m][s]=m枚のカードの和がsとなるような選び方の総数
    M = len(W)
    dp = [collections.defaultdict(int) for _ in range(M + 1)]
    dp[0][0] = 1
    for i, w in enumerate(W):
        for j in range(i, -1, -1):
            for k, v in dp[j].items():
                dp[j + 1][k + w] += v
    return dp


dpx = calc(X)
print(sum(dpx[i][i * A] for i in range(1, N + 1)))

Submission status: Accepted

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

# dp[i][j][k]：　i枚目までのカードをj枚使用して合計kを作れる組み合わせ
dp = np.zeros((n+1, n+1, 3001)).astype(np.int64)
dp[0][0][0] = 1

for i in range(n):
    _x = x[i]
    for j in range(n):
        dp[i+1, j+1, _x:] += dp[i, j, :-_x]
        dp[i+1, j, :] += dp[i, j, :]

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

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0]*(2501) for i in range(51)] for j in range(51)]
#dp[i][j][k]は、i番目まででj枚とって総数kとなる取り方
for i in range(n+1):
    dp[i][0][0]=1
for i in range(n):
    for j in range(1,i+2):
        for k in range(1,2501):
            if k-x[i]>=0:
                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][j][a*j]
print(ans)

Submission status: Accepted

Solution code:
n , a= map(int , input().split())
arr = list(map(int , input().split()))
dp = [ [[ 0 for j in range(0 , a*(n+2))] for k in range(0 , n+2)] for i in range(0,n+2)]
dp[0][0][0]=1
b=[0 for i in range(0 , n+1)]
for i in range(0 , n):
	b[i+1]=arr[i]
for i in range(1 , n+1):	# choosing only first i elements
	for j in range(0 , i+1):# choosing only j elements from first i elements
		for k in range(0 , a*(n)+2):# no of ways of forming a sum k taking j elements out of i elements
			if k<b[i]:
				dp[i][j][k]=dp[i-1][j][k]
			else:
				dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-b[i]]
tot = 0
for i in range(1 , n+1):
	tot = tot + dp[n][i][(i)*a]
print(tot)

Submission status: Accepted

Solution code:
n , a= map(int , input().split())
arr = list(map(int , input().split()))
dp = [ [[ 0 for j in range(0 , a*(n+2))] for k in range(0 , n+2)] for i in range(0,n+2)]
dp[0][0][0]=1
b=[0 for i in range(0 , n+1)]
for i in range(0 , n):
	b[i+1]=arr[i]
for i in range(1 , n+1):
	for j in range(0 , i+1):
		for k in range(0 , a*(n)+2):
			if k<b[i]:
				dp[i][j][k]=dp[i-1][j][k]
			else:
				dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-b[i]]
tot = 0
for i in range(1 , n+1):
	tot = tot + dp[n][i][(i)*a]
print(tot)

Submission status: Accepted

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

dpp = [0]*3000
dpm = [0]*3000

p = []
m = []
n0 = 0

for i in range(n):
    x1 = x[i] - a
    if x1 == 0:
        n0 += 1
    elif x1 > 0:
        p.append(x1)
    else:
        m.append(-x1)

for i in p:
    for j in range(2600,0,-1):
        if dpp[j] >= 1:
            dpp[j+i] += dpp[j]
    dpp[i] += 1

for i in m:
    for j in range(2600,0,-1):
        if dpm[j] >= 1:
            dpm[j+i] += dpm[j]
    dpm[i] += 1

ans = 0

for i in range(3000):
    ans += dpp[i] * dpm[i]

ans *= pow(2,n0)
ans += pow(2,n0) - 1

print(ans)

Submission status: Accepted

Solution code:
#想定解法
N, A = map(int, input().split())
X = sorted(list(map(int, input().split())))
xm = max(X)
xm = max(xm, A)
for i in range(N):
  X[i] -= A 
#print(X, xm)
dp = [[0] * (2 * N * xm + 1) for i in range(N + 1)]
dp[0][N * xm] = 1

for i in range(1, N + 1):
  for j in range(2 * N * xm + 1):
    if 0 <= j - X[i - 1] <= 2 * N * xm:
      dp[i][j] = dp[i - 1][j] + dp[i - 1][j - X[i - 1]]
    else:
      dp[i][j] = dp[i - 1][j]

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

Submission status: Accepted

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

    X = [x - A for x in X]

    neg = pos = 0
    for x in X:
        if x > 0:
            pos += x
        else:
            neg += x

    M = pos - neg
    base = -neg

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

    for i in range(N):
        for s in range(M + 1):
            dp[i + 1][s] = dp[i][s]
            if 0 <= s - X[i] <= M:
                dp[i + 1][s] += dp[i][s - X[i]]

    print(dp[N][base] - 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    X = [x - A for x in X]
    base = 2500
    dp = [[0] * 5001 for _ in range(N + 1)]
    dp[0][base] = 1

    for i in range(N):
        for s in range(5001):
            dp[i + 1][s] = dp[i][s]
            if 0 <= s - X[i] <= 5000:
                dp[i + 1][s] += dp[i][s - X[i]]

    print(dp[N][base] - 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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


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

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

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

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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


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

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

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

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    dp = [[0] * (N * 50 + 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], N * 50 + 1):
                dp[j][k] += dp[j - 1][k - X[i]]

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    dp = [[0] * (N * 50 + 1) for j in range(N + 1)]
    dp[0][0] = 1

    for i in range(N):
        for j in range(N, -1, -1):
            for k in range(N * 50 + 1):
                if k - X[i] >= 0 and j > 0:
                    dp[j][k] += dp[j - 1][k - X[i]]

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

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

dp[0][0] = 1

for i in range(0, N):
    for cnt in range(N, 0, -1):
        for val in range(N * A, -1, -1):
            if val - X[i] >= 0:
                dp[cnt][val] += dp[cnt - 1][val - X[i]]

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

print(ans)

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
X = list(map(int,input().split()))
Y = [x-A for x in X]
dp = {0:1}

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

print(dp[0]-1)

Submission status: Accepted

Solution code:
import numpy as np
n,a=map(int,input().split())
x=list(map(int,input().split()))
s=sum(x)
dp=np.zeros((n,s+1),dtype=np.int64)
for i in range(n):
    for j in range(i)[::-1]:
        dp[j+1][x[i]:]+=dp[j][:-x[i]]
    dp[0][x[i]]+=1
t=0
for k in range(n):
    if (k+1)*a<=s:
        t+=dp[k][(k+1)*a]
print(t)

Submission status: Accepted

Solution code:
import sys

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

integers=[x-a for x in cards]
cards.append(a)
f=max(cards)*n


dp=[[0 for i in range(n+1)] for j in range(2*f+1) ]

for y in range(n+1):
    for x in range(2*f+1):
        if y==0 and x==f:
            dp[x][y]=1
        elif y>0 and (x-integers[y-1]<0 or x-integers[y-1]>2*f):
            dp[x][y]=dp[x][y-1]
        elif y>0 and x-integers[y-1]>=0 and x-integers[y-1]<=2*f:
            dp[x][y]=dp[x-integers[y-1]][y-1]+dp[x][y-1]
        else:
            dp[x][y]=0
print(dp[f][n]-1)

Submission status: Accepted

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

Submission status: Accepted

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

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

for j in range(N):
    for k in range(N):
        for s in range(sumX):
            if dp[j][k][s]==0:
                continue
            dp[j+1][k][s] += dp[j][k][s]
            dp[j+1][k+1][s+X[j]] += dp[j][k][s]
ans = 0

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

Submission status: Accepted

Solution code:
N,A=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0]*(2501) for i in range(N+1)] for k in range(N+1)]
dp[0][0][0]=1
for j in range(N):
  for k in range(N):
    for i in range(2501):
      if dp[j][k][i]==0:
        continue
      dp[j+1][k][i]+=dp[j][k][i]
      dp[j+1][k+1][i+x[j]]+=dp[j][k][i]
ans=0
for j in range(N+1):
    ans+=dp[N][j][j*A]
print(ans-1)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter

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

    ans = 0
    counter = Counter()

    counter[0] += 1
    for i in range(n):
        cur = a - x[i]
        counter_next = Counter()
        for key, val in counter.items():
            counter_next[key] += val
            counter_next[cur + key] += val
        counter = counter_next

    print(counter[0] - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,A = map(int,input().rstrip().split(" "))
X = list(map(int,input().rstrip().split(" ")))
DPq = [0 for _ in range(1300)]
DPp = [0 for _ in range(1300)]
DPp[0] = 1
DPm = [0 for _ in range(1300)]
DPm[0] = 1
just = 0
ans = 0
for i in X:
    if i > A:
        for i2 in range(1250,-1,-1):
            DPp[i2 + (i - A)] += DPp[i2]
    elif i < A:
        for i2 in range(1250,-1,-1):
            DPm[i2 + (A - i)] += DPm[i2]
    else:
        just += 1
for i in range(1250):
    ans += DPp[i] * DPm[i]
ans *= 2 ** just
ans -=1
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


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

N, A = getNM()
Q = getList()
for i in range(N):
    Q[i] -= A

dp = [[0] * 5002 for i in range(N + 1)]
dp[0][2501] = 1

for i in range(1, N + 1):
    for j in range(5002):
        dp[i][j] += dp[i - 1][j]
        if 0 <= j - Q[i - 1] <= 5001:
            dp[i][j] += dp[i - 1][j - Q[i - 1]]

print(dp[-1][2501] - 1)

Submission status: Accepted

Solution code:
def main():
    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):
        for i in reversed(range(k+1)):
            for j in range(50 * N + 1 -x[k]):
                dp[i+1][j+x[k]] += dp[i][j]
    r = 0
    for i in range(1, N+1):
        r += dp[i][i*A]
    return r
print(main())

Submission status: Accepted

Solution code:
import copy
def main():
    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):
        dpn = copy.deepcopy(dp)
        for i in range(k+1):
            for j in range(50 * N + 1 -x[k]):
                dpn[i+1][j+x[k]] += dp[i][j]
        dp = dpn
    r = 0
    for i in range(1, N+1):
        r += dp[i][i*A]
    return r
print(main())