Problem Description

Tak has N cards. On the i-th (1≤i≤N) card is written an integer xi. 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≤N≤50
1≤A≤50
1≤xi≤50
N,?A,?xi are integers

Partial Score

200 points will be awarded for passing the test set satisfying 1≤N≤16.

Input

The input is given from Standard Input in the following format:

N A
x1 x2 … xN

Output

Print the number of ways to select cards such that the average of the written integers is exactly A.

Example

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.

題意：有 n 張牌，每張牌有一個(gè)整數(shù) xi，現(xiàn)在要在 n 張牌里選 1 或多張，使得所選的牌的平均值是 A，問有多少種選擇方式

思路：

由于所給的數(shù)據(jù)范圍不大，因此可設(shè) dp[i][j] 為前 i 張卡上的數(shù)相加為 j 的方案數(shù)

那么首先枚舉?n 件物品，每次考慮使得取得的卡數(shù) i?減少 1 張，那么相應(yīng)的和的最大值有 j+x[k]，因此，對(duì)于前 i+1 張卡其相加的值為 j+x[k]，那么組成的方案數(shù) dp[i+1][j+x[k]] 就為原本的方案數(shù)再加上前 i 張卡的值，即：dp[i+1][j+x[k]]+=dp[i][j]

最后統(tǒng)計(jì)方案數(shù)即可

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 50+5; const int dx[] = {0,0,-1,1,-1,-1,1,1}; const int dy[] = {-1,1,0,0,-1,1,-1,1}; using namespace std; int x[N]; LL dp[N][N*N];//dp[i][j]表示前i個(gè)數(shù)相加值為j的方案數(shù) int main(){int n,a;scanf("%d%d",&n,&a);for(int i=1;i<=n;i++)scanf("%d",&x[i]);dp[0][0]=1;for(int k=1;k<=n;k++){//n個(gè)物品for(int i=k-1;i>=0;i--){//每次取得的物品個(gè)數(shù)減少for(int j=0;j<=50*i;j++){//統(tǒng)計(jì)相加的值，最大為50*idp[i+1][j+x[k]]+=dp[i][j];}}}LL res=0;for(int i=1;i<=n;i++){int val=i*a;//選擇i個(gè)物品時(shí)他們平均值的總和res+=dp[i][val];}printf("%lld\n",res);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的高橋君とカード / Tak and Cards（AtCoder-2037）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。