고교군과 카쿠/Tak and Cards(dp)

Time limit : 2sec/ Memory limit : 256MB
Score : 300 points

Problem Statement

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.

Sample Input 1

Copy

4 8
7 9 8 9

Sample Output 1

Copy

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

Copy

3 8
6 6 9

Sample Output 2

Copy

0

Sample Input 3

Copy

8 5
3 6 2 8 7 6 5 9

Sample Output 3

Copy

19

Sample Input 4

Copy

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

Copy

8589934591

 

The answer may not fit into a 32-bit integer.

o# 아이디어 전재
 
제목: n개의 숫자를 주고 이 n개의 숫자 평균수가 a인 조합수를 구하세요.
사고방식: 처음으로atcoder를 쳤는데 이 문제는 두 가지로 나뉘어 풀고 완전히 풀었다.부분 해제 요구 n<=16, 완전 해제 n<=50.
부분해의 방법은 매우 간단하다. 모든 자집을 매거하여 조건에 부합되는지 확인하면 된다.
가방으로 해야 한다는 것을 완전히 풀고 dp(i, j, k)를 설정하여 i번째 숫자 앞에서 j개와 k의 모든 조합 수를 선택한다.왜냐하면 우리는 평균수의 계산 방법이Σxi/X, a= 설정Σxi/X, a*X=Σxi.우리는 마지막으로 모든 dp(n, X, a*X)만 통계하면 된다.
옮기면 우선 계수는 이전의 결과를 현재의 결과로 옮기고 dp(i, j, k)+=dp(i-1, j, k).다음은 가방입니다. dp(i,j,k)+=dp(i-1,j-1,k-x(i-1)))|{k>=x(i-1)}
 
코드는 자기가 쳤어요.
 

#include 
#include 
typedef long long ll;
using namespace std;

ll dp[55][55][2551];

int main()
{
    int x[2550],n,a,i,j,k;

    cin>>n>>a;
    for(i=0;i>x[i];

    dp[0][0][0]=1;

    for(i=1;i<=n;i++)
    {
        for(j=i;j>=0;j--)
        {
            for(k=a*n+1;k>=0;k--)
            {
                dp[i][j][k]+=dp[i-1][j][k];
                if(k>=x[i-1] && j>=1)
                    dp[i][j][k]+=dp[i-1][j-1][k-x[i-1]];
            }
        }
    }
    ll ans=0;

    for(i=1;i<=n;i++)ans+=(dp[n][i][i*a]);

    cout<