我爱小数据！

思路

注意到$n\leq 50$，好开心！考虑直接使用DP，定义$f_{i,j,k}$为前$i$个卡片中选中$j$个和为$k$的方案数，转移方程如下：

然后直接暴力就好了，复杂度$O(n^4)$，比kevin少一维。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=55;
int f[N][N][N*N],a[N],s[N],n,A;
signed main()
{
	scanf("%lld%lld",&n,&A);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
	for(int i=0;i<=n;i++)f[i][0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			for(int k=0;k<a[i];k++)
			{
				f[i][j][k]=f[i-1][j][k];
			}
			for(int k=a[i];k<=s[i];k++)
			{
				f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k-a[i]];
			}
		}
	}
	int ans=0;
	for(int i=1;i*A<=s[n]&&i<=n;i++)ans+=f[n][i][i*A];
	printf("%lld\n",ans);
	return 0;
}

看到数据大小N<=50，我们就可以直接暴力DP

用dp[i][j]来表示当前选了i个，它们的总和为j的方案数，所以转移方程为：

最后答案是

因为选了i个数，其总和为i*A，它的平均数才是A

然后实现即可，时间复杂度为$O(n^4)$，比kevin少一层......

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[100],A,ans=0,dp[60][2610];
int main()
{
	scanf("%lld%lld",&n,&A);
	for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	dp[0][0]=1;
	for(ll i=1;i<=n;i++)
		for(ll j=2500;j>=a[i];j--)
			for(ll k=1;k<=n;k++)
				dp[k][j]+=dp[k-1][j-a[i]];
	for(ll i=1;i<=n;i++)ans+=dp[i][i*A];
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define N 50
#define int long long
int s,ans,a[N+5],f[N+5][N*N+5];
//f[i][j]表示用i张卡片凑出j有多少种情况 
signed main()
{
	int n,m;scanf("%lld%lld",&n,&m);f[0][0]=1;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),s+=a[i];
	for(int i=1;i<=n;i++)for(int j=s;j>=a[i];j--)
		for(int k=1;k<=n;k++)f[k][j]+=f[k-1][j-a[i]];
	for(int i=1;i<=n;i++)ans+=f[i][i*m];
	printf("%lld\n",ans);return 0;
}

良心提示：本题的数据范围足够使用 $O(N^5)$ 的时间复杂度。

这题看到数据直接一眼了。平均数不好求，所以我们直接把这个问题转化成如下问题：对于每个 $k \in [1,n]$，从 $a$ 中选取 $k$ 个数的总价值为 $k*A$ 的方案数，很明显直接背包。再根据 $a_i$ 的范围，时间复杂度为 $O(N^5)$。

我这里用了滚动数组优化，其实也可以不用。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=60;
int dp[N][N*N],dp1[N][N*N],n,p,a[N],sum;
int solve(int x)
{
	memset(dp,0,sizeof(dp));dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<x;j++)
			for(int k=0;k<=x*p-a[i];k++)
				dp1[j+1][k+a[i]]+=dp[j][k];
		for(int i=0;i<=x;i++)for(int j=0;j<=x*p;j++)dp[i][j]+=dp1[i][j],dp1[i][j]=0;
	}
	return dp[x][x*p];
}
signed main()
{
	cin>>n>>p;
	for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
	int ans=0;
	for(int i=1;i<=n&&i*p<=sum;i++)ans+=solve(i);
	cout<<ans;
	return 0;
}