求C(p,q)%MOD(主要处理n!%MOD的求法)

最新推荐文章于 2022-05-01 11:20:32 发布

my_acm

最新推荐文章于 2022-05-01 11:20:32 发布

阅读量1.5k

点赞数

本文链接：https://blog.csdn.net/my_acm/article/details/44138707

版权

#define ll long long
#define maxn 1000010
#define MOD 1000000007
ll f[maxn],ny[maxn];
ll inv(ll a,ll m){
	ll p=1,q=0,b=m,c,d;
	while(b>0){
		c=a/b;
		d=a; a=b; b=d%b;
		d=p; p=q; q=d-c*q;
	}
	return p<0?p+m:p;
}
void init(){
	f[0]=1;
	ny[0]=inv(f[0],MOD);
	for(int i=1;i<maxn;++i){
		f[i]=f[i-1]*i%MOD;
		ny[i]=inv(f[i],MOD);
	}
}
ll C(ll a,ll b){
	if(b<0 || a<0 || a<b) return 0;
	return f[a]*ny[b]%MOD*ny[a-b]%MOD;
}
ll ans=C(p,q);