题目大意

有n个节点的树，m个限制限制一个点的度数不能为多少。

容斥

显然可以容斥，然后就知道了一些限制。 根据prufer序的唯一对应性，假如有x个限制（注意如果有限制相同节点的不能算，所以现在讨论的这些限制都限制了不同节点的度数），第i个限制限制一个节点度数必须为d[i]。 答案为 Cd[1]−1n−2∗Cd[2]−1n−2−d[1]+1]∗……∗(n−x)n−2−∑xi=1d[i]−1

#include<cstdio> #include<algorithm> #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; typedef long long ll; const int maxn=1000000+10,maxm=17+10,mo=1000000007; int fac[maxn],inv[maxn]; int b[maxm],d[maxm]; bool bz[maxm],pd[maxm]; int i,j,k,l,t,n,m,ans; int quicksortmi(int x,int y){ if (!y) return 1; int t=quicksortmi(x,y/2); t=(ll)t*t%mo; if (y%2) t=(ll)t*x%mo; return t; } int C(int n,int m){ if (n<m) return 0; return (ll)fac[n]*inv[m]%mo*inv[n-m]%mo; } void dfs(int x,int y){ if (x==m+1){ int i,j=1,k=0,t=n-2; fo(i,1,m) if (bz[i]){ j=(ll)j*C(t,d[i]-1)%mo; t-=d[i]-1; k++; } j=(ll)j*quicksortmi(n-k,t)%mo; ans=(ans+(y%2?-j:j))%mo; return; } if (!pd[b[x]]){ bz[x]=1; pd[b[x]]=1; dfs(x+1,y+1); bz[x]=0; pd[b[x]]=0; } dfs(x+1,y); } int main(){ scanf("%d%d",&n,&m); fac[0]=1; fo(i,1,n) fac[i]=(ll)fac[i-1]*i%mo; inv[n]=quicksortmi(fac[n],mo-2); fd(i,n-1,0) inv[i]=(ll)inv[i+1]*(i+1)%mo; fo(i,1,m) scanf("%d%d",&b[i],&d[i]); dfs(1,0); (ans+=mo)%=mo; printf("%d\n",ans); }