fzu 2020 组合数对素数取模lucas定理

由于p是素数，计算逆元可以借助费马小定理，用扩展欧几里得也可以，不过预计比快速幂慢吧。

代码如下：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 
 6 int pow_mod( int a, int n, int mod )
 7 {
 8     int ans = 1, w = a % mod;
 9     while ( n )
10     {
11         if ( n & 1 )
12         {
13             ans = (ll) ans * w % mod;
14         }
15         w = (ll) w * w % mod;
16         n = n >> 1;
17     }
18     return ans;
19 }
20 
21 int c( int n, int m, int p )
22 {
23     int ans = 1;
24     for ( int i = 1; i <= m; i++ )
25     {
26         int a = n - m + i, b = i;
27         a = a % p, b = b % p;
28         ans = (ll) ans * ( (ll) a * pow_mod( b, p - 2, p ) % p ) % p;
29     }
30     return ans;
31 }
32 
33 int lucas( int n, int m, int p )
34 {
35     int ans = 1;
36     while ( n )
37     {
38         ans = (ll) ans * c( n % p, m % p, p ) % p;
39         n = n / p, m = m / p;
40     }
41     return ans;
42 }
43 
44 int main ()
45 {
46     int t;
47     cin >> t;
48     while ( t-- )
49     {
50         int n, m, p;
51         cin >> n >> m >> p;
52         cout << lucas( n, m, p ) << endl;
53     }
54     return 0;
55 }

参考于：http://m.blog.csdn.net/blog/acdreamers_11109/8037918