组合数取模

 

给出N,M,P，求C(N,M) Mod P
1<=M<=N<=10^6,1<=P<=10^5,P可能为合数

Input

一行给出N,M,P

Output

如题

Sample Input

5 2 3

Sample Output

1

sol:前面在组合数取模——计算系数一题中，讲了两种组合数取模的方法。
但本题数据，（1）如用时间复杂度为O(n^2)的求杨辉三角的方法，要超时；(2)用求逆元的方法，m,n的值要小于p，但本题数据m,n的范围大于p。
本题我们用分解质因子的方法，c(n,m)=n!/(m!*(n-m)!)，我们把如n!写成2^a1*3^b1*5^c1...的形式，那么c(n,m)就可以写为2^(a1-a2-a3)*3^(b1-b2-b3)*...

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 typedef long long LL;
 6 const int N = 200005;
 7 bool prime[N];
 8 int p[N];
 9 int cnt;
10 void isprime()
11 {
12     cnt = 0;
13     memset(prime,true,sizeof(prime));
14     //设所有数字都是质数 
15     for(int i=2; i<N; i++)
16     {
17         if(prime[i]) //如果i是质数 
18         {
19             p[cnt++] = i;  //将数字i放到一个数组中 
20             for(int j=i+i; j<N; j+=i) //i的若干倍都不是质数 
21                 prime[j] = false;
22         }
23     }
24 }
25
26 LL quick_mod(LL a,LL b,LL m)
27 //快速幂求a^b mod m
28 {
29     LL ans = 1;
30     a %= m;
31     while(b)
32     {
33         if(b & 1)
34         {
35             ans = ans * a % m;
36             b--;
37         }
38         b >>= 1;
39         a = a * a % m;
40     }
41     return ans;
42 }
43
44 LL Work(LL n,LL p)
45 //1到N之间所有数字，有多少个数字可分解出质因子p 
46 {
47     LL ans = 0;
48     while(n)
49     {
50         ans += n / p;
51         n /= p;
52     }
53     return ans;
54 }
55
56 LL Solve(LL n,LL m,LL P)
57 //N!,m!,(n-m)!这三个数字进行质因子分解 
58 {
59     LL ans = 1;
60     for(int i=0; i<cnt && p[i]<=n; i++)
61     //枚举质因子 
62     {
63         LL x = Work(n, p[i]);
64         LL y = Work(n - m, p[i]);
65         LL z = Work(m, p[i]);
66         x -= (y + z);
67         ans *= quick_mod(p[i],x,P);
68         //依次计算p[i]^x mod P，并进行相乘
69         ans %= P;
70     }
71     return ans;
72 }
73
74 int main()
75 {
76     int T;
77     isprime();
78     LL n,m,P;
79     cin>>n>>m>>P;
80     cout<<Solve(n,m,P)<<endl;
81     return 0;
82 }