组合 Lucas定理

组合

Time Limit: 1000MS

Memory Limit: 32768KB

64bit IO Format: %I64d & %I64u

[Submit] [Go Back] [Status]

Description

给出组合数C(n,m), 表示从n个元素中选出m个元素的方案数。例如C(5,2) = 10, C(4,2) = 6.可是当n,m比较大的时候，C(n,m)很大！于是xiaobo希望你输出 C(n,m) mod p的值！

Input

输入数据第一行是一个正整数T,表示数据组数 (T <= 100) 接下来是T组数据，每组数据有3个正整数 n, m, p (1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素数)

Output

对于每组数据，输出一个正整数，表示C(n,m) mod p的结果。

Sample Input

2
5 2 3
5 2 61

Sample Output

1
10

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 #define ll long long
 6 ll power(ll x,ll y)
 7 {
 8    ll p=y+2,ans=1;
 9    while(y)
10    {
11        if(y&1)
12        ans=(ans*x)%p;
13        x=(x*x)%p;
14        y>>=1;
15    }
16    return ans;
17 }
18 ll c(ll n,ll m,ll p)
19 {
20     if(m>n)return 0;
21     ll size=min(m,n-m),i,ans=1;
22     for(i=1;i<=size;i++)
23     ans=ans*((n-i+1)*power(i,p-2)%p)%p;
24     return ans;
25 }
26 ll solve(ll n,ll m,ll p)
27 {
28     if(m==0)return 1;
29     return (c(n%p,m%p,p)*solve(n/p,m/p,p))%p;
30 }
31 int main()
32 {
33     int t;
34     scanf("%d",&t);
35     ll n,m,p;
36     while(t--)
37     {
38         scanf("%I64d%I64d%I64d",&n,&m,&p);
39         printf("%I64d
",solve(n,m,p));
40     }
41 }

View Code

这个问题有个叫做Lucas的定理，定理描述是，如果

那么得到

这样然后分别求，采用逆元计算即可。