[ABC044C] Tak and Cards 题解

题目链接：[ABC044C] Tak and Cards

题意：

高桥君有 $N$ 张不同的卡片，还有一个整数 $A$ ，第 $i$ 张卡片上写着整数 $x_i$。

现在要从中选出若干张卡片，使得它们上面写的数的平均值为 $A$。求合法的选择方案数。

卡片相同而顺序不同的，视作同一种方案。

保证输入的数均是不大于 $50$ 的正整数。

设 $f(i,j,k)$ 表示前 $i$ 个数选了 $j$ 个且和为 $k$ 时的方案数，则

$$f(i,j,k) = f(i - 1, j, k) + f(i - 1, j - 1, k - x_i)$$

每次转移都从 $i-1$ 到 $i$ ，且 $j,k$ 倒序枚举不会转移错误，因此考虑滚动数组。

然后我们只需要枚举所有合法的 $(j,k)$ ，加上他们的答案就好啦~

时间复杂度 $\mathcal{O}(n^4)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(55))

const int _ = 2550;
int n,m,res,a[N],f[N][N * N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = _; j >= a[i]; j--)
            for(int k = n; k; k--) f[k][j] += f[k - 1][j - a[i]];
    for(int i = 1; i <= n; i++)
        for(int j = _; ~j; j--) res += (m * i == j) * f[i][j];
    cout << res << '\n';
    return 0;
}