「国家集训队」Crash的文明世界

题目大意：给出一棵 $n$ 个点的树，每条边的长度为 $1$，对于每个点 $i$ 输出 $\sum\limits_{j=1}^{n}dis(i,j)^k \mod 10007$，其中 $dis(i,j)$ 表示点 $i$ 到点 $j$ 的距离。$n \leq 50000, k \leq 150$

根据第二类斯特林数的性质，有

$$m^n=\sum\limits_{k=1}^{m}k!\binom{m}{k} \left\{ \begin{matrix} n \\ k \end{matrix} \right\}$$

（其中 $k$ 的上限 $m$ 也可以换成 $n$，详见 Lmsh7的blog）

因此

$$\begin{eqnarray}\sum\limits_{j=1}^{n}dis(i,j)^k &=&\sum\limits_{j=1}^{n}\sum\limits_{l=1}^{k}l!\binom{dis(i,j)}{l}\left\{ \begin{matrix} k \\ l \end{matrix} \right\}\\ &=&\sum\limits_{l=1}^{k}l!\left\{ \begin{matrix} k \\ l \end{matrix} \right\}\sum\limits_{j=1}^{n}\binom{dis(i,j)}{l} \end{eqnarray}$$

设 $d[i][j]$ 表示 $l=j$ 时 $i$ 的子树对 $i$ 的贡献，$u[i,j]$ 表示子树 $i$ 之外的节点对 $i$ 的贡献。

由于每条边的长度为 $1$，根据杨辉三角，有 $d[fa[i]][j]=d[i][j-1]+d[i][j]$，而 $u$ 可以用 $d$ 来容斥得到。

其中 $d[i][0]$ 就是 $siz[i]$。

#include <cstdio>

const int N = 50005, M = 155, P = 10007;
int head[N], pre[N<<1], nxt[N<<1], d[N][M], u[N][M], s[M][M], fac[M], tot, n, K;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
void add_edge(int u, int v) {
    pre[++tot] = head[u];
    head[u] = tot, nxt[tot] = v;
}

void previous() {
    s[0][0] = 1;
    for (int i = 1; i <= K; ++i)
        for (int j = 1; j <= i; ++j)
            s[i][j] = (s[i-1][j] * j + s[i-1][j-1]) % P;
    fac[1] = 1;
    for (int i = 2; i <= K; ++i) fac[i] = fac[i-1] * i % P;
}
void dfs1(int cur, int fa) {
    d[cur][0] = 1; //相当于size
    for (int i = head[cur]; i; i = pre[i])
        if (nxt[i] != fa) {
            dfs1(nxt[i], cur);
            d[cur][0] += d[nxt[i]][0];
            for (int j = 1; j <= K; ++j)
                d[cur][j] = (d[cur][j] + d[nxt[i]][j-1] + d[nxt[i]][j]) % P;
        }
}
void dfs2(int cur, int fa) {
    if (fa) {
        u[cur][0] = n - d[cur][0];
        for (int i = 1; i <= K; ++i) {
            u[cur][i] = (u[fa][i] + u[fa][i-1] + d[fa][i] + d[fa][i-1] - d[cur][i] - (d[cur][i-1] << 1)) % P; //容斥
            if (i > 1) u[cur][i] = ((u[cur][i] - d[cur][i-2]) % P + P) % P;
        }
    }
    for (int i = head[cur]; i; i = pre[i])
        if (nxt[i] != fa) dfs2(nxt[i], cur);
}

int main() {
    n = read(), K = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        add_edge(u, v), add_edge(v, u);
    }
    previous(), dfs1(1, 0), dfs2(1, 0);
    for (int i = 1; i <= n; ++i) {
        int ans = 0;
        for (int j = 1; j <= K; ++j)
            ans = (ans + 1LL * fac[j] * s[K][j] * (d[i][j] + u[i][j])) % P;
        printf("%d\n", ans);
    }
    return 0;
}

时间复杂度 $O(nk)$