娃娃机毒瘤 qwq
题意简述：求所有\(n\)个点的有标号有根树的子树大小乘积的\(k\)次方和，对\(p\)取模。\(n\leq 5000, k\leq p\leq 10^9\)。
看上去吓人实际上不算难的计数题……
设\(f_i\)表示\(i\)个点的有标号有根树的答案，\(g_i\)表示\(i\)个点的有标号有根森林的答案，考虑转移。
对于\(f_i\)，根节点有\(i\)种选择方案，每种方案会产生\(i^k\cdot g_{i-1}\)的贡献。
对于\(g_i\)，考虑枚举\(i\)号点所在子树大小\(j\in[1, n]\)，其中根节点有\(j\)种选择方案，每种方案中，\(i\)点一定在这棵树中，其余\(j-1\)个点从\(i-1\)个点中自由选择，这\(j\)个点组合成一棵树会产生\(f_j\)的贡献。
因此暴力\(O(n^2)\)dp即可，写了三模数\(\operatorname{fft}\)……
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#define R register
#define ll long long
using namespace std;
const int N = 5100;
int n, k, mod;
ll f[N], g[N], fac[N], comb[N][N];
template <class T> inline void read(T &x) {
x = 0;
char ch = getchar(), w = 0;
while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x = w ? -x : x;
return;
}
inline ll quickpow(ll base, ll pw) {
ll ret = 1;
while (pw) {
if (pw & 1) ret = ret * base % mod;
base = base * base % mod, pw >>= 1;
}
return ret;
}
int main() {
read(n), read(k), read(mod);
f[0] = g[0] = fac[0] = comb[0][0] = 1;
for (R int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod, comb[i][0] = 1;
for (R int j = 1; j <= i; ++j)
comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % mod;
}
for (R int i = 1; i <= n; ++i) {
f[i] = g[i - 1] * i % mod * quickpow(i, k) % mod;
for (R int j = 1; j <= i; ++j)
g[i] = (g[i] + f[j] % mod * comb[i - 1][j - 1] % mod * g[i - j]) % mod;
}
for (R int i = 1; i <= n; ++i)
printf("%lld ", f[i]);
return 0;
}