【NOIP2012模拟11.3】图的计数

first of all，

时间有保障！！！

这题找规律。
由于重边和自环，所以我们可以添加的边有：n²-(n-1)*(n-2)/2条
然后，由于1~n的最短路径为n-1，所以我们必须先找出n-1条边来保证。
那么我们可以发现：
（n=4）
1–>2–>3–>4
1–>3–>2–>4
共2种
（n=5）
1–>2–>3–>4–>5
1–>2–>4–>3–>5
1–>3–>2–>4–>5
1–>3–>4–>2–>5
1–>4–>2–>3–>5
1–>4–>3–>2–>5
共6种
共有(n-2)!种方案，所以答案还要乘个(n-2)!
总的来说，答案便是：

由于这样弄会时超（或许是我打的丑）

所以我们将C上面的东西变成下面的减去原来的上面的。。。

#include<cstdio>
#define ll long long
#define mo 1000000007
using namespace std;
ll a,b,ans=1,s=1;
int n,m;

ll ksm(ll x,int y)
{
	ll s=1;
	while (y>0)
	{
		if (y & 1) s=s*x%mo;
		x=x*x%mo,y>>=1;
	}
	return s;
}

int main()
{
	freopen("T2.in","r",stdin);
//	freopen("T2.out","w",stdout);
	scanf("%d%d",&n,&m);
	a=n*n-(n-1)*(n-2)/2+m-n,b=a-(m-n+1);
	for (int i=b+1;i<=a;i++) ans=ans*i%mo;
	for (int i=n-1;i<=a-b;i++) s=s*i%mo;
	printf("%lld
",ans*ksm(s,mo-2)%mo);
	return 0;
}