题解 P4827 【[国家集训队] Crash 的文明世界】

· · 题解

Description

给定一棵 n 个点 n-1 条边的无向连通图，对于每个点 i 求出：

S(i) = \sum_{j=1}^n dist(i,j)^k

Solution

观察题目考虑利用第二类斯特林数进行推导。斯特林数具有如下性质：

m^n=\sum\limits_{i=0}^m\begin{Bmatrix}n \\ i\end{Bmatrix}*i!*\dbinom{m}{i}

这里给出感性证明。考虑到 m^n 是把 n 个不同的小球放进 m 个不同的盒子,允许空盒的方案数。由于要求非空，需要从 m 个盒子里面选出 i 个非空盒子,要乘上 \dbinom{m}{i} 。将 n 个球放进去需要乘上 \begin{Bmatrix}n \\ i\end{Bmatrix} ，由于盒子不同，最后需要乘以 i! 。

对于点 i 考虑将原先的式子用斯特林数展开：

\begin {aligned} S(i) &=\sum_{j=1}^n dist(i,j)^k \\ \\ &=\sum_{j=1}^n\sum_{t=0}^k \begin{Bmatrix} k\\t \end{Bmatrix} \binom{dist(i,j)}{t} i! \end{aligned}

调整一下顺序即有：

S(i)=\sum_{t=0}^k \begin{Bmatrix} k\\t \end{Bmatrix} i! \sum_{j=1}^n \binom{dist(i,j)}{t}

我们可以简单递推预处理出斯特林数和阶乘的部分，之后换根dp求解后半部分即可。

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x=0,f=1,c=getchar();
    while(c<48) c=='-'&&(f=-1),c=getchar();
    while(c>47) x=x*10+c-'0',c=getchar();
    return x*f;
}

const int mod = 10007;
const int MAXN = 50005;
std::vector<int> G[MAXN];
int f[MAXN][155],g[MAXN][155];
int s[155][155],fac[155],res[MAXN];
int n,k;

inline void addedge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

void dfs(int x,int fa)
{
    f[x][0]=1;
    for(int &y : G[x])
    {
        if(y==fa) continue; dfs(y,x);
        for(int j=0; j<=k; ++j) (f[x][j]+=f[y][j])%=mod;
        for(int j=1; j<=k; ++j) (f[x][j]+=f[y][j-1])%=mod;
    }
}

inline void sol(int x,int fa)
{
    for(int j=0; j<=k; ++j) g[x][j]=f[x][j];
    if(fa)
    {
        for(int j=0; j<=k; ++j) res[j]=(g[fa][j]-f[x][j]+mod)%mod;
        for(int j=1; j<=k; ++j) res[j]=(res[j]-f[x][j-1]+mod)%mod;
        for(int j=0; j<=k; ++j) g[x][j]=(g[x][j]+res[j])%mod;
        for(int j=1; j<=k; ++j) g[x][j]=(g[x][j]+res[j-1])%mod;
    }
    for(int &y : G[x]) if(y^fa) sol(y,x);
}

inline void init()
{
    for(int i=1; i<=k; ++i) fac[i]=fac[i-1]*i%mod;
    for(int i=1; i<=k; ++i)
        for(int j=1; j<=i; ++j)
            s[i][j]=(s[i-1][j-1]+j*s[i-1][j])%mod;
}

int main(int argc, char const *argv[])
{
    n=read(); k=read(); fac[0]=s[0][0]=1;
    for(int i=1; i<n; ++i)
        addedge(read(),read());
    init(); dfs(1,0); sol(1,0);
    for(int i=1; i<=n; ++i)
    {
        int ans=0;
        for(int j=0; j<=k; ++j)
            ans=(ans+s[k][j]*fac[j]%mod*g[i][j]%mod)%mod;
        printf("%d\n",ans);
    }
    return 0;
}