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=input().split()

for i in range(N):
    x[i]=int(x[i])
X=max(max(x),A)
for i in range(N):
    x[i]=x[i]-A
dp=[[0 for t in range(2*N*X+1)] for j in range(N+1)]

for j in range(N+1):
    for t in range(2*N*X+1):
        if j==0 and t==N*X:dp[j][t]=1
        elif j>=1:
            if t-x[j-1]<0 or t-x[j-1]>2*N*X:
                dp[j][t]=dp[j-1][t]
            elif t-x[j-1]>=0 and t-x[j-1]<=2*N*X:
                dp[j][t]=dp[j-1][t]+dp[j-1][t-x[j-1]]
print(dp[N][N*X]-1)
#http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

if __name__ == "__main__":
    N, A = map(int, input().split())
    x = [i-A for i in map(int, input().split())]
    X = max(x + [A])
    dp = [[0] * (2*N*X + 1) for _ in range(N+1)]
    for row in range(N+1):
        for column in range(2*N*X):
            if row == 0 and column == N*X:
                dp[row][column] = 1
            elif row >=1 and (column - x[row-1] < 0 or column - x[row-1] > 2*N*X):
                    dp[row][column] = dp[row-1][column]
            elif row >=1 and 0 <= column - x[row-1] <= 2*N*X:
                dp[row][column] = dp[row-1][column] + dp[row-1][column-x[row-1]]
            else:
                dp[row][column] = 0
    print(dp[N][N*X]-1)

Submission status: Accepted

Solution code:
def func(n, a, x):
    # NX
    # x.sort()
    x = [i - a for i in x]
    minus = 0
    plus = 0
    for _x in x:
        if _x > 0:
            plus += _x
        else:
            minus += _x
    # print("x:{}".format(x))
    dp = [[0] * (plus - minus + 1) for j in range(n + 1)]
    # 平均がAとは,x[i]-Aの和が0となること
    # dp[j][t] = "xからj枚以上選んで和が「t-(負のxの和)」の場合の数"
    # 0 <= j <= N
    # 0 <= t <= (正のx[i]-Aを全て選ぶ) - (負のx[i]-Aを全て選ぶ)
    # dp[j][t] = dp[j-1][t-x[j]] + dp[j-1][t]
    # dp[0][-(負のxの和)] = 1 #初期シード,1つも選ばない場合は1通り
    # dp[0][-(負のxの和)でない] = 0
    dp[0][-minus] = 1
    for j in range(1, len(dp)):
        for t in range(len(dp[0])):
            # print("j:{} dp({},{})".format(j, len(dp), len(dp[0])))
            dp[j][t] = dp[j - 1][t]
            # print("t:{} x[{}]:{}".format(t, j-1, x[j-1]))
            if len(dp[0]) > t - x[j-1] >= 0:
                # print(t - x[j-1])
                dp[j][t] += \
                    dp[j - 1][t - x[j-1]]
    return dp[n][-minus] - 1


n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
print(func(n, a, x))
"""
print(func(4, 8, [7, 8, 9, 9]) == 5)  # 合計33
print(func(3, 8, [6, 6, 9]) == 0)  # 合計21
print(func(8, 5, [3, 6, 2, 8, 7, 6, 5, 9]) == 19)  # 合計46
print(func(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])
      == 8589934591)  # 合計46
"""

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
X = [0]+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(1,N+1):
    for k in range(n+1):
        for s in range(50*k+1):
            if s<X[n]:
                dp[n][k][s] = dp[n-1][k][s]
            elif k>=1 and s>=X[n]:
                dp[n][k][s] = dp[n-1][k][s] + dp[n-1][k-1][s-X[n]]

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

print(Ans)

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
X = [0]+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(1,N+1):
    for k in range(n+1):
        for s in range(50*k+1):
            if n>=1 and s<X[n]:
                dp[n][k][s] = dp[n-1][k][s]
            elif n>=1 and k>=1 and s>=X[n]:
                dp[n][k][s] = dp[n-1][k][s] + dp[n-1][k-1][s-X[n]]

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

print(Ans)

Submission status: Accepted

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(50*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: Accepted

Solution code:
import collections
N, A = map(int, input().split())
ys = [int(x) - A for x in input().split()]

dp = collections.defaultdict(lambda: 0)
dp[0] = 1
for y in ys:
    for accum, count in list(dp.items()):
        dp[accum + y] += count
found = -1 # for dp[0]
for accum, count in dp.items():
    if accum == 0:
        found += count
print(found)

Submission status: Accepted

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
M = max(x)
M = max(M,a)
dp = [[[0]*(n*M+1) 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+1):
        for s in range(n*M+1):
            if dp[j][k][s]:
                dp[j+1][k][s] += dp[j][k][s]
                dp[j+1][k+1][s+x[j]] += dp[j][k][s]

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

print(ans)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
maxn = max(max(X), A)
 
dp = [[0 for _ in range(2 * N * maxn + 1)] for _ in range(N + 1)]
dp[0][N * maxn] = 1
 
for i in range(N):
    for k in range(2 * N * maxn + 1):
        dp[i + 1][k] = dp[i][k]
        if 0 <= k - X[i] < 2 * N * maxn:
            dp[i + 1][k] += dp[i][k - X[i]]
 
print(dp[N][N * maxn] - 1)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
maxn = max(max(X), A)
 
dp = [[0 for _ in range(2 * N * maxn + 1)] for _ in range(N + 1)]
dp[0][N * maxn] = 1
 
for i in range(N):
    for k in range(2 * N * maxn + 1):
        dp[i + 1][k] = dp[i][k]
        if 0 <= k - X[i] <= 2 * N * maxn:
            dp[i + 1][k] += dp[i][k - X[i]]
 
print(dp[N][N * maxn] - 1)

Submission status: Accepted

Solution code:
import collections
N, A = map(int, input().split())
xs = list(map(int, input().split()))

dp = collections.defaultdict(lambda: 0)
dp[(0, 0)] = 1
for n, x in enumerate(xs, start=1):
    for (k, accum), count in list(dp.items()):
        dp[(k + 1, accum + x)] += count
found = 0
for (k, accum), count in dp.items():
    if k > 0 and k * A == accum:
        found += count
print(found)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
maxn = max(max(X), A)

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

for i in range(N):
    for k in range(2 * N * maxn + 1):
        dp[i + 1][k] = dp[i][k]
        if 0 <= k - X[i] <= 2 * N * maxn:
            dp[i + 1][k] += dp[i][k - X[i]]

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

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
M = max(x)
M = max(M, a)
dp = [[[0]*(n*M+1) 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+1):
        for s in range(n*M+1):
            if dp[j][k][s]:
                dp[j+1][k][s] += dp[j][k][s]
                dp[j+1][k+1][s + x[j]] += dp[j][k][s]

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

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
maxn = max(max(X), A)

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

for i in range(N):
    for k in range(2 * N * maxn + 1):
        dp[i + 1][k] = dp[i][k]
        if 0 <= k - X[i] <= 2 * N * maxn:
            dp[i + 1][k] += dp[i][k - X[i]]

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

Submission status: Accepted

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: Accepted

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

dp = [[0 for j in range(100 * N + 1)] for i in range(N+1)]
dp[0][50 * N] = 1
#-50～50マデノ値ガ入ルカモ

for i in range(N):
    for j in range(100*N + 1):
        dp[i+1][j] = dp[i][j]
        if 0 <= j-X[i] <= 100*N:
            dp[i+1][j] += dp[i][j - X[i]]
        
print(dp[N][50 * N] -1)

Submission status: Accepted

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

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

for i in range(N):
    for j in range(50, 100 * N + 1 - 50):
        dp[i + 1][j] = dp[i][j] + dp[i][j - x[i]]
        
print(dp[N][50 * N] - 1)

Submission status: Accepted

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+1-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: Accepted

Solution code:
from collections import defaultdict
import copy

N,A=map(int,input().split())
C=list(map(int,input().split()))
CA=[C[i]-A for i in range(N)]

CAMINUS=[]
CAPLUS=[]
ZERO=0
for c in CA:
    if c>0:
        CAPLUS.append(c)
    elif c<0:
        CAMINUS.append(c)
    else:
        ZERO+=1


MINDP=defaultdict(int)
PLUDP=defaultdict(int)

for c in CAMINUS:
    NDP=copy.copy(MINDP)
    for m in MINDP:
        NDP[m+c]+=MINDP[m]

    NDP[c]+=1

    MINDP=NDP

for c in CAPLUS:
    NDP=copy.copy(PLUDP)
    for m in PLUDP:
        NDP[m+c]+=PLUDP[m]

    NDP[c]+=1

    PLUDP=NDP


ANS=2**ZERO-1

for m in MINDP:
    ANS+=MINDP[m]*PLUDP[-m]*2**ZERO

print(ANS)

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
l=[int(i) for i in input().split()]
ans=0
#dp=[[[0 for i in range(51)] for j in range(51)] for k in range(2501)]
dp=[[[0 for i in range(2501)] for j in range(51)] for k in range(51)]
dp[0][0][0]=1

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

Submission status: Accepted

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_zero = len(X) - len(X_plus) - len(X_minus)
s_plus = sum(X_plus)
s_minus = sum(X_minus)
dp_plus = {0: 1}
dp_minus = {0: 1}
for p in X_plus:
    dp_plus_old = dp_plus.copy()
    for k, v in dp_plus_old.items():
        dp_plus[k + p] = dp_plus_old.get(k, 0) + dp_plus_old.get(k + p, 0)
for m in X_minus:
    dp_minus_old = dp_minus.copy()
    for k, v in dp_minus_old.items():
        dp_minus[k + m] = dp_minus_old.get(k, 0) + dp_minus_old.get(k + m, 0)
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: Accepted

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 = [1] + [0] * s_plus
dp_minus = [1] + [0] * s_minus
for i in range(l_plus):
    dp_plus_old = dp_plus.copy()
    for j in range(s_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(s_minus + 1 - X_minus[i]):
        dp_minus[j + X_minus[i]] += dp_minus_old[j]
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[j] * dp_minus[j]
print(ans)

Submission status: Accepted

Solution code:
N, A = [int(_) for _ in input().split()]
X = [int(_) - A for _ in input().split()]
M = max(X + [A])
dp = [0] * (2 * N * M + 1)
dp[N * M] = 1
for x in X:
    dp_old = dp.copy()
    for i in range(max(-x, 0), min(2 * N * M + 1, 2 * N * M + 1 - x)):
        dp[i + x] += dp_old[i]
print(dp[N * M] - 1)

Submission status: Accepted

Solution code:
N, A = [int(_) for _ in input().split()]
X = [int(_) - A for _ in input().split()]
dp = [0] * 3000 + [1] + [0] * 3000
for x in X:
    dp_old = dp.copy()
    for i in range(max(-x, 0), min(6001, 6001 - x)):
        dp[i + x] += dp_old[i]
print(dp[3000] - 1)

Submission status: Accepted

Solution code:
import collections

# input
n, a = map(int, input().split())
X = [int(i) - a for i in input().split()]

S = collections.Counter([0, X[0]])
# Xから1枚以上選んで作ることが可能な和:作り方の場合の数
# 1枚も選ばない＝0:1通り
# X[0]のみ選ぶ＝X[0]:1通り

for i in X[1:]: # 選べるカードを増やしていく (X[0] ~ X[i] から選ぶ)
    S_temp = collections.Counter()
    for s, c in S.items():
        S_temp[s + i] += c # X[0] ~ X[i - 1] で作れる和に X[i] を足す
    S += S_temp

print(S[0] - 1) # 1枚も選ばないのはルール違反

Submission status: Accepted

Solution code:
import collections

# input
n, a = map(int, input().split())
X = [int(i) - a for i in input().split()]

sums = collections.Counter([0, X[0]])
# Xから1枚以上選んで作ることが可能な和:作り方の場合の数
# 1枚も選ばない＝0:1通り
# X[0]のみ選ぶ＝X[0]:1通り

for i in X[1:]: # 選べるカードを増やしていく (X[0] ~ X[i] から選ぶ)
    sums2 = collections.Counter()
    for s, c in sums.items():
        sums2[s + i] += c # X[0] ~ X[i - 1] で作れる和に X[i] を足す
    sums += sums2

print(sums[0] - 1) # 1枚も選ばないのはルール違反

Submission status: Accepted

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

Submission status: Accepted

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

S = [[None] * N for x in range(3000)]
def search(value, pos):
    if pos == N: return 0 if value else 1
    if S[value + A][pos] is not None: return S[value + A][pos]
    S[value + A][pos] = search(value, pos + 1) + search(value + X[pos], pos + 1)
    return S[value + A][pos]

print(search(0, 0) - 1)

Submission status: Accepted

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

X = max(max(xs), A)
ys = [x - A for x in xs]
ys.sort(reverse=True)
dp = [[0] * (2 * N * X + 1) for i 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 - ys[j-1] < 2 * N * X:
            dp[j][t] = dp[j-1][t] + dp[j-1][t-ys[j-1]]
        else:
            dp[j][t] = dp[j-1][t]

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

Submission status: Accepted

Solution code:
#正負で分割
#dpの作り方はARCの方の人のロジックを参考にした。
def 解():
    iN,iA =[int(x) for x in input().split()]
    aX = [int(x) - iA for x in input().split()]
    aPlus = [x for x in aX if 0 < x ]
    aMinus = [-1 * x for x in aX if x < 0  ]
    iLenPlus = len(aPlus)
    iLenMinus = len(aMinus)
    iLen0 = iN - iLenPlus - iLenMinus

    iCZero = 2**iLen0  #sum(k=1..N){nCk} = 2^n -1 #1は組み合わせ0の場合
    iRet = 0
    iUlim = min(sum(aPlus) , sum(aMinus))
    if 0 < iUlim:
        dp1 = {0:1}
        for iX in aPlus:
            for k,v in dp1.copy().items():
                n = k+iX
                if n <= iUlim:
                    dp1[n] = dp1.get(n,0)+v
        dp2 = {0:1}
        for iX in aMinus:
            for k,v in dp2.copy().items():
                n = k+iX
                if n <= iUlim:
                    dp2[n] = dp2.get(n,0)+v
        for i in range(1,iUlim+1):
            if i in dp1 and i in dp2:
                iRet += dp1[i] * dp2[i]
    print((iRet+1)*iCZero  -1) #組み合わせ0の場合を引く
解()

Submission status: Accepted

Solution code:

#正負で分割
#dpの作り方はARCの方の人のロジックを参考にした。
#こんなんでええんや...
def 解():
    iN,iA =[int(x) for x in input().split()]
    aX = [int(x) - iA for x in input().split()]
    aPlus = [x for x in aX if 0 < x ]
    aMinus = [-1 * x for x in aX if x < 0  ]
    iLenPlus = len(aPlus)
    iLenMinus = len(aMinus)
    iLen0 = iN - iLenPlus - iLenMinus

    iCZero = 2**iLen0  #sum(k=1..N){nCk} = 2^n -1 #1は組み合わせ0の場合
    iRet = 0
    iUlim = min(sum(aPlus) , sum(aMinus))
    if 0 < iUlim:
        dp1 = {0:1}
        for iX in aPlus:
            for k,v in dp1.copy().items():
                dp1[k+iX] = dp1.get(k+iX,0)+v
        dp2 = {0:1}
        for iX in aMinus:
            for k,v in dp2.copy().items():
                dp2[k+iX] = dp2.get(k+iX,0)+v
        for i in range(1,iUlim+1):
            if i in dp1 and i in dp2:
                iRet += dp1[i] * dp2[i]
    print((iRet+1)*iCZero  -1) #組み合わせ0の場合を引く
解()

Submission status: Accepted

Solution code:
#正負で分割
#dpの作り方はARCの方の人のロジックを参考にした。
#こんなんでええんや...
def 解():
    iN,iA =[int(x) for x in input().split()]
    aX = [int(x) - iA for x in input().split()]
    aPlus = [x for x in aX if 0 < x ]
    aMinus = [-1 * x for x in aX if x < 0  ]
    iLenPlus = len(aPlus)
    iLenMinus = len(aMinus)
    iLen0 = iN - iLenPlus - iLenMinus

    iCZero = 2**iLen0 - 1 #sum(k=1..N){nCk} = 2^n -1

    iRet = 0
    iRet += iCZero
    iCZero += 1 #0の場合を追加

    iUlim = min(sum(aPlus) , sum(aMinus))
    if 0 < iUlim:
        dp1 = {0:1}
        for iX in aPlus:
            for k,v in dp1.copy().items():
                dp1[k+iX] = dp1.get(k+iX,0)+v
        dp2 = {0:1}
        for iX in aMinus:
            for k,v in dp2.copy().items():
                dp2[k+iX] = dp2.get(k+iX,0)+v
        for i in range(1,iUlim+1):
            if i in dp1 and i in dp2:
                iRet += iCZero * dp1[i] * dp2[i]
    print(iRet)
解()

Submission status: Accepted

Solution code:
def 解():
    iN,iA =[int(x) for x in input().split()]
    aX = [int(x) - iA for x in input().split()]
    aPlus = [x for x in aX if 0 < x ]
    aMinus = [-1 * x for x in aX if x < 0  ]
    iLenPlus = len(aPlus)
    iLenMinus = len(aMinus)
    iLen0 = iN - iLenPlus - iLenMinus

    iCZero = 2**iLen0 - 1 #sum(k=1..N){nCk} = 2^n -1

    iRet = 0
    iRet += iCZero
    iCZero += 1 #0の場合を追加

    iSumPlus = sum(aPlus)
    iSumMinus = sum(aMinus)
    iUlim = min(iSumPlus , iSumMinus)
    iOlim = max(iSumPlus , iSumMinus)
    if 0 < iUlim:
        dp1 = [[0]*(iOlim +1) for _ in range(iLenPlus)]
        dp1[0][0] = 1
        dp1[0][aPlus[0]]=1
        for j in range(1,iLenPlus):
            for k in range(iUlim + 1):
                if k < aPlus[j] :
                    dp1[j][k] = dp1[j-1][k]
                else:
                    dp1[j][k] = dp1[j-1][k] + dp1[j-1][k-aPlus[j]]

        dp2 = [[0]*(iOlim +1) for _ in range(iLenMinus)]
        dp2[0][0] = 1
        dp2[0][aMinus[0]]=1
        for j in range(1,iLenMinus):
            for k in range(iUlim + 1):
                if k < aMinus[j] :
                    dp2[j][k] = dp2[j-1][k]
                else:
                    dp2[j][k] = dp2[j-1][k] + dp2[j-1][k-aMinus[j]]
        for i in range(1,iUlim+1):
            iRet += iCZero * dp1[-1][i] * dp2[-1][i]

    print(iRet)
解()

Submission status: Accepted

Solution code:

#人のすなるCounterなるものを我も書いてみんとてするなり
from collections import Counter

#方針 マイナスとプラスでDPを分割
iN,iA =[int(x) for x in input().split()]
aX = [int(x) - iA for x in input().split()]
aPlus = [x for x in aX if 0 < x ]
aMinus = [-1 * x for x in aX if x < 0  ]
iLenPlus = len(aPlus)
iLenMinus = len(aMinus)
iLen0 = iN - iLenPlus - iLenMinus
#0の場合はnCkの累積和なので別に計算する
#知ってたわけではなく解析しててみつけた
iCZero = 2**iLen0 - 1 #sum(k=1..N){nCk} = 2^n -1

iRet = 0
iRet += iCZero
iCZero += 1 #0の場合を追加

iUlim = min(sum(aPlus) , sum(aMinus))
if 0 < iUlim:
    dp1 = Counter([0,aPlus[0]])
    for i in range(1,iLenPlus):
        iThisX = aPlus[i]
        tmp = {}
        for k, v in dp1.items():
            tmp[iThisX + k] = v
        dp1 += tmp
    dp2 = Counter([0,aMinus[0]])
    for i in range(1,iLenMinus):
        iThisX = aMinus[i]
        tmp = {}
        for k, v in dp2.items():
            tmp[iThisX + k] = v
        dp2 += tmp
    for i in range(1,iUlim+1):
        iRet += iCZero * dp1[i] * dp2[i]
print(iRet)

Submission status: Accepted

Solution code:
#分割してみた。
#
iN,iA =[int(x) for x in input().split()]
aX = [int(x) - iA for x in input().split()]
aPlus = [x for x in aX if 0 < x ]
aMinus = [-1 * x for x in aX if x < 0  ]
iLenPlus = len(aPlus)
iLenMinus = len(aMinus)
iLen0 = iN - iLenPlus - iLenMinus

iCZero = 2**iLen0 - 1 #sum(k=1..N){nCk} = 2^n -1

iRet = 0
iRet += iCZero
iCZero += 1 #0の場合を追加

iSumPlus = sum(aPlus)
iSumMinus = sum(aMinus)
iUlim = min(iSumPlus , iSumMinus)
iOlim = max(iSumPlus , iSumMinus)
if 0 < iUlim:
    dp1 = [[0]*(iOlim +1) for _ in range(iLenPlus)]
    dp1[0][0] = 1
    dp1[0][aPlus[0]]=1
    for j in range(1,iLenPlus):
        for k in range(iUlim + 1):
            if k < aPlus[j] :
                dp1[j][k] = dp1[j-1][k]
            else:
                dp1[j][k] = dp1[j-1][k] + dp1[j-1][k-aPlus[j]]

    dp2 = [[0]*(iOlim +1) for _ in range(iLenMinus)]
    dp2[0][0] = 1
    dp2[0][aMinus[0]]=1
    for j in range(1,iLenMinus):
        for k in range(iUlim + 1):
            if k < aMinus[j] :
                dp2[j][k] = dp2[j-1][k]
            else:
                dp2[j][k] = dp2[j-1][k] + dp2[j-1][k-aMinus[j]]
    for i in range(1,iUlim+1):
        iRet += iCZero * dp1[-1][i] * dp2[-1][i]

print(iRet)

Submission status: Accepted

Solution code:
#分割してみた。これで通るかな？
iN,iA =[int(x) for x in input().split()]
aX = [int(x) - iA for x in input().split()]
aPlus = [x for x in aX if 0 < x ]
aMinus = [-1 * x for x in aX if x < 0  ]
iLenPlus = len(aPlus)
iLenMinus = len(aMinus)
iLen0 = iN - iLenPlus - iLenMinus

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


iCZero = 2**iLen0 - 1 #sum(k=1..N){nCk} = 2^n -1

iRet = 0
iRet += iCZero
iCZero += 1 #0の場合を追加

iSumPlus = sum(aPlus)
iSumMinus = sum(aMinus)
iUlim = min(iSumPlus , iSumMinus)
iOlim = max(iSumPlus , iSumMinus)
if 0 < iUlim:
    dp1 = [[0]*(iOlim +1) for _ in range(iLenPlus)]
    dp1[0][0] = 1
    dp1[0][aPlus[0]]=1
    for j in range(1,iLenPlus):
        for k in range(iUlim + 1):
            if k < aPlus[j] :
                dp1[j][k] = dp1[j-1][k]
            else:
                dp1[j][k] = dp1[j-1][k] + dp1[j-1][k-aPlus[j]]

    dp2 = [[0]*(iOlim +1) for _ in range(iLenMinus)]
    dp2[0][0] = 1
    dp2[0][aMinus[0]]=1
    for j in range(1,iLenMinus):
        for k in range(iUlim + 1):
            if k < aMinus[j] :
                dp2[j][k] = dp2[j-1][k]
            else:
                dp2[j][k] = dp2[j-1][k] + dp2[j-1][k-aMinus[j]]
    for i in range(1,iUlim+1):
        iRet += iCZero * dp1[-1][i] * dp2[-1][i]

print(iRet)

Submission status: Accepted

Solution code:
iN,iA =[int(x) for x in input().split()]
#aX = [int(x) - iA for x in input().split()]
aX = [int(x) for x in input().split()]

#解法1

iMX = max(aX + [iA])
dp = [[[0]*(iN*iMX + 1) for _ in range(iN+1)] for _ in range(iN + 1)]

dp[0][0][0] = 1
for j in range(1,iN+1):
#   for k in range(0,iN+1):
    for k in range(0,j+1):
#       for s in range(0,iN*iMX + 1):
        for s in range(0,j*iMX + 1):
            if  s < aX[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif k >= 1 and  s >= aX[j-1]:
                dp[j][k][s] = dp[j-1][k][s]+dp[j-1][k-1][s- aX[j-1]]
            else:
                dp[j][k][s] = 0
iRet = 0
for k in range(1,iN+1):
    iRet += dp[iN][k][k*iA]
print(iRet)

Submission status: Accepted

Solution code:
iN,iA =[int(x) for x in input().split()]
aX = [int(x) - iA for x in input().split()]

#解法2そのまま

iMX = max(aX + [iA])
iULim = iN*iMX
iULim2 = 2*iULim

#y0..yjから0枚以上選んだ合計をt-iN*iMXにするような選び方の総数
dp = [[0]*(iULim2 + 1) for _ in range(iN+1)]
for j in range(0,iN+1):
    for t in range(0,iULim2):
        if j == 0 and t == iULim :
            dp[j][t] = 1
        elif  t - aX[j-1] < 0 or t - aX[j-1] > iULim2:
            dp[j][t] = dp[j-1][t]
        elif  0 <= t - aX[j-1] <= iULim2:
            dp[j][t] = dp[j-1][t] + dp[j-1][t-aX[j-1]]
        else:
            dp[j][t] = 0
print(dp[iN][iN*iMX] -1 )

Submission status: Accepted

Solution code:
iN,iA =[int(x) for x in input().split()]
aX = [int(x) - iA for x in input().split()]

#解法2

iMX = max(aX + [iA])
dp = [[0]*(2 * iN*iMX + 1) for _ in range(iN+1)]

for j in range(0,iN+1):
    for t in range(0,2*iN*iMX):
        if j == 0 and t == iN * iMX :
            dp[j][t] = 1
        elif j >= 0 and ( t - aX[j-1] < 0 or t - aX[j-1] > 2*iN*iMX):
            dp[j][t] = dp[j-1][t]
        elif j >= 0 and ( 0 <= t - aX[j-1] <= 2*iN*iMX):
            dp[j][t] = dp[j-1][t] + dp[j-1][t-aX[j-1]]
        else:
            dp[j][t] = 0
print(dp[iN][iN*iMX] -1 )

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N, A = map(int, input().split())
    X = list(sorted(list(map(int, input().split()))))

    dp = [[0] * (50 * 50 + 2) for _ in range(52)]
    dp[0][0] = 1
    for i in range(N):
        x = X[i]
        for j in range(N, -1, -1):
            for k in range(len(dp[0])):
                if dp[j][k] != 0 and k + x < len(dp[0]):
                    dp[j + 1][k + x] += dp[j][k]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
Xmax = 50
for i in range(N):
  X[i] -= A
  
dp = [[0] * (2*N*Xmax +1) for i in range(N+1)]
#dp[i][j] : i枚目までで、和がj-N*Xmaxである通り数。
# initialize
dp[0][N*Xmax] = 1

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

#print(dp[N])
print(dp[N][N*Xmax]-1)

Submission status: Accepted

Solution code:
import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j-1]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
X = [int(_) for _ in input().split()]
for i in range(N): #総和のみを考えるために全体からAを引く
    X[i] -= A

def DP(i, n, memo = {}): #i番目までのカードを使って総和をnにする組合せの数
    if i == 1:
        return (1 if X[0] == n else 0)
    try:
        return memo[(i, n)]
    except KeyError:
        ans = DP(i-1, n, memo) + DP(i-1, n-X[i-1], memo)
        if n == X[i-1]:
            ans += 1
        memo[(i, n)] = ans
        return ans

memo = {}
print(DP(N, 0, memo))

Submission status: Accepted

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
b=sum(x)
ans=0
dp=[[0]*(b+1)for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for k in range(i+1,0,-1):
        for v in range(b,x[i]-1,-1):
            dp[k][v]+=dp[k-1][v-x[i]]
for k in range(1,n+1):
    if k*a>b:
        break
    ans+=dp[k][k*a]
print(ans)