51NOD 1806 wangyurzee的树[容斥+purfer序列]

题目描述

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

输入输出格式

输入格式

第一行输入$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<=U_i<=m$。同时保证 $1<=U_i<=n,1<=D_i<=n-1$,保证不会有两条完全相同的限制。

输出格式

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

输入输出样例

输入样例

3 1
1 2

输出样例

2

样例解释

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

题解

总的情况是 $n^(n-2)$ 种
我们考虑点 $u[i]$ 度数为 $d[i]$ 的情况,然后随便容斥一下就可以了。
注意:当$u[i]==u[j]$时,这种情况要跳过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
int read()
{
char s;int k=0,base=1;while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
int n,m;
int u[20],d[20];
const long long mod=1000000007;
long long ksm(long long x,int y)
{
long long sum=1;
while (y) {if (y&1) sum=sum*x%mod;x=x*x;if (x>=mod) x%=mod;y>>=1;}
return sum;
}
long long ans,jie[1001000],ny[1001000];int f[20];
int vis[1001000];
long long C(int x,int y){return jie[y]*ny[y-x]%mod;}//这里除以x!的部分和后面的约掉了
void dfs(int x,int s,int s1)
{
if (s1>n-2) return ;
if (x==m+1)
{
if (s==0) return;
long long ss=ksm(n-s,n-2-s1)*C(s1,n-2)%mod;
for (int i=1;i<=m;i++) if (f[i]==1) ss=ss*ny[d[i]-1]%mod;
if (s%2==1) ans-=ss; else ans+=ss;ans%=mod;return;
}
f[x]=0;dfs(x+1,s,s1);
if (vis[u[x]]) return;
vis[u[x]]=1;f[x]=1;
dfs(x+1,s+1,s1+d[x]-1);
vis[u[x]]=0;
return;
}
int main()
{
n=read();m=read();if (n==1){printf(m>=1?"0":"1");return 0;}
for (int i=1;i<=m;i++) u[i]=read(),d[i]=read();
ans=ksm((long long)n,n-2);
jie[0]=1;ny[0]=1;jie[1]=1;ny[1]=1;
for (int i=2;i<=n;i++)
{
jie[i]=jie[i-1]*i%mod;
ny[i]=ksm(jie[i],mod-2);
}
dfs(1,0,0);
ans=(ans%mod+mod)%mod;
printf("%lld\n",ans);
return 0;
}