一、题目：

洛谷原题

二、思路：

非常妙的DP题。

我们考虑一个以 \(x\) 为平均数的集合 \(S\)，再考虑这样两个集合：\(A_1=\{x-z|z\in S,z<x\},A_2=\{z-x|z\in S,z>x\}\)，我们会发现 \(A_1\) 和 \(A_2\) 中集合元素之和是相等的。

所以假设我们已经求出了 \(dp(i,j)\)，表示考虑了前 \(i\) 个正整数，能凑出 \(j\) 的方案数。那么以 \(x\) 为平均数的集合个数为：

\[-1+(K+1)\sum_{k=0}^{n(n-1)/2\times K} dp(x-1,k)\times dp(n-x,k) \]

为什么要减一呢？只是因为有一种情况不符合题意，那就是什么都不选的情况。

再来考虑 \(dp\) 数组如何求解。首先可以想到多重背包的做法，即：

\[dp(i,j)=\sum_{k=0}^K dp(i-1,j-i*k) \]

时间复杂度 \(O(n^3K)\)。不能通过本题。

再来考虑多重背包的经典优化，那就是同余优化。观察到 \(dp(i,j)\) 是由 \(dp(i-1,j),dp(i-1,j-i),dp(i-1,j-i*2),\ldots,dp(i-1,j\mod i)\) 转移来的，所以考虑对 \(\{dp(i-1,j-k\times i)\}\)进行前缀和优化。

时间复杂度 \(O(n^2K)\)。

三、代码：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

inline int read(void) {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return f * x;
}

const int maxn = 105;

int n, K, mod;
long long dp[maxn][maxn * maxn * maxn];
long long f[maxn];

inline void init(void) {
    dp[0][0] = 1;
    for (int j = 0; j <= K; ++ j) dp[1][j] = 1;
    for (int i = 2; i <= n; ++ i) {
        memset(f, 0, sizeof f);
        for (int j = 0; j <= n * (n - 1) / 2 * K; ++ j) {
            int x = j % i;
            (f[x] += dp[i - 1][j]) %= mod;
            if (j - i * (K + 1) >= 0) {
                (f[x] -= dp[i - 1][j - i * (K + 1)]) %= mod;
                if (f[x] < 0) f[x] += mod;
            }
            dp[i][j] = f[x];
        }
    }
}

int main() {
    n = read(); K = read(); mod = read();
    init();
    for (int x = 1; x <= n; ++ x) {
        long long ans = 0;
        for (int j = 0; j <= n * (n - 1) / 2 * K; ++ j) {
            (ans += dp[x - 1][j] * dp[n - x][j] % mod) %= mod;
        }
        (ans *= (K + 1)) %= mod;
        -- ans;
        if (ans < 0) ans += mod;
        printf("%lld\n", ans);
    }
    return 0;
}