題意
https://vjudge.net/problem/AtCoder-2037
選一些數使得和的平均值等于a，問方案數，
思路
設dp[i][j]為選i個數和為j的方案數，如果當前選了x，那么dp[j+1][w+x]+=dp[j][w]，
令dp[0][0]=1，注意倒序遍歷j
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=55;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
ll dp[N][N*N];
int main()
{
std::ios::sync_with_stdio(false);
int n,a;
cin>>n>>a;
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
for(int j=i-1;j>=0;j--)
for(int w=0;w<=N*j;w++)
{
dp[j+1][w+x]+=dp[j][w];
// cout<<j+1<<" "<<w+x<<" "<<dp[j+1][w+x]<<endl;
}
}
ll ans=0;
for(int i=1;i<=n;i++)
{
ans+=dp[i][i*a];
}
cout<<ans<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/127160.html
標籤：其他