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\) 个叶子节点的方案数，\(n\leq 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;

}