Luogu 1313(組合せ数学)(NOIP 2011)
2951 ワード
転送ゲートNOIP 2011 D 2 T 1(高速べき乗,組合せ数,Ferma小定理,逆元)の問題解はコードの前に,最初の行で述べた性質が容易に解決できることが分かった.
/*
(by+ax)^k , (x^n)*(y^m) m=k-n
ans=C(k,n)*(a^n)*(b^(k-n))
*/
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const ll MOD=1e4+7;
ll a,b,k,n,m;
ll fac[1002]={1,1};
ll fpow(ll x,ll y,ll p) {
ll ret=1;
while (y) {
if (y&1) ret=ret*x%p;
y>>=1,x=x*x%p;
}
return ret;
}
int main() {
scanf("%lld%lld%lld%lld%lld",&a,&b,&k,&n,&m);
for (int i=2;i<=1000;++i) fac[i]=fac[i-1]*(ll)i%MOD;
ll comb=fac[k]*fpow(fac[k-n]*fac[n]%MOD,MOD-2,MOD)%MOD;
printf("%lld
",comb*fpow(a,n,MOD)%MOD*fpow(b,k-n,MOD)%MOD);
}