[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;
}