abc044C Tak and Cards

有N张卡片，第i张卡片上的数字为x[i]，可以从中选择1张或多张卡片，要求平均数为A，求方案数。
1<=N<=50; 1<=A<=50; 1<=x[i]<=50

分析：由于N最大为50，dfs搜索会超时，考虑dp。记dp[i][j][k]表示前i张卡片中选择了j张，并且和为k，根据每张卡片选与不选进行递推。

#include <bits/stdc++.h>
using i64 = long long;

i64 dp[51][51][2501];

void solve() {
	int N, A;
	std::cin >> N >> A;
	std::vector<int> X(N + 1);
	for (int i = 1; i <= N; i++) {
		std::cin >> X[i];
	}
	for (int i = 0; i <= N; i++) {
		dp[i][0][0] = 1;
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			for (int k = 1; k <= 2500; k++) {
				dp[i][j][k] = dp[i - 1][j][k];
				if (k >= X[i]) {
					dp[i][j][k] += dp[i - 1][j - 1][k - X[i]];
				}
			}
		}
	}

	i64 ans = 0;
	for (int i = 1; i <= N; i++) {
		ans += dp[N][i][i * A];
	}
	std::cout << ans << "\n";
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	int t = 1;
	while (t--) solve();
	return 0;
}