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

max_of_a = N * A

# dp[i][j][k] := i枚目までからj枚取って、合計をkにする通り数
dp = [[[0] * (max_of_a + 1) for _ in range(N+1)]for _ in range(N+1)]
dp[0][0][0] = 1


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

ans = 0
for j in range(1, N+1):
    # N枚(カード総数)の中から1枚以上取った時の、j枚取って合計がj*Aの所 の合計
    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()))
X = sum(x)

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, A, *x = map(int, open(0).read().split())
    MAX_A_x = max(A, max(x))
    x = [xi - A for xi in x]
    # dp[i][j]
    # i 選んだ枚数 0 <= i <= N
    # j 合計 0 <= j <= 2 * N * MAX_A_x
    dp = [[0] * (2 * N * MAX_A_x + 1) for i in range(N + 1)]
    dp[0][N * MAX_A_x] = 1
    for i in range(1, N + 1):
        for j in range(2 * N * MAX_A_x + 1):
            if j - x[i - 1] < 0 or 2 * N * MAX_A_x < j - x[i - 1]:
                dp[i][j] = dp[i - 1][j]
            elif 0 <= j - x[i - 1] <= 2 * N * MAX_A_x:
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - x[i - 1]]
            else:
                dp[i][j] = 0
    print(dp[N][N * MAX_A_x] - 1)
    return


main()

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
# 予め-Kした状態で用意しておく
A = [a-K for a in LIST()]

MAX = N * K * 2
# dp[i][k] := i枚目までのカードで、合計をkにする通り数
dp = list2d(N+1, MAX+1, 0)
# 負の数を考慮して、N*K位置を0とする
dp[0][N*K] = 1
for i in range(N):
    a = A[i]
    for k in range(MAX+1):
        dp[i+1][k] += dp[i][k]
        if 0 <= k+a <= MAX:
            dp[i+1][k+a] += dp[i][k]
# N回終わって合計が0になっている通り数 - 1枚も取らないケース
print(dp[N][N*K]-1)

Submission status: Accepted

Solution code:
def solve():
    def recur(i, n, total):
        # print("i, n, total", i, n, total)

        if not TABLE[i][n][total] == -1:
            return TABLE[i][n][total]

        if not i < N:
            if n > 0 and total == A * n:
                TABLE[i][n][total] = 1
                return TABLE[i][n][total]

            TABLE[i][n][total] = 0
            return TABLE[i][n][total]

        ans1 = recur(i + 1, n, total)
        ans2 = recur(i + 1, n + 1, total + XS[i])

        # print(ans1, ans2)

        TABLE[i][n][total] = ans1 + ans2
        return TABLE[i][n][total]

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

    TABLE = []
    for _ in range(N + 1):
        lines = [[-1 for x in range(N * 50 + 1)] for y in range(N + 1)]
        TABLE.append(lines)

    return recur(0, 0, 0)


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

Submission status: Accepted

Solution code:
def solve():
    def recur(i, n, total):
        # print("i, n, total", i, n, total)

        if not TABLE[i][n][total] == -1:
            # print('cache!')
            return TABLE[i][n][total]

        if not i < N:
            if n > 0 and total == A * n:
                return 1
            return 0

        ans1 = recur(i + 1, n, total)
        ans2 = recur(i + 1, n + 1, total + XS[i])

        # print(ans1, ans2)

        TABLE[i][n][total] = ans1 + ans2
        return TABLE[i][n][total]

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

    TABLE = []
    for _ in range(N + 1):
        lines = [[-1 for x in range(N * 50 + 1)] for y in range(N + 1)]
        TABLE.append(lines)

    return recur(0, 0, 0)


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
# dp[j][t]=(y1,...,yj から 0 枚以上選んで yi の合計を t − 1250 にするような選び方の総数)

def solve(N: int, A: int, x: "List[int]"):
    x = [x[i]-A for i in range(N)]
    dp = [[0]*2500 for _ in range(N+1)]
    dp[0][1250] = 1

    for j in range(1,N+1):
        for t in range(2500):
            if t-x[j-1]>=0 and t-x[j-1]<2500:
                dp[j][t] = dp[j-1][t] + dp[j-1][t-x[j-1]]
            else:
                dp[j][t] = dp[j-1][t]
    print(dp[N][1250]-1)
    
    return

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np


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


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

Submission status: Accepted

Solution code:
import numpy as np


def main(n, a, x):
    SUM_MAX = max(a, max(x)) * n + 1
    dp = np.zeros(shape=(n + 1, n + 1, SUM_MAX), dtype=int)

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

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


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

Submission status: Accepted

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

def Count(n,k,a):
	s = sum(x)
	dp=[[[0 for l in range(s+1)] for j in range(k+1)] for i in range(n+1)]
	dp[0][0][0]=1
	Sum=0
	for i in range(n):
		for j in range(k+1):
			for l in range(s+1):
				if l < x[i]:
					dp[i+1][j][l] = dp[i][j][l]
				if j >=1 and l >= x[i]:
					dp[i+1][j][l] = dp[i][j][l] + dp[i][j-1][l-x[i]]
				if j <= i+1 and l ==j*a and j >= 1:
					if dp[i+1][j][l]>=1:	
						Sum += dp[i+1][j][l]-dp[i][j][l]
	return Sum

print(Count(n,n,a))

Submission status: Accepted

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

    mx = max(x + [a])

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

    sm = 2 * n * mx

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

    dp[0][n*mx] = 1

    for i, e in enumerate(x, 1):
        for j in range(sm + 1):
            if 0 <= j - e <= sm:
                dp[i][j] = dp[i-1][j] + dp[i-1][j-e]
            else:
                dp[i][j] = dp[i-1][j]

    ans = dp[n][n*mx] - 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def main():
    n, a = map(int, input().split())
    x = tuple(map(int, input().split()))

    sm_mx = sum(x)

    dp = [[[0] * (sm_mx + 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(n + 1):
            for sm in range(sum(x[:i]) + 1):
                if sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 全DP C - 高橋君とカード / Tak and Cards

import numpy as np

N, A = map(int, input().split())
x = np.array(list(map(int, input().split())))

x_diff = x - np.array(A)
X = max(A, max(x))

dp = np.zeros((N+2, 2*N*X+2)) #dp[i+1][j]はx_diff[i]までの数からいくつか選んで合計j-N*Xにするような選び方のパターン
dp = dp.tolist()
dp[0][N*X] = 1

for i in range(N):
    for j in range(2*N*X+1):
        if j < x_diff[i] or x_diff[i] < j - 2*N*X: # x_diff[i]を足しても絶対にj-N*Xにならないとき
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = dp[i][j] + dp[i][j-x_diff[i]]
            
print(int(dp[N][N*X] - 1))

Submission status: Accepted

Solution code:

n,k = map(int,input().split())
A = list(map(int,input().split()))
dic1 = {(0,0):1}
for i in range(n):
    dic2 = {(0,0):0}
    for (total,num),amount in dic1.items():
        if (total,num) in dic2:
            dic2[(total,num)] += amount
        else:
            dic2[(total,num)] = amount
        if (total+A[i],num+1) in dic2:
            dic2[(total+A[i],num+1)] += amount
        else:
            dic2[(total+A[i],num+1)] = amount
    
    dic1 = dic2

ans = 0
for i in range(1,n+1):
    if (i*k,i) in dic1:
        ans += dic1[(i*k,i)]

print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
l=[int(i) for i in input().split()]
dp = [[[0 for k in range(55)] for j in range(3000)] for i in range(55)]

for i in range(n+1):
    dp[i][0][0]=1 
sm=sum(l)
for i in range(1,n+1):
    for j in range(sm+5):
        for k in range(1,n+1):
            curr=l[i-1]
            if curr<=j:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-curr][k-1]
            else:
                dp[i][j][k]=dp[i-1][j][k]

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

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = list(map(lambda x: int(x) - a, input().split()))
d = {0: 1}
for i in x:
    for j, k in list(d.items()):
        d[i + j] = d.get(i + j, 0) + k
ans = d[0] - 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

X, A = map(int, input().split())
x = [i - A for i in map(int, input().split())]
x.sort()
dp = Counter()

for i in x:
    for j, k in list(dp.items()):
        dp[j + i] = dp[j + i] + k
    dp[i] += 1

print(dp[0])

Submission status: Accepted

Solution code:
import collections

n, a = map(int, input().split())
ls = sorted([x - a for x in map(int, input().split())])
counter = collections.Counter()
for x in ls:
    for k, v in list(counter.items()):
        counter[k + x] = counter[k + x] + v
    counter[x] += 1
print(counter[0])

Submission status: Accepted

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

# dp[i][j][k] i枚までj枚えらんで合計k
# 答えはdp[n][1..n][a..ak]
dp = [[[0] * 2700 for _ in range(52)]
      for __ in range(52)]

dp[0][0][0] = 1
for i in range(0, n):
    for j in range(0, n + 1):
        for k in range(n * max(X) + 1):
            dp[i + 1][j][k] += dp[i][j][k]  # 選ぶ
            dp[i + 1][j + 1][k + X[i]] += dp[i][j][k]  # 選ばない

ans = 0
for i in range(1, n+1):
    for j in range(a, 2501):
        if i * a == j:
            ans += dp[n][i][j]
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]
LMT = max(max(X), A)

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

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

mx = 0
for i in range(n):
    mx += abs(x[i])
mx +=1

dp = [[0 for i in range(3*mx)] for j in range(n)]
dp[0][0] += 1
dp[0][x[0]] += 1

for i in range(1,n) :
    for j in range(-mx,mx):
        dp[i][j] += dp[i-1][j-x[i]]
        dp[i][j] += dp[i-1][j]
    #print(*dp[i])
print(dp[n-1][0]-1)

Submission status: Accepted

Solution code:
n, a = map(int, input().split())
x = [0] + list(map(int, input().split()))
nx = 2501

# DP: x1からxjまでの間でk枚を選んで合計がsになる組み合わせの数
dp = [ [ [0 for s in range(nx+1)] for k in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 1

for j in range(1, n+1):
    for k in range(n+1):
        for s in range(nx+1):
            if x[j] > s:
                dp[j][k][s] = dp[j-1][k][s]
            elif k >= 1:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j]]
#print(dp)
ans = 0
for k in range(1, n+1):
    ans += dp[-1][k][a * k]

print(ans)

Submission status: Accepted

Solution code:
def f(n,x,i):
    if n == 0:
        if x != 0:
            if x / i == a:
                return 1
        return 0
    if memo[i][n][x] != -1:
        return memo[i][n][x]
    memo[i][n][x] = f(n-1,x,i)+f(n-1,x+ary[n-1],i+1)
    return memo[i][n][x]
n,a = map(int,input().split())
ary = list(map(int,input().split()))
memo = [[[-1 for _ in range(sum(ary)+1)] for _ in range(n+1)] for _ in range(n+1)]
print(f(n,0,0))

Submission status: Accepted

Solution code:
N,A = [int(x) for x in input().split()]
x = [int(x) for x in input().split()]
X = max(x+[A])
#%%
dp = [[[-1]*(N*X+1) for _ in range(N+1)] for _ in range(N+1)]

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

ans = 0
for k in range(1,N+1):
    ans += rep(N,k,k*A)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n, a = LI()
L = LI()
L = [i - a for i in L]
dp = defaultdict(int)
dp[0] = 1
for i in range(n):
    if L[i] <= 0:
        for j in range(-2500, 2501):
            dp[j] += dp[j - L[i]]
    else:
        for j in range(2500, -2501, -1):
            dp[j] += dp[j - L[i]]


print(dp[0] - 1)

Submission status: Accepted

Solution code:
inp=input().split(" ")
N=int(inp[0])
A=int(inp[1])
x=list(map(int, input().split(" ")))
y=[x[i]-A for i in range(N)]
y=[0]+y
X=max(x)
dp=[[0 for i 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 and (t-y[j]<0 or t-y[j]>2*X*N):
            dp[j][t]=dp[j-1][t]
        elif j>=1 and 0<=t-y[j] 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:
n, a = map(int, input().split(" "))
list_x = [int(x) - a for x in input().split(" ")]
counts = [{} for i in range(n + 1)]
counts[0][0] = 1
for i, x in enumerate(list_x):
  for v in counts[i]:
    c = counts[i][v]
    if v not in counts[i + 1]:
      counts[i + 1][v] = 0
    counts[i + 1][v] += c
    if v + x not in counts[i + 1]:
      counts[i + 1][v + x] = 0
    counts[i + 1][v + x] += c
print(counts[n][0] - 1)

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

def main():
    N, A = map(int, input().split())
    x = np.array(list(map(int, input().split())))
    X = max(A, max(x))
    x -= A
    # print(x)
    dp = np.zeros((N+1, 2*N*X+1), dtype=int)
    # 初期化
    dp[0][N*X] = 1
    for i in range(N):
        dp[i+1] += dp[i]
        if x[i] > 0:
            dp[i+1][x[i]:] += dp[i][:-x[i]]
        elif x[i] < 0:
            dp[i+1][:x[i]] += dp[i][-x[i]:]
        else:
            dp[i+1] += dp[i]
    
    # print(dp[:, N*X-5:N*X+5])
    # print(x)
    print(dp[-1][N*X] - 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, A = map(int, input().split())  # N枚数のカード, 平均をAにしたい
X = tuple(map(int, input().split()))  # N枚のカードの中身

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

dp[0][0][0] = 1  # 0枚の中から0枚選んで合計が0になる選び方が1通りある

for i in range(N):
    for j in range(N+1):
        for k in range(50*N+1):
            if dp[i][j][k]:  # ここの分岐が分からん
                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][i*A]
print(ans)

Submission status: Accepted

Solution code:
N, A = map(int, input().split())  # N枚数のカード, 平均をAにしたい
X = tuple(map(int, input().split()))  # N枚のカードの中身

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

dp[0][0][0] = 1  # 0枚の中から0枚選んで合計が0になる選び方が1通りある

for i in range(N):
    for j in range(N+1):
        for k in range(50*N+1):
            if dp[i][j][k]:  # そのパターン数が0になっている場所からの遷移はありえない！！！
                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][i*A]
print(ans)

Submission status: Accepted

Solution code:
# ABC044C - 高橋君とカード / Tak and Cards (ARC060C)
def main():
    N, A, *X = map(int, open(0).read().split())
    X, D = [i - A for i in X], {0: 1}
    for i in X:
        for j, k in list(D.items()):
            D[i + j] = D.get(i + j, 0) + k
    ans = D[0] - 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC044C - 高橋君とカード / Tak and Cards (ARC060C)
from collections import defaultdict


def main():
    N, A, *X = map(int, open(0).read().split())
    X, D = [i - A for i in X], defaultdict(int)
    D[0] = 1
    for i in X:
        for j, k in list(D.items()):
            D[i + j] += k
    ans = D[0] - 1
    print(ans)
    


if __name__ == "__main__":
    main()

Submission status: Accepted

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

X.sort()
ii = 0
while ii < n and X[ii] < a:
    ii += 1
jj = ii
while jj < n and X[jj] == a:
    jj += 1

aa = jj-ii
A = [[a-i for i in X[:ii]], [j-a for j in X[jj:]]]

# print(A)

mm = min(sum(A[0]), sum(A[1]))

AA = [[0] * (mm + 1) for i in range(2)]
for k in range(2):
    AA[k][0] = 1
    for i in range(len(A[k])):
        for j in range(len(AA[k])-1, -1, -1):
            if j - A[k][i] >= 0:
                AA[k][j] += AA[k][j-A[k][i]]
                # print(AA)
                # print(k, j, A[k][i])


# print(AA,aa)
ans = 0
for i in range(1, mm + 1):
    ans += AA[0][i] * AA[1][i]
# print(ans)
ans *= 2 ** aa

print(ans + (2 ** aa - 1))

Submission status: Accepted

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

"""
普通にやると最大で2**50通りなのでTLE
i枚選んだ時に合計がi*Aになる物を考えるとよい
prd_xxxさんの解答に自分向けのコメントつけただけ
https://atcoder.jp/contests/abc044/submissions/3018277
"""

# 0枚からN枚まで選んで、合計値がkeyでその組み合わせの数がvalue
dp = [Counter() for _ in range(N+1)]
dp[0][0] = 1

for i, a in enumerate(X): # i番目のカードまで選べる
    for j in reversed(range(i+1)): # j枚選ぶとき（０～i枚の範囲）、逆順にしないと１枚目にX_iを選んで３枚目にもX_iを選ぶみたいな重複が発生するのでこれを回避するために逆順にする
        for k,v in dp[j].items(): # j枚選んだ時の合計値とその組み合わせの個数についてみていく
            dp[j+1][k+a] += v # j+1枚目としてi番目のカードを選ぶ時に合計がk+aになる個数は、j枚選んでｋになる個数と同じ（それぞれの場合にaを足してできる）

ans = 0
for i, C in enumerate(dp):
    if i >= 1:
        ans += C[i*A]
print(ans)

Submission status: Accepted

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

"""
普通にやると最大で2**50通りなのでTLE
i枚選んだ時に合計がi*Aになる物を考えるとよい

"""

# 0枚からN枚まで選んで、合計値がkeyでその組み合わせの数がvalue
dp = [Counter() for _ in range(N+1)]
dp[0][0] = 1

for i, a in enumerate(X): # i番目のカードまで選べる
    for j in reversed(range(i+1)): # j枚選ぶとき（０～i枚の範囲）、逆順にしないと１枚目にX_iを選んで３枚目にもX_iを選ぶみたいな重複が発生するのでこれを回避するために逆順にする
        for k,v in dp[j].items(): # j枚選んだ時の合計値とその組み合わせの個数についてみていく
            dp[j+1][k+a] += v # j+1枚目としてi番目のカードを選ぶ時に合計がk+aになる個数は、j枚選んでｋになる個数と同じ（それぞれの場合にaを足してできる）

ans = 0
for i, C in enumerate(dp):
    if i >= 1:
        ans += C[i*A]
print(ans)

Submission status: Accepted

Solution code:
n,*x=map(int,open(0).read().split());y=[x[0]-i for i in x];m=n*max(x);d=[[0]*m*2 for _ in[0]*-~n];d[0][0]=1
for i in range(1,n+1):
	for s in range(-m,m):d[i][s]=d[i-1][s]+d[i-1][s-y[i]]
print(d[n][0]-1)

Submission status: Accepted

Solution code:
n,*x=map(int,open(0).read().split())
y=[x[0]-i for i in x]
m=n*max(x)
dp=[[0]*(m*2+1) for _ in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
	for s in range(-m,m):
		dp[i][s]=dp[i-1][s]+dp[i-1][s-y[i]]
print(dp[n][0]-1)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,A = inpl()
x = inpl()
nx = n * max(max(x),A)
dp = [[[0 for _ in range(n+5)] for i in range(nx+1)] for j in range(n+5)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(nx+1):
        for k in range(n):
            if j >= x[i]:
                dp[i+1][j][k+1] = dp[i][j-x[i]][k] + dp[i][j][k+1]
            else:
                dp[i+1][j][k] = dp[i][j][k]

ans = 0
for j in range(1,nx+1):
    for k in range(1,n+1):
        if j/k == A:
            ans += dp[n][j][k]
print(ans)

Submission status: Accepted

Solution code:

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

lis = []

for i in range(51):
    lis.append([0] * 2501)

lis[0][0] = 1

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


for x in X:

    nlis = []
    for k in range(51):
        new = lis[k].copy()
        nlis.append(new)

    for i in range(51):

        for j in range(2501):

            if i+1 <= 50 and j+x <= 2500 and nlis[i][j] > 0:

                lis[i+1][j+x] += nlis[i][j]

ans = 0
for i in range(51):

    for j in range(2501):

        if i != 0 and j % i == 0 and j // i == A:
            #print (i,j,lis[i][j])
            ans += lis[i][j]

print (ans)

Submission status: Accepted

Solution code:
n,a =map(int,input().split())
X=list(map(int,input().split()))
X=list(map(lambda x:x-a, X))
dp={0:1}
for i in X:
  for k,v in list(dp.items()):
    dp[i+k]=dp.get(i+k,0)+v
print(dp[0]-1)

Submission status: Accepted

Solution code:
def f(n,x,i):
    if n == 0:
        if i != 0:
            if x/i == m:
                return 1
        return 0
    if memo[n-1][i][x] != -1 :
        return memo[n-1][i][x]
    memo[n-1][i][x] = f(n-1,x,i)+f(n-1,x+a[n-1],i+1)
    return memo[n-1][i][x]

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

Submission status: Accepted

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

dp = [defaultdict(int) for i in range(n+1)]
dp[0][0] = 1

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

# for dp_i  in dp:
#     print(dp_i)

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

Submission status: Accepted

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

X = max(x + [A])

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
N,A = map(int,input().split())
X = [int(x) for x in input().split()]
dp = np.zeros((N+1,3000),dtype=np.int64) # 枚数、目標数ごとに場合の数
dp[0,0] = 1

for x in X:
  dp[1:,x:] += dp[:-1,:-x].copy()
  
answer = 0
for n in range(1,N+1):
  answer += dp[n,n*A]
  
print(answer)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, a = na()
x = na()
x = [0] + x
dp = [[[0] * (50 * n + 1) for i in range(n+1)] for j in range(n+1)]

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

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
xs = list(map(int, input().split()))
dp = [{} for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
  x = xs[i]-A
  for s in dp[i]:
    n = dp[i][s]
    if s not in dp[i+1]: dp[i+1][s] = 0
    dp[i+1][s] += n
    if s+x not in dp[i+1]: dp[i+1][s+x] = 0
    dp[i+1][s+x] += n
r = dp[N][0]-1
print(r)

Submission status: Accepted

Solution code:
def main():
    N,A = map(int,input().split())
    X = [int(x) for x in input().split()]
    dp = [[[0 for _ in range(2501)] for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0][0] = 1
    for j in range(N):
        now = X[j]
        for k in range(N+1):
            for s in range(2501):
                if now>s:
                    dp[j+1][k][s] = dp[j][k][s]
                else:
                    dp[j+1][k][s] = dp[j][k][s] + dp[j][k-1][s-now]
    ans = 0

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

            

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
# ABC044C - 高橋君とカード / Tak and Cards (ARC060C)
def main():
    N, A = tuple(map(int, input().split()))
    X = tuple(map(lambda x: int(x) - A, input().split()))
    D = {0: 1}
    for i in X:
        for j, k in list(D.items()):
            D[i + j] = D.get(i + j, 0) + k
    ans = D[0] - 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

print(dp(0, []))

Submission status: Accepted

Solution code:
N, A = map(int, input().split())
x = [int(i) for i in input().split()]
DP = [[[0] * (2501) for i in range(N+1)] for j in range(N+1)]
ans = 0
DP[0][0][0] = 1

for i in range(N):
  for j in range(N):
    for k in range(2501):
      if DP[i][j][k]:
        DP[i+1][j+1][k+x[i]] += DP[i][j][k]
        DP[i+1][j][k] += DP[i][j][k]
for i in range(N):
  ans += DP[N][i+1][(i+1)*A]
print(ans)

Submission status: Accepted

Solution code:
MAX_X = 50
n, a = map(int, input().split())
x = list(map(int, input().split()))
dp = [[[0] * (MAX_X * n + 1) for i in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n):
    for k in range(n):
        for j in range(MAX_X * n + 1):
            if j >= x[i]:
                dp[i + 1][k + 1][j] = dp[i][k + 1][j] + dp[i][k][j - x[i]]
            else:
                dp[i + 1][k][j] = dp[i][k][j]
ans = 0
for p in range(1, n + 1):
    ans += dp[n][p][a * p]
print(ans)

Submission status: Accepted

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

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