1806 wangyurzee的树

链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1806

想法：因为$m \le 17$，所以用容斥统计一下。即限定一些$u_i$的度数为$d_i$，然后变成Prufer统计带标号树的计数。

#include< cstdio >#define FILE(F) freopen(F".in","r",stdin),freopen(F".out","w",stdout)#define gec getchar#define DEBUG fprintf(stderr,"Passing [%s] in Line (%d)\n",__FUNCTION__,__LINE__);typedef long long ll;templateinline void read(T&x){	x=0;bool f=0;char c=gec();	for(;c<‘0‘||c>‘9‘;c=gec())f|=(c==‘-‘);	for(;c>=‘0‘&&c<=‘9‘;c=gec())x=x*10+c-‘0‘;	x=f?-x:x;}const int MAXN(1e6+10),S(1<<17),MP(1000000007);int inv[MAXN],fac[MAXN],ok[20];void Deal_Fac(int n){	fac[0]=inv[0]=inv[1]=1;	for(int i=1;i<=n;i++)fac[i]=(ll)fac[i-1]*i%MP;	for(int i=2;i<=n;i++)inv[i]=(MP-MP/i)*(ll)inv[MP%i]%MP;	for(int i=2;i<=n;i++)inv[i]=(ll)inv[i]*inv[i-1]%MP;}int A(int n,int m){return n>=m?(ll)fac[n]*inv[n-m]%MP:0;}int C(int n,int m){return n>=m?(ll)fac[n]*inv[m]%MP*(ll)inv[n-m]%MP:0;}int power(int a,int b){	int t=1;	for(;b;b>>=1){if(b&1)t=(ll)t*a%MP;a=(ll)a*a%MP;}	return t;}int n,m,d[20],u[20],Ans;int main(){#ifndef ONLINE_JUDGE 	FILE("C");#endif	Deal_Fac(1e6); read(n);read(m);	for(int i=0;i<m;i++)read(u[i]),read(d[i]),u[i]--;	for(int i=0,tmp,sum,cnt,cont;i<1<<m;i++)	{		tmp=1;sum=0;cnt=0;cont=0;		for(int j=0;j<m;j++)		if(i&(1<<j))		{			if(ok[u[j]]==i){cont=1;break;} ok[u[j]]=i;			tmp=(ll)tmp*C(n-2-sum,d[j]-1)%MP;sum+=d[j]-1;cnt++;		}		if(sum>n-2||cont)continue;//巧了，不存在。		tmp=(ll)tmp*power(n-cnt,n-2-sum)%MP;		if(cnt&1)Ans-=tmp;else Ans+=tmp;		Ans%=MP;	}	if(n==1&&m==0)Ans=1;	Ans+=Ans<0?MP:0;	printf("%d\n",Ans);	return 0;}

51Nod 1806 wangyurzee的树