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); }