计算系数

计算系数

n! ≡ n! mod p(mod p)

所以n!的逆元≡(n! mod p)的逆元

这样就可以做这道题了。

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 
 8 const int mod = 10007;
 9 ll a,b,k,n,m;
10 ll ans;
11 
12 ll work1(ll a,ll b){
13     ll s = 1;
14     while(b){
15         if(b&1)s = s*a%mod;
16         b >>= 1;
17         a = a*a%mod;
18     }
19     return s;
20 }
21 
22 ll work2(ll n){
23     ll s = 1;
24     for(int i = 2;i <= n;i++)s = s*i%mod;
25     return s;
26 }
27 
28 ll work3(ll n){
29     return work1(work2(n),mod-2);
30 }
31 
32 int main(){
33     cin >> a >> b >> k >> n >> m;
34     cout << work2(k)*work1(a,n)%mod*work1(b,m)*work3(n)%mod*work3(k-n)%mod << '\n';    
35 return 0;
36 }

 

上一篇:模板 - 扩展大步小步算法


下一篇:Raising Modulo Numbers POJ - 1995 裸快速幂