题解 | #D 与 C#

内测一血。

这道题原来数据范围巨大，要用 Lucas 定理，然后在内测阶段被我们几个参与内测的鲨下来难度了 /youl

好了来谈谈这道题的解法。

一个无向图一共是 $m={\displaystyle \frac{n\times (n-1)}{2}}m=\backslash dfrac\{n\backslash times(n-1)\}\{2\}$ 条边，他问的是 $AA$ 和 $BB$ 至少有一条公共边，这就很难算了，可以考虑容斥一下，用 所有方案数 减去 没有公共边 的方案数。

第一个很好算，根据乘法原理和组合数，答案就是 $mm$ 个边里面选 $aa$ 个 $\times \backslash times$ $mm$ 个边里面选 $bb$ 个。

第二个也不难算，无非就是 $mm$ 个边里面钦定下来 $aa$ 个，那么后面选 $\in B\backslash in\; B$ 的边的时候不选它们就是了，也就是在剩下来的 $m-am-a$ 个边里面选 $bb$ 个，还是乘法原理去就好。

最终答案就是 $C(m,a)\times C(m,b)-C(m,a)\times C(m-a,b)C(m,a)\backslash times\; C(m,b)-C(m,a)\backslash times\; C(m-a,b)$。

下面的代码使用了 Lucas 定理，缩小数据范围后可以不使用。

signed main(signed argc,char**argv){
	n=in();
	int a=in(),b=in();
	m=n*(n-1)/2;
	p=10007;
	fac[0]=1;
	for(int i=1;i<=p;++i)
		fac[i]=(fac[i-1]*i)%p;
	int s1=Lucas(m,a)*Lucas(m,b)%p;
	int s2=Lucas(m,a)*Lucas(m-a,b)%p;
	wr(((s1-s2)%p+p)%p);
}
int Lucas(int n,int m){
	if(!m)return 1;
	return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}
int C(int n,int m){
	if(m>n)return 0;
	return (fac[n]*quick_mod(fac[m],p-2,p)%p*
	quick_mod(fac[n-m],p-2,p)%p);
}
int quick_mod(int a,int b,int p){
    int s=1;
    while(b){
        if(b&1)s=s*a%p;
        a=a*a%p;b>>=1; 
    }
    return s;
}