prufer编码

看51nod的一场比赛，发现不会大家都A的一道题，有关prufer的

我去年4月就埋下prufer这个坑，一直没解决

prufer编码是什么

对于一棵无根树的生成的序列，prufer序列可以和无根树一一对应，具体可以参见百科和poj2567和poj2568两个题。

prufer序列用来计数

1. (n) 个点的无向完全图的生成树的个数为 (n^{n-2}) 。即prufer序列的长度为 (n-2)，每个点的值是1 到 (n)
2. (n) 个节点的度依次为 (D_1)，(D_2)，...，(D_n) 的无根树共有 (dfrac{(n-2)!}{prod{(D_i-1)!}})。即第 (i) 个点出现了 (D_i-1) 次，变转换成问题：(n) 种元素，共 (n-2) 个，其中第 (i) 种元素有 (D_i-1) 个，求排列数。
3. (n) 个节点的度数有的已知有的未知，假设有 (m) 个未知的，(L=n-2-sum{(D_i-1)}) ，那么树的个数为 (dfrac{m^L(n-2)!}{L!prod{(D_i-1)!}}) ，参见bzoj1005。

51nod1805

大意：(n) 个点生成的树，(m) 个叶子节点的方案数，(nleq 10^6)

考虑这棵树的prufer序列，那么问题转化为长度为 (n-2) ，且在着 (n-2) 个数里面恰好出现了 (n-m) 个不同的数的方案数，就可以容斥一下解决了

inline int pw(int n,int m){int r=1;for(;m;m>>=1,n=1ll*n*n%MOD)if(m&1)r=1ll*r*n%MOD;return r;}
const int N=1e6+1;
int n,m,fac[N],fai[N];
void init(){
	fac[0]=1;For(i,1,N)fac[i]=1ll*fac[i-1]*i%MOD;
	fai[N-1]=pw(fac[N-1],MOD-2);
	per(i,1,N-1)fai[i-1]=1ll*fai[i]*i%MOD;
}
inline int C(int n,int m){return 1ll*fac[n]*fai[m]%MOD*fai[n-m]%MOD;}
int main(){
	init();
	n=rd(),m=rd();
	if(n==2&&m==2){puts("1");return 0;}
	ll ans=0;
	per(i,1,(n-m)){
		ans+=((n-m-i&1)?-1ll:1ll)*C(n-m,i)*pw(i,n-2)%MOD;
	}
	ans=(ans%MOD+MOD)%MOD;
	ans=ans*C(n,n-m)%MOD;
	cout<<ans<<endl;
}