[C++知识库]牛客练习赛92-D与C-(组合数+容斥)

C

题意：
就是有一个图是n个点，然后小A的图包含a个边，小B的图包含b个边，问你一共有多少种方案数使得小A和小B的图中至少包含一个公共边。

思考：
刚开始看到，感觉这貌似有点复杂，但是一看过的人数有点少，其实这个过的人数不能作为评判标准。然后仔细思考一般题目求这种的要么是直接求要么是求反面，正难则反。一共有m = n*(n-1)/2条边，那么总方案数就是C(m,a)*C(m,b)，减去没有公共边的也就是C(m,a)*C(m-a,b)。对吧，对于题目不要怕，就哪些东西。

代码：

int T,n,m,k;
int va[N];
int fact[N],infact[N];

int ksm(int a,int b)
{
	int sum = 1;
	while(b)
	{
		if(b&1) sum = sum*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return sum%mod;
}

void init(int x)
{
	fact[0] = infact[0] = 1;
	for(int i=1;i<=x;i++) fact[i] = fact[i-1]*i%mod;
	infact[x] = ksm(fact[x],mod-2)%mod;
	for(int i=x-1;i>=1;i--) infact[i] = infact[i+1]*(i+1)%mod;
}

int C(int a,int b)
{
	if(a<b) return 0;
	return fact[a]*infact[b]%mod*infact[a-b]%mod;
}

signed main()
{
	IOS;
	init(5e6);
	int a,b;
	cin>>n>>a>>b;
	m = n*(n-1)/2;
	int ans = C(m,a)%mod*C(m,b)%mod;
	int sum = C(m,a)%mod*C(m-a,b)%mod;
	ans = (ans-sum+mod)%mod;
	cout<<ans;
	return 0;
}

总结：
多多思考和尝试。