AtCoder Beginner Contest 044 C - 高橋君とカード / Tak and Cards

时间：2023-01-01 05:01:44

题目链接：http://abc044.contest.atcoder.jp/tasks/arc060_a

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

题意：给定一串数字，问能够组成多少种不连续子串使得子串的平均数为某个数

题解：用动态规划，i表示相加的个数，j表示加起来后的值

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cstdlib>

 #include <iomanip>

 #include <cmath>

 #include <ctime>

 #include <map>

 #include <set>

 #include <queue>

 using namespace std;

 #define lowbit(x) (x&(-x))

 #define max(x,y) (x>y?x:y)

 #define min(x,y) (x<y?x:y)

 #define MAX 100000000000000000

 #define MOD 1000000007

 #define pi acos(-1.0)

 #define ei exp(1)

 #define PI 3.141592653589793238462

 #define INF 0x3f3f3f3f3f

 #define mem(a) (memset(a,0,sizeof(a)))

 typedef long long ll;

 ll gcd(ll a,ll b){

     return b?gcd(b,a%b):a;

 }

 bool cmp(int x,int y)

 {

     return x>y;

 }

 const int N=;

 const int mod=1e9+;

 ll dp[N][N*N];

 int main()

 {

     int n,a;

     cin>>n>>a;

     dp[][]=;

     for(int i=;i<=n;i++){

         int x;

         cin>>x;

         for(int j=i-;j>=;j--)

             for(int k=;k<=N*j;k++)

                 dp[j+][k+x]+=dp[j][k];

     }

     ll ans=;

     for(int i=;i<=n;i++)

         ans+=dp[i][i*a];

     cout<<ans<<endl;

     return ;

 }

相关文章