[国家集训队]Crash的文明世界

集训队]Crash的文明世界"/>

[国家集训队]Crash的文明世界

Description

Luogu4827
BZOJ2159

给定一棵树，对于每个点\(x\)，求出\(\sum\limits_{i=1}^n dist(x, i)^k\)。

Solution

与\(x^k\)有关的题目，基本都要扯到第二类斯特林数上

啥是第二类斯特林数？第二类斯特林数\(\big\{^x_k\big\}\)表示将\(x\)个元素分成\(k\)个非空子集的方案数，\(\big\{^x_k\big\}=\big\{^{x-1}_{k-1}\big\}+k\big\{^{x-1}_k\big\}\)
这东西和\(x^k\)咋扯上的关系咧？\(x^k = \sum_{i=1}^k \big\{^k_i\big\} \cdot A_x^i\)，思考这个式子的组合意义就好了。当然这个式子也可以变形成\(\sum_{i=1}^k \big\{^k_i\big\} \cdot i! {x\choose i}\)

然后变形一下原来的式子\(\sum\limits_{i=1}^n dist(x, i)^k = \sum\limits_{i=1}^n \sum_{j=1}^k \big\{^k_j\big\} \cdot j! {dist(x, i)\choose i}\)，然后就是交换一下求和顺序，预处理前两项，树形DP最后一项即可。

Code

#include <cstdio>
#include <vector>const int N = 5e4 + 10;
const int M = 2 * N;
const int MOD = 10007;int n, K;
std::vector<int> g[N];
int fa[N];
int S[155][155]; // 斯特林数 
int fct[155]; // 阶乘
int u[N][155], d[N][155], ans[N]; void dfs1(int x, int fa) {d[x][0] = 1;for (int i : g[x]) if (i != fa) {dfs1(i, x);d[x][0] = (d[x][0] + d[i][0]) % MOD;for (int j = 1; j <= K; ++j) {d[x][j] = (d[x][j] + d[i][j-1] + d[i][j]) % MOD;}}
}void dfs2(int x, int fa) {u[x][0] = n-d[x][0];if (fa) for (int i = 1; i <= K; ++i) {u[x][i] = u[fa][i] + d[fa][i] - d[x][i] - d[x][i-1] + u[fa][i-1] + d[fa][i-1] - d[x][i-1] - d[x][i-2]+ 4 * MOD;u[x][i] %= MOD;}for (int i : g[x]) if (i != fa) dfs2(i, x);
}int main() {scanf("%d%d", &n, &K);for (int i = 1, x, y; i < n; ++i) {scanf("%d%d", &x, &y);g[x].push_back(y);g[y].push_back(x);}S[1][1] = 1;for (int i = 2; i <= K; ++i) {for (int j = 1; j <= K; ++j) {S[i][j] = (S[i-1][j-1] + S[i-1][j]*j) % MOD;}}fct[1] = 1;for (int i = 2; i <= K; ++i) fct[i] = i * fct[i-1] % MOD;dfs1(1, 0);dfs2(1, 0);for (int i = 1; i <= n; ++i) {for (int j = 1; j <= K; ++j) {ans[i] = (ans[i] + S[K][j]*fct[j]%MOD * (u[i][j]+d[i][j])%MOD) % MOD;}printf("%d\n", ans[i]);}return 0;
}

转载于:.html