[ARC060A] 高橋君とカード / Tak and Cards

题面翻译

高桥有n张卡。在i(1≤i≤n)的第一个磁卡上，卡上面写着整数x_i。

高桥从这些卡片中挑选1张以上，想把选择的卡片上写的整数的平均数变成等于A的数。问有几种方案。

读入：第一行读入N,A；接下来一行读入N个数

输出：一个数，记得加回车

感谢@STEPHEN_ 提供的翻译

题目描述

高橋君は、 $ N $ 枚のカードを持っています。 $ i\ \,\ (1\ \leq\ i\ \leq\ N) $ 番目のカードには、整数 $ x_i $ が書かれています。高橋君は、これらのカードの中から $ 1 $ 枚以上を選び、選んだカードに書かれた整数の平均をちょうど $ A $ にしたいと考えています。そのようなカードの選び方が何通りあるか求めてください。

输入格式

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

 $ N $   $ A $ 
 $ x_1 $   $ x_2 $   $ ... $   $ x_N $

输出格式

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

样例 #1

样例输入 #1

4 8
7 9 8 9

样例输出 #1

样例 #2

样例输入 #2

8 5
3 6 2 8 7 6 5 9

样例输出 #2

样例 #3

样例输入 #3

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

样例输出 #3

8589934591

样例 #4

样例输入 #4

4 8
7 9 8 9

样例输出 #4

样例 #5

样例输入 #5

8 5
3 6 2 8 7 6 5 9

样例输出 #5

样例 #6

样例输入 #6

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

样例输出 #6

8589934591

提示

制約

$ 1\ \leq\ N\ \leq\ 50 $
$ 1\ \leq\ A\ \leq\ 50 $
$ 1\ \leq\ x_i\ \leq\ 50 $
$ N,\,A,\,x_i $ はいずれも整数である

部分点

$ 1\ \leq\ N\ \leq\ 16 $ を満たすデータセットに正解した場合は、 $ 200 $ 点が与えられる。

Problem Statement

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

Partial Score

$ 200 $ points will be awarded for passing the test set satisfying $ 1\ \leq\ N\ \leq\ 16 $ .

Sample Explanation 1

平均が $ 8 $ となるカードの選び方は、以下の $ 5 $ 通りです。
- $ 3 $ 枚目のカードのみを選ぶ。
- $ 1 $ 枚目と $ 2 $ 枚目のカードを選ぶ。
- $ 1 $ 枚目と $ 4 $ 枚目のカードを選ぶ。
- $ 1 $ 枚目、 $ 2 $ 枚目および $ 3 $ 枚目のカードを選ぶ。
- $ 1 $ 枚目、 $ 3 $ 枚目および $ 4 $ 枚目のカードを選ぶ。

Sample Explanation 4

答えは $ 32 $ ビット整数型に収まらない場合があります。

Sample Explanation 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 Explanation 8

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

一道十分典型的背包题

数组 dp[j][k] 表示选用j张牌，这j张牌上数字之和为k时的方法总数

所以动态转移方程就是 dp[j][k]+=dp[j-1][k-x]

最后的答案就是选用 $i$ $(1\leq i\leq N)$ 张牌且数字之和为 $i*A$ 时的方法总和

记得要 long long！！！

#include <cstdio>
#include <iostream>
using namespace std;
long long N, A, x;
long long dp[300][8000], ans;
int main() {
    dp[0][0] = 1;
    scanf("
    for (int i = 1; i <= N; i++) {
        scanf("
        for (int j = i; j > 0; j--) {
            for (int k = A * N; k >= x; k--) {
                dp[j][k] += dp[j - 1][k - x];
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        ans += dp[i][i * A];
    }
    printf("
    return 0;
}