3390 - 计算系数

1 1 3 1 2

3

Hint

【数据范围】 
对于 30%的数据，有 0≤k≤10； 
对于 50%的数据，有 a = 1，b = 1； 

<span style="font-family:serif;font-size:15.555556297302246px;line-height:20px;background-color:#FFFFFF;">对于 100%的数据，有 0≤k≤1,000，0≤n, m≤k，且 n + m = k，0≤a，b≤1,000,000。</span>



<span style="font-family:serif;font-size:15.555556297302246px;line-height:20px;background-color:#FFFFFF;"><br />




<span style="font-family:serif;font-size:15.555556297302246px;line-height:20px;background-color:#FFFFFF;"><strong>上传者：吕红波</strong></span>

Solution C++

//AUTHOR::STDAFX
//ALGORITHM::Math
 
#define Mod 10007L
 
#include <cstdio>
 
using namespace std;
 
typedef long long ll;
 
int a,b,k,n,m;
ll c[1010][1010];
 
ll fx(ll a,int b)
{
    ll ans=1;
    a%=Mod;
    while(b>0){
        if(b&1){
            ans=(ans*a)%Mod;
        }
        b>>=1;
        a=(a*a)%Mod;
    }
    return ans%Mod;
}
int main(){
    scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
    a%=Mod;b%=Mod;
    c[1][1]=c[1][2]=1;
    for(int i=2;i<=k;i++){
        c[i][1]=1;
        for(int j=2;j<=m+1;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%Mod;
        }
    }
    c[k][m+1]*=fx(a,n);
    c[k][m+1]%=Mod;
    c[k][m+1]*=fx(b,m);
    c[k][m+1]%=Mod;
    printf("%d",c[k][m+1]);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}