51nod 1806 wangyurzee的树

基准时间限制：1 秒空间限制：131072 KB

wangyurzee有n个各不相同的节点，编号从1到n。wangyurzee想在它们之间连n-1条边，从而使它们成为一棵树。
可是wangyurzee发现方案数太多了，于是他又给出了m个限制条件，其中第i个限制条件限制了编号为u[i]的节点的度数不能为d[i]。
一个节点的度数，就是指和该节点相关联的边的条数。
这样一来，方案数就减少了，问题也就变得容易了，现在请你告诉wangyurzee连边的方案总数为多少。
答案请对1000000007取模。

样例解释
总方案共有3种，分别为{(1,2),(1,3)}，{(1,2),(2,3)}，{(2,3),(1,3)}。其中第二种方案节点1的度数为2，不符合要求，因此答案为2。

Input

第一行输入2个整数n(1<=n<=1000000)，m(0<=m<=17)分别表示节点个数以及限制个数。

第2行到第m+1行描述m个限制条件，第i+1行为2个整数u[i]，d[i]，表示编号为u[i]的节点度数不能为d[i]。

为了方便起见，保证1<=ui<=m。同时保证1<=ui<=n，1<=di<=n-1，保证不会有两条完全相同的限制。

Output

输出一行一个整数表示答案。

Input示例

3 1

1 2

Output示例

树 prufer编码数学问题容斥

算度数不为d[i]的方案数看上去不可做，考虑算度数为d[i]的方案数。

首先我们知道n个点有标号生成树的数量为 $ n^{n-2} $

注意到限制条件m很小，可以计算不满足一个条件的方案数，不满足两个条件的方案数，不满足三个条件的方案数……然后容斥一下。

假设当前计算不满足某x个条件的方案数：

若一个点的度数为 $ d[i] $，那么它在prufer序列中出现了 $ d[i]-1 $次。
现在有x个点的贡献确定了，其度数总和为

$ \sum_{i=1}^{x} d[i] $

那么在prufer序列中有

$ sum=\sum_{i=1}^{x} (d[i]-1) $　　个位置被占用。
占用这么多位置的方案数是

$ C(n-2, sum)$
这些位置里选$d[1]-1$个位置填第1种编号，方案数为

$ C(sum,d[1]-1)$
再选位置填第2种编号，方案数为

$ C(sum-d[1]-1,d[2]-1)$
以此类推
根据乘法原理把上面这些组合数乘起来，化简得到：
$ \frac{(n-2)!}{(n-2-sum)! * \Pi (d[i]-1)!}$
prufer序列中剩下的位置可以任意填不被限制度数的点，共有

$(n-x)^{n-2-sum}$　　种方案
所以符合当前度数限制的方案数有
$ \frac{(n-2)!}{(n-2-sum)! * \Pi (d[i]-1)!} * (n-x)^{n-2-sum}$

注意：可能出现两个限制条件同时限制一个点的度数，需要特判

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #define LL long long

 using namespace std;

 const int mod=1e9+;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int inv[mxn],fac[mxn];

 void init(int n){

     n+=;

     inv[]=inv[]=;fac[]=fac[]=;

     for(int i=;i<=n;i++){

         fac[i]=(LL)fac[i-]*i%mod;

         inv[i]=((-mod/i*(LL)inv[mod%i])%mod+mod)%mod;

     }

     for(int i=;i<=n;i++)inv[i]=(LL)inv[i-]*inv[i]%mod;

     return;

 }

 int n,m;

 int u[],d[];bool vis[];

 LL ans=;

 int ksm(int a,int k){

     int res=;

     while(k){

         if(k&)res=(LL)res*a%mod;

         a=(LL)a*a%mod;

         k>>=;

     }

     return res;

 }

 int main(){

     int i,j;

     n=read();m=read();

     if(n==){printf("1\n");return ;}

     init(n);

     for(i=;i<m;i++){

         u[i]=read();d[i]=read();

     }

     ans=ksm(n,n-);

     int ed=<<m;

     for(int S=;S<ed;S++){//枚举状态

         int tmp=S,smm=,cnt=;bool flag=;

         LL down=;

         memset(vis,,sizeof vis);

         for(i=;i<m;i++){

             if((S>>i)&){

                 if(vis[u[i]]){flag=;break;}//限制重复

                 vis[u[i]]=;

                 smm+=d[i]-;

                 ++cnt;

                 down=down*inv[d[i]-]%mod;

             }

         }

         if(!flag)continue;

         if(smm>n-)continue;

         LL up=fac[n-];

         up=up*down%mod*inv[n--smm]%mod;

         up=up*ksm(n-cnt,n--smm)%mod;

         (ans+=(cnt&)?-up:up)%=mod;

     }

     ans=(ans+mod)%mod;

     printf("%lld\n",ans);

     return ;

 }

秒客网

51nod 1806 wangyurzee的树

相关文章