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

一、题目

点此看题

二、解法

要求的是这个柿子：

\[\sum_{j=1}^ndis(x,j)^k \]

一看这个 \(dis(x,j)^k\) 然后 \(k\) 很小就知道是套路题了，直接第二类斯特林数反演：

\[\sum_{j=1}^n\sum_{i=0}^kS(k,i)\times i!\times C(dis(x,j),i) \]

然后略微的变换一下，因为 \(S(k,i)\times i!\) 和 \(j\) 没有一点关系，所以可以提到前面去：

\[\sum_{i=0}^kS(k,i)\times i!\sum_{j=1}^nC(dis(x,j),i) \]

由于 \(k\) 很小，前面那些东西可以直接算，问题是求后面的 \(f(x,i)=\sum_{j=1}^n C(dis(x,j),i)\) ，直接算会比较难，但是你发现 这个东西是放在树上的 ，这个关键条件没有用到啊！如果能通过递推的方式算出 \(f(x,i)\) 就好了。

因为 \(C(dis(x,j),i)=C(dis(x,j)-1,i)+C(dis(x,j)-1,i-1)\) ，设 \(y\) 是 \(x\) 的儿子，那么有递推式：

\[f(x,i)=f(y,i)+f(y,i-1) \]

但是你发现这个只对 \(x\) 是根的情况成立，所以外面还要套一个换根 \(dp\) ，这个很容易写吧，时间复杂度 \(O(nk)\)

\(\tt UPD 2021/10/29\)：也可以直接用组合意义做，相当于从路径上选出 \(i\) 个点，我们枚举另一个端点从哪个子树中来，然后讨论点 \(u\) 选不选，也可以得到上面的转移。

#include 
const int M = 50005;
const int MOD = 10007;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,k,tot,f[M],ans[M],fac[155],s[155][155];
int dp[M][155],t1[M][155],t2[M][155];
struct edge
{
	int v,next;
	edge(int V=0,int N=0) : v(V) , next(N) {} 
}e[2*M];
void dfs(int u,int fa)
{
	dp[u][0]=1;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
		for(int j=1;j<=k;j++)
			dp[u][j]=(dp[u][j]+dp[v][j]+dp[v][j-1])%MOD;
		dp[u][0]=(dp[u][0]+dp[v][0])%MOD;
	}
}
void dfs2(int u,int fa)
{
	for(int i=0;i<=k;i++)
		ans[u]=(ans[u]+1ll*s[k][i]*fac[i]%MOD*dp[u][i])%MOD;
	for(int w=f[u];w;w=e[w].next)//换根 
	{
		int v=e[w].v;
		if(v==fa) continue;
		for(int i=0;i<=k;i++)
			t1[u][i]=dp[u][i],t2[u][i]=dp[v][i];
		//先把v的贡献从u中删掉
		dp[u][0]-=dp[v][0];
		for(int i=1;i<=k;i++)
			dp[u][i]=(dp[u][i]-dp[v][i]-dp[v][i-1])%MOD;
		//在把u加到v里面去,分开写 
		dp[v][0]+=dp[u][0];
		for(int i=1;i<=k;i++)
			dp[v][i]=(dp[v][i]+dp[u][i]+dp[u][i-1])%MOD;
		dfs2(v,u);
		//还原，回溯
		for(int i=0;i<=k;i++)
			dp[u][i]=t1[u][i],dp[v][i]=t2[u][i]; 
	}
}
signed main()
{
	n=read();k=read();
	s[0][0]=fac[0]=1;
	for(int i=1;i<=k;i++)
		fac[i]=1ll*fac[i-1]*i%MOD;
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++)
			s[i][j]=(1ll*s[i-1][j]*j+s[i-1][j-1])%MOD; 
	for(int i=1;i