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

P4827 国家集训队 Crash 的文明世界
前置：

[egin{matrix} displaystyle m^n = sum_{i=0}^megin{Bmatrix}n\iend{Bmatrix}i!dbinom{m}{i} = sum_{i=0}^{n}egin{Bmatrix}n\iend{Bmatrix}i!dbinom{m}{i} end{matrix}]

推式子（钦定 (x) 为根）：

[egin{matrix} displaystyle sum_{i=1}^n dist(i,x)^k = sum_{i=1}^n sum_{j=0} ^{dist(i,x)} egin{Bmatrix}k\jend{Bmatrix} j! dbinom{dist(i,x)}{j}\ displaystyle = sum_{i=1}^n sum_{j=0}^{dist(i,x)}egin{Bmatrix}k\jend{Bmatrix}j!Big( inom{dist(i,x)-1}{j}+ inom{dist(i,x)-1}{j-1} Big)\ displaystyle =sum_{i=1}^n sum_{j=0}^{k}egin{Bmatrix}k\jend{Bmatrix}j!Big( inom{dist(i,x)-1}{j}+ inom{dist(i,x)-1}{j-1} Big) \ displaystyle = sum_{j=0}^{k} egin{Bmatrix}k\jend{Bmatrix} j! sum_{i=1}^{n}Big( inom{dist(i,x)-1}{j}+ inom{dist(i,x)-1}{j-1} Big) end{matrix}]

然后用 (f_{x,j}) 表示在 (x) 点子树内 (dbinom{dist(i,x)}{j})，其中 (i) 在 (x) 的子树内。
然后可以从儿子转移一下.
(displaystyle f_{x,i} = sum_{v in son_x}(f_{v,i-1}+f_{v,i}))
然后换根。

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

using namespace std;

typedef long long ll;
const ll MAXN = 1e5+10;
const ll MOD = 1e4+7;

struct edge {
    ll nt, to;
} E[MAXN];

ll N, K, head[MAXN], fac[160], cnt = -1, f[MAXN][160], dis[MAXN], ans[MAXN], f2[MAXN][160], tem[160], str[200][200];

void dfs(ll, ll);
void dfs2(ll, ll);
void add(ll, ll);

int main() {
    memset(head, -1, sizeof(head));
    scanf("%lld%lld", &N, &K);
    for (ll x, y, i = 1; i < N; i++) {
        scanf("%lld%lld", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs(1, 0); dfs2(1, 0);
    str[0][0] = 1; fac[0] = 1;
    for (ll i = 1; i <= K; i++) {
        str[i][0] = 0;
        for (ll j = 1; j <= K; j++) {
            str[i][j] = (str[i-1][j-1] + j * str[i-1][j] % MOD) % MOD;
        }
        fac[i] = fac[i-1] * i % MOD;
    }
    for (ll i = 1; i <= N; i++) {
        ll ans = 0;
        for (ll j = 0; j <= K; j++) ans = (ans + str[K][j] * fac[j] % MOD * f2[i][j] % MOD) % MOD;
        printf("%lld
", (ans + MOD) % MOD); 
    }
    return 0;
}

void dfs2(ll n, ll ff) {
    for (ll i = 0; i <= K; i++) f2[n][i] = f[n][i];
    if (ff) {
        for (ll i = 1; i <= K; i++) tem[i] = (f2[ff][i] - f[n][i] + MOD - f[n][i-1] + MOD) % MOD;
        tem[0] = (f2[ff][0] - f[n][0] + MOD) % MOD;
        for (ll i = 1; i <= K; i++) f2[n][i] = (f2[n][i] + tem[i-1] + tem[i]) % MOD;
        f2[n][0] = (f2[n][0] + tem[0] + MOD) % MOD;
    }
    for (ll i = head[n]; ~i; i = E[i].nt) {
        ll v = E[i].to;
        if (v == ff) continue;
        else {
            dfs2(v, n);
        }
    }
}

void add(ll x, ll y) {
    cnt++;
    E[cnt].to = y;
    E[cnt].nt = head[x];
    head[x] = cnt;
}

void dfs(ll n, ll ff) {
    f[n][0] = 1;
    for (ll i = head[n]; ~i; i = E[i].nt) {
        ll v = E[i].to;
        if (v == ff) continue;
        else {
            dfs(v, n);
            for (ll j = 1; j <= K; j++) f[n][j] = (f[n][j] + f[v][j-1] + f[v][j]) % MOD;
            f[n][0] = (f[n][0] + f[v][0]) % MOD;
        }
    }
}