欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CDUTCM——1216任大佬的数学难题

程序员文章站 2022-07-13 13:46:21
...

CDUTCM——1216任大佬的数学难题

PS:这道题卡了很久,到最后都没有AC,题意很清楚明了,认真分析一下就可以发现就是一个公式C(k,m)a的(k-m)次方乘以b的m次方,但由于k,n,m都很大,所以求C(k,m)时不能用常规的取模运算,具体为什么点这里,大佬讲的很详细,除法不能取模,所以就要用乘法逆元,具体我也不是很懂,记住要这样用就对了

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 10007;
 
int a, b, k, n, m,i;
 
int pow_c(int x, int num){//快速幂模板 
	int res = 1 % mod;
	x %= mod;
	while(num){
		if(num & 1) res = (res * x) % mod;
		x = (x * x) % mod;
		num >>= 1;
	}
	return res;
}
 
int main()
{
 
	while(cin>>a>>b>>k>>n>>m){
	if((n==0&&m==0)||(a==0||b==0)){//特判 
		cout<<"1"<<endl;continue;
	}
    int c[1001];
    c[0]=0; 
	c[1]=1;
	i=1;
	for (i=2; i<=k; i++){
		c[i]=c[i-1]*i%mod;
	}
	c[i]=c[i-1]*i % mod;
	/*for(int i=1;i<=k;i++){
		cout<<c[i]<<" ";
	}
	cout<<endl;*/ 
	int ans=c[k]*pow_c(c[m]*c[n],mod-2)%mod;//求组合数转换要转换为乘法逆元 
	//int ans=c[k]/(c[m]*c[n]%mod);
	//cout<<ans<<endl;
    ans=ans*pow_c(b,k-n)%mod*pow_c(a, n)%mod;
	//printf("%d\n",ans*pow_c(b,k-n)%mod*pow_c(a, n) % mod);
	/*ans=(ans*pow_c(a,n))%mod;
	ans=(ans*pow_c(b,m))%mod;*/
	cout<<ans<<endl;
    }
	return 0;
}

//C(k,m)a^{k-m}b^{m}公式 

相关标签: 逆元 组合数学