「解题报告」[ARC104D] Multiset Mean
K8He
·
·
题解
[ARC104D] Multiset Mean
感觉翻译的歧义好大，那先把题面翻译成人话：
给定 n,k 和 m。对于每个大小在 [1, n] 中的 x，求每个元素大小在 [1, n] 中，平均数为 x 且相同元素不超过 k 个的可重集的数量，对 m 取模。
题意有个很厉害的转化：整体减去 x。也就是说原来我们可以选的数是 1\sim n，现在选的是 1 - x\sim n - x。
这个时候可选的部分变为了 [1 - x, -1], 0 和 [1, n - x] 三个部分。0 随便选，有 k + 1 种方案。然后要求在 [1 - x, -1] 中和在 [1, n - x] 中选的元素之和相加为零，考虑背包预处理。注意减去空集情况。
答案就是：
$$
(k + 1)\sum_{j = 0}^{\frac{n(n + 1)k}{2}}f_{i - 1, j}f_{n - i, j} - 1
$$
~~前天模拟赛刚好学到前缀和优化多重背包，可以优化到 $O(n^2k)$。~~
Update on 2023/10/18：
错了，这个上限是 $O(n^2k)$ 级别的，总复杂度应该是 $O(n^3k)$，感谢 @[369Pai](https://www.luogu.com.cn/user/290023) 指出。
我不知道谁贺的谁的，题解区全说时间复杂度是 $O(n^2k)$。
Code:
```cpp
const ll N = 110;
namespace SOLVE {
ll n, k, P, f[N][N * N * N], ans[N];
inline ll rnt () {
ll x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
inline void In () {
n = rnt (), k = rnt (), P = rnt ();
return;
}
inline void Solve () {
f[0][0] = 1;
ll sum = 0, l = 0;
_for (i, 1, n) {
sum += i * k, l += k + 1;
_for (j, 0, i - 1) f[i][j] = f[i - 1][j];
_for (j, i, sum) f[i][j] = (f[i - 1][j] + f[i][j - i]) % P;
for_ (j, sum, l) f[i][j] = (f[i][j] - f[i][j - l] + P) % P;
}
_for (i, 1, n) {
ans[i] = 0;
_for (j, 0, sum) ans[i] = (ans[i] + f[i - 1][j] * f[n - i][j] % P) % P;
ans[i] = (ans[i] * (k + 1) % P - 1 + P) % P;
}
return;
}
inline void Out () {
_for (i, 1, n) printf ("%lld\n", ans[i]);
return;
}
}
```