CDUTCM——1216任大佬的数学难题
程序员文章站
2022-07-13 13:46:21
...
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}公式
推荐阅读