首页 > 代码库 > 51nod 1806 wangyurzee的树

51nod 1806 wangyurzee的树

2024-09-26 05:02:39   215人阅读

基准时间限制：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 11 2
Output示例
2

 

树 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}$

 

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

 

 

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int mod=1e9+7; 9 const int mxn=1000050;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14     return x*f;15 }16 int inv[mxn],fac[mxn];17 void init(int n){18     n+=5;19     inv[0]=inv[1]=1;fac[0]=fac[1]=1;20     for(int i=2;i<=n;i++){21         fac[i]=(LL)fac[i-1]*i%mod;22         inv[i]=((-mod/i*(LL)inv[mod%i])%mod+mod)%mod;23     }24     for(int i=2;i<=n;i++)inv[i]=(LL)inv[i-1]*inv[i]%mod;25     return;26 }27 int n,m;28 int u[20],d[20];bool vis[20];29 LL ans=0;30 int ksm(int a,int k){31     int res=1;32     while(k){33         if(k&1)res=(LL)res*a%mod;34         a=(LL)a*a%mod;35         k>>=1;36     }37     return res;38 }39 int main(){40     int i,j;41     n=read();m=read();42     if(n==1){printf("1\n");return 0;}43     init(n);44     for(i=0;i<m;i++){45         u[i]=read();d[i]=read();46     }47     ans=ksm(n,n-2);48     int ed=1<<m;49     for(int S=1;S<ed;S++){//枚举状态 50         int tmp=S,smm=0,cnt=0;bool flag=1;51         LL down=1;52         memset(vis,0,sizeof vis);53         for(i=0;i<m;i++){54             if((S>>i)&1){55                 if(vis[u[i]]){flag=0;break;}//限制重复 56                 vis[u[i]]=1;57                 smm+=d[i]-1;58                 ++cnt;59                 down=down*inv[d[i]-1]%mod;60             }61         }62         if(!flag)continue;63         if(smm>n-2)continue;64         LL up=fac[n-2];65         up=up*down%mod*inv[n-2-smm]%mod;66         up=up*ksm(n-cnt,n-2-smm)%mod;67         (ans+=(cnt&1)?-up:up)%=mod;68     }69     ans=(ans+mod)%mod;70     printf("%lld\n",ans);71     return 0;72 }

 

51nod 1806 wangyurzee的树


联系
我们