FZU 2020 组合

组合数求模要用逆元，用到了扩展的欧几里得算法。

#include<cstdio>

int mod;

typedef long long LL;

void gcd(LL a,LL b,LL &d,LL &x,LL &y)

{

	if(!b) {d=a;x=1;y=0;}

	else { gcd(b,a%b,d,y,x); y-=x*(a/b);}

}

LL inv(LL a,LL n)

{

	LL d,x,y;

	gcd(a,n,d,x,y);

	return d==1? (x+n)%n:-1;

}

int c(LL n,LL m)

{

	if(n==0||n<m) return 0;

	if(m>n/2) m=n-m;

	LL sum2=1,sum1=1;

	for(LL i=n-m+1; i<=n; i++)

		sum1= sum1*i%mod;

	for(LL i=1; i<=m; i++)

		sum2= sum2*i%mod;

	LL ans;

	ans=sum1*inv(sum2,mod) %mod;

	return ans;

}

int main()

{

	int n,m,T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d%d",&n,&m,&mod);

		printf("%d\n",c(n,m));

	}

}

巴特西

FZU 2020 组合

最新文章

热门文章