[国家集训队]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;
}