[国家集训队] Crash 的文明世界——斯特林反演、组合数、换根DP

第二类斯特林数有一个公式： x k = ∑ i = 0 k S ( k , i ) i ! ( x i ) x^k=sum_{i=0}^kS(k,i)i!{xchoose i} xk=∑i=0k​S(k,i)i!(ix​)，现在终于记住了，勉强能用了。

我们先把答案用这个公式转换一下：
S ( u ) = ∑ v = 1 n d i s t ( u , v ) k = ∑ v = 1 n ∑ i = 0 k S ( k , i ) i ! ( d i s t ( u , v ) i ) = ∑ i = 0 k S ( k , i ) i ! ∑ v = 1 n ( d i s t ( u , v ) i ) S(u)=sum_{v=1}^n dist(u,v)^k\ =sum_{v=1}^nsum_{i=0}^kS(k,i)i!{dist(u,v)choose i}\ =sum_{i=0}^kS(k,i)i!sum_{v=1}^n{dist(u,v)choose i} S(u)=v=1∑n​dist(u,v)k=v=1∑n​i=0∑k​S(k,i)i!(idist(u,v)​)=i=0∑k​S(k,i)i!v=1∑n​(idist(u,v)​)

我们设 f ( x , i ) = ∑ v 在 x 的 子 树 内 ( d i s t ( x , v ) i ) f(x,i)=sum_{v在x的子树内}{dist(x,v)choose i} f(x,i)=∑v在x的子树内​(idist(x,v)​)，我们知道 ( n m ) = ( n − 1 m ) + ( n − 1 m − 1 ) {nchoose m}={n-1choose m}+{n-1choose m-1} (mn​)=(mn−1​)+(m−1n−1​)，所以
f ( x , i ) = ∑ v 在 x 的 子 树 内 ( d i s t ( x , v ) − 1 i ) + ( d i s t ( x , v ) − 1 i − 1 ) = ∑ ( x , v ) ∈ E f ( v , i ) + f ( v , i − 1 ) f(x,i)=sum_{v在x的子树内}{dist(x,v)-1choose i}+{dist(x,v)-1choose i-1}\ =sum_{(x,v)in E}f(v,i)+f(v,i-1) f(x,i)=v在x的子树内∑​(idist(x,v)−1​)+(i−1dist(x,v)−1​)=(x,v)∈E∑​f(v,i)+f(v,i−1)
直接树形DP转移。

由于我们要求的是每个点为根时的DP值，所以再做一次换根DP即可。

时间复杂度 O ( n k ) O(nk) O(nk)。

#include//JZM yyds!!
#define ll long long
#define uns unsigned
#define IF (it->first)
#define IS (it->second)
#define END putchar('n')
using namespace std;
const int MAXN=50005;
const ll INF=1e18;
inline ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[30],lpt;
inline void print(ll x,char c='n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
inline ll lowbit(ll x){return x&-x;}

const ll MOD=10007;
struct edge{
	int v,to;edge(){}
	edge(int V,int T){v=V,to=T;}
}e[MAXN<<1];
int EN,G[MAXN];
inline void addedge(int u,int v){
	e[++EN]=edge(v,G[u]),G[u]=EN;
	e[++EN]=edge(u,G[v]),G[v]=EN;
}

int n,k;
ll fac[MAXN],S[155][155],f[MAXN][155],as[MAXN];
inline void ad(ll&a,ll b){a+=b;if(a>=MOD)a-=MOD;}
inline void dfs1(int x,int fa){
	f[x][0]=1;
	for(int i=G[x];i;i=e[i].to){
		int v=e[i].v;
		if(v==fa)continue;
		dfs1(v,x);
		ad(f[x][0],f[v][0]);
		for(int j=1;j<=k;j++)
			ad(f[x][j],f[v][j]),ad(f[x][j],f[v][j-1]);
	}
}
inline void dfs2(int x,int fa){
	for(int i=0;i<=k;i++)
		ad(as[x],S[k][i]*fac[i]%MOD*f[x][i]%MOD);
	for(int i=G[x];i;i=e[i].to){
		int v=e[i].v;
		if(v==fa)continue;
		ad(f[x][0],MOD-f[v][0]);
		for(int j=1;j<=k;j++)
			ad(f[x][j],MOD-f[v][j]),ad(f[x][j],MOD-f[v][j-1]);
		ad(f[v][0],f[x][0]);
		for(int j=1;j<=k;j++)
			ad(f[v][j],f[x][j]),ad(f[v][j],f[x][j-1]);
		dfs2(v,x);
		ad(f[v][0],MOD-f[x][0]);
		for(int j=1;j<=k;j++)
			ad(f[v][j],MOD-f[x][j]),ad(f[v][j],MOD-f[x][j-1]);
		ad(f[x][0],f[v][0]);
		for(int j=1;j<=k;j++)
			ad(f[x][j],f[v][j]),ad(f[x][j],f[v][j-1]);
	}
}
signed main()
{
	n=read(),k=read();
	S[0][0]=1,fac[0]=1;
	for(int i=1;i<=k;i++){
		fac[i]=fac[i-1]*i%MOD;
		for(int j=1;j<=i;j++)
			S[i][j]=(S[i-1][j]*j+S[i-1][j-1])%MOD;
	}
	for(int i=1;i