【组合数】

组合数求法

↑  

Lucas（卢卡斯）定理

↑

Lucas定理是用来求 C(n,m) mod p，p为素数的值。（注意：p一定是素数）

注意：Lucas定理最大的数据处理能力是p在10^5左右

表达式：C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p。（可以递归）

递归方程：(C(n%p, m%p)*Lucas(n/p, m/p))%p。（递归出口为m==0，return 1）

已知C(n, m) mod p = n!/(m!(n - m)!) mod p。显然是除法取模，这里又要用到逆元。

求逆元，用费马小定理。

 

费马小定理

b^（p−1）%p=1

可以直接得到 b 的逆元是 b^(p−2) 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e5;
ll n, m, p, fac[N];
void init()
{
    int i;
    fac[0] =1;
    for(i =1; i <= p; i++)
        fac[i] = fac[i-1]*i % p;
}
ll q_pow(ll a, ll b)
{
    ll  ans =1;
    while(b)
    {
        if(b &1)  ans = ans * a % p;
        b>>=1;
        a = a*a % p;   
    }
    return  ans;
}

ll C(ll n, ll m)
{
    if(m > n)  return 0;
    return  fac[n]*q_pow(fac[m]*fac[n-m], p-2) % p;
}

ll Lucas(ll n, ll m )
{
    if(m ==0)  return 1;
    else return  (C(n%p, m%p)*Lucas(n/p, m/p))%p;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%I64d%I64d%I64d", &n, &m, &p);
        init();
        printf("%I64d
", Lucas(n, m));
    }
    return 0;
}