[数学] Jzoj P3085 图的计数

Description

在观察完第一个作业之后你终于开始观察第二个作业了，第二个作业十分无聊，就只是一道题目。

询问有多少个N个点，M条边的有向图，从1号点到达N号点需要经过至少N-1条边。该有向图中可以包含重边和自环。

Input

第一行两个整数N,M。

Output

仅一个整数表示答案 mod (10^9+7）。

Sample Input

2 2

Sample Output

Hint

对于30%的数据 N<=5,M<=10

对于60%的数据 N<=80,M<=3000

对于100%的数据 1<=N<=10000 1<=M<=100000

题解

首先，我们可以看到在这个n个点m条边的有向图中，最短路径是n-1
那么我们已经确定了n-1条边，剩下的边肯定不能使最短路径变得更短
简单点来说，就是剩下的边不能在n-1最短路径上的边里两两连边，这样的话方案数就很容易算出来了，C(n-1,2)=(n-1)(n-2)/2
那么我们就可以把剩下的m-n+1条边随便放入图中，那么就有N*N-C(n-1,2)的一种情况
就相当与把n个球放入m个挡板中C(n-m+1,n)
这样总的答案就是C(n*n-C(n-1,2)-1+m-(n-1),m-(n-1))
最后的话，答案还要乘上(n-2)!

代码

 1 #include <cstdio>
 2 #define ll long long
 3 using namespace std;
 4 ll n,m,ans=1,mx,j,f,x,y,z,r,mo=1e9+7;
 5 ll ksm(ll a,ll b){ for (r=1;b;b>>=1,a=a*a%mo) if (b&1) r=r*a%mo; return r; }
 6 int main()
 7 {
 8     scanf("%lld%lld",&n,&m);
 9     if (m<n-1) { printf("0
"); return 0; }
10     for (ll i=1;i<=n-2;i++) ans=ans*i%mo;
11     mx=(n+n-1+((n-1)*n)/2%mo)%mo,m-=n-1,f=1;
12     for (ll i=1;i<=mx-1+m;i++,f=f*i%mo)
13         if (i==mx-1+m) x=f;
14         else if (i==mx-1) y=f;
15         else if (i==m) z=f;
16     ans=ans*x%mo*ksm(y,mo-2)%mo*ksm(z,mo-2)%mo,printf("%lld
",ans);
17 }