ARC104D Multiset Mean

题面

题解

枚举平均数 (x)，只需求有多少个集合满足 (sum S_i = |S|x) 即可。

移项，即 (sum (S_i - x) = 0)，将 (1, 2, cdots, x - 1) 分为一类，(x + 1, cdots, n) 分为一类，分别背包出来判断即可。

设 (f_{i, j}) 表示前 (i) 个数，和为 (j) 的方案数，那么第一类的方案数为 (f_{x - 1})，第二类为 (f_{n - x}) 所以只需要 dp 出这个背包即可。

用同余类优化，时间复杂度 (mathcal O(n^3k))。

代码

#include <cstdio>

inline int read()
{
	int data = 0, w = 1; char ch = getchar();
	while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if (ch == '-') w = -1, ch = getchar();
	while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data * w;
}

const int N(105);
int n, K, M, f[N][N * N * N], s[N];
inline void Add(int &x, int y) { x = (x + y) % M; }

int main()
{
	n = read(), K = read(), M = read(), f[0][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < i; j++) s[j] = 0;
		for (int j = 0; j <= i * i * K; j++)
		{
			Add(s[j % i], f[i - 1][j]);
			if (j >= (K + 1) * i) Add(s[j % i], M - f[i - 1][j - (K + 1) * i]);
			f[i][j] = s[j % i];
		}
	}
	for (int i = 1; i <= n; i++)
	{
		int ans = 0;
		for (int j = 1; j <= n * n * K; j++)
			Add(ans, 1ll * f[i - 1][j] * f[n - i][j] % M);
		printf("%lld
", (K + 1ll * ans * (K + 1)) % M);
	}
	return 0;
}