洛谷 P1313 [NOIP2011 提高组] 计算系数 (组合数取模)

 //1007为质数，运用二项式展开，且对于1-1006与1007互质，用费马小定理可以求组合数的分母mod1007，也就是求逆元
 1 #include
 2 using namespace std;
 3 const int mod=1e4+7;
 4 int a,b,k,n,m;
 5 int quipow(int a,int n)
 6 {
 7     int ans=1%mod;
 8     while(n)
 9     {
10         if(n&1)ans=1ll*ans*a%mod;
11         n>>=1;
12         a=1ll*a*a%mod;
13     }
14     return ans;
15 }
16 int jc(int n)
17 {
18     int ans=1%mod;
19     for(int i=1;i<=n;i++)
20     ans=1ll*ans*i%mod;
21     return ans;
22 }
23 int main()
24 {
25     cin>>a>>b>>k>>n>>m;
26     int a_pow=quipow(a,n),b_pow=quipow(b,m);
27     int a_j=jc(k),b_j=1ll*jc(k-n)*jc(n)%mod;
28     int t=quipow(b_j,mod-2);
29     int ans=1ll*a_pow*b_pow*t*a_j%mod;
30     cout<endl;
31     return 0;
32 }