【BZOJ2159】Crash的文明世界（第二类斯特林数，动态规划）
题面
题解
看到(k)次方的式子就可以往二项式的展开上面考，但是显然这样子的复杂度会有一个(O(k^2))，因此需要换别的方法。
注意到自然指数幂和第二林斯特林数之间的关系：
[n^k=sum_{i=0}^k egin{Bmatrix}k\iend{Bmatrix}{nchoose i}i!
]
那么将答案式化简
[egin{aligned}
Ans_x&=sum_{i=1}^N dis(i,x)^K\
&=sum_{i=1}^N sum_{j=0}^K egin{Bmatrix}K\jend{Bmatrix}{dis(x,i)choose j}j!\
&=sum_{j=0}^Kegin{Bmatrix}K\jend{Bmatrix}j!sum_{i=1}^N {dis(x,i)choose j}
end{aligned}]
那么对于每一个点(x)，要求的只有(displaystyle sum_{i=1}^N {dis(x,i)choose j})
我们知道组合数杨辉三角上的转移(displaystyle {nchoose m}={n-1choose m}+{n-1choose m-1})
那么带进去，可以得到：$$sum_{i=1}^N {dis(x,i)choose j}=sum_{i=1}^N {dis(x,i)-1choose j}+sum_{i=1}^N {dis(x,i)-1choose j-1}$$
考虑怎么(dp)，设(f[i][j])表示(i)子树内的({dischoose j})的和。
考虑节点(u)和其儿子(v)。显然(v)的子树到(u)的距离是到(v)的距离(-1)。
所以可以得到转移(displaystyle f[u][j]=sum_{v}(f[v][j]+f[v][j-1]))。
因为需要换根(dp)，所以再额外考虑清楚如何减去一个子树的贡献，这里懒得写了。
那么只需要换根(dp)做完之后求出所有节点的(f)，再预处理第二类斯特林数直接算答案即可。
BZOJ数据有点奇怪，用注释的部分读入
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define MOD 10007
#define MAX 50500
#define MAXK 155
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct Line{int v,next;}e[MAX<<1];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int S[MAXK][MAXK],jc[MAXK];
int f[MAX][MAXK],g[MAX][MAXK],tmp[MAXK];
int n,K;
void dfs(int u,int ff)
{
f[u][0]=1;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;if(v==ff)continue;
dfs(v,u);
for(int j=0;j<=K;++j)f[u][j]=(f[u][j]+f[v][j])%MOD;
for(int j=1;j<=K;++j)f[u][j]=(f[u][j]+f[v][j-1])%MOD;
}
}
void DFS(int u,int ff)
{
for(int j=0;j<=K;++j)g[u][j]=f[u][j];
if(ff)
{
for(int j=0;j<=K;++j)tmp[j]=g[ff][j];
for(int j=0;j<=K;++j)tmp[j]=(tmp[j]+MOD-f[u][j])%MOD;
for(int j=1;j<=K;++j)tmp[j]=(tmp[j]+MOD-f[u][j-1])%MOD;
for(int j=0;j<=K;++j)g[u][j]=(g[u][j]+tmp[j])%MOD;
for(int j=1;j<=K;++j)g[u][j]=(g[u][j]+tmp[j-1])%MOD;
}
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff)DFS(e[i].v,u);
}
int main()
{
/*
int L,now,A,B,Q;
scanf("%d%d%d%d%d%d%d",&n,&K,&L,&now,&A,&B,&Q);
for(int i=1;i<n;i++)
{
now=(now*A+B)%Q;
int tmp=i<L?i:L;
int x=i-now%tmp,y=i+1;
Add(x,y);
}
*/
n=read();K=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read();
Add(u,v);Add(v,u);
}
S[0][0]=jc[0]=1;
for(int i=1;i<=K;++i)jc[i]=jc[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;
dfs(1,0);DFS(1,0);
for(int i=1;i<=n;++i)
{
int ans=0;
for(int j=0;j<=K;++j)
ans=(ans+1ll*S[K][j]*jc[j]*g[i][j])%MOD;
printf("%d
",ans);
}
return 0;
}