组合数的三种常规精度求法

本节介绍组合数的三种常规精度求法，用以应对不同类型的数据

看一下第一种数据类型

分析数据范围发现特点是ab都较小，问询数较多 这种数据比较适合用DP打表预处理出所有的Cab，然后根据问询输出

递推使用公式

{n \choose k } = {n - 1 \choose k - 1} + {n - 1 \choose k}

一个感性好用的理解： 对于要从n个苹果里选出k个的选法，由两种情况构成：对于任意一个苹果，我们可以选择，然后从n – 1个苹果里选k – 1个，或者不选，即从 n – 1个苹果里选k个

直接DP，初始化出边界为1的情况然后推出一个三角形区域即可 如果不理解用Excel画一下会很有帮助

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2010, MOD = 1e9 + 7;
int c[N][N];
void init()
{
    // C[a][b] = C[a - 1][b - 1] + C[a][b - 1];
    for(int i = 0; i < N; i++)
        c[0][i] = 1;
    for(int i = 1; i < N; i++)
        for(int j = i; j < N; j++)
            c[i][j] = (c[i - 1][j - 1] + c[i][j - 1]) % MOD;
}

int main()
{
    // ios::sync_with_stdio(false);
    int n;
    scanf("%d", &n);

    init();

    while(n--)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", c[b][a]);
    }
    return 0;
}

需要特别注意的一点是，我在写Cab时，ab的顺序比较随意，看代码时请留意一下

看一下第二种数据类型

显然无法处理出所有Cab来打表解决问题

此时可以考虑从公式方面解决

{a \choose b} = \frac{a!}{b!(a-b)!} 

而题目要求结果对1e9+7取模，可以考虑打表活的范围内ab的阶乘和ab mod p的逆，以此来解决问题

需要注意的是，本题模数p是质数，所以求逆首选快速幂（费马小定理）法，不了解乘法逆元和费马小定理的可以看我这篇文章

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7;
const int N = 1e5 + 10;

ll fact[N], infact[N]; // 分别储存n的阶乘和n的阶乘mod MOD的逆

ll qmi(ll x, ll q, ll m)
{
    // x ^ q % m， 快速幂模板
    ll res = 1;
    while (q)
    {
        if (q & 1)
            res = (res * x % m) % m;
        q >>= 1;
        x = (x * x % m) % m;
    }
    return res;
}

void init()
{
    // 出始化出n的阶乘和n的阶乘mod MOD的逆
    // 1 <= n <= 1e5
    ll x = 1;
    fact[0] = 1, infact[0] = 1;
    for (int i = 1; i <= (int)1e5; i++)
    {
        x = (x * i) % MOD;
        fact[i] = x;
        infact[i] = qmi(x, MOD - 2, MOD);
    }
}

ll getC(ll a, ll b)
{
    // C(b, a) = a! / (b! (a- b)!)
    return ((fact[a] * infact[b] % MOD) * infact[a - b] % MOD) % MOD;
}

int main()
{
    //ios::sync_with_stdio(false);
    init();
    int n;
    scanf("%d", &n);
    while (n--)
    {
        ll a, b;
        scanf("%lld %lld", &a, &b);
        printf("%lld\n", getC(a, b));
    }
    return 0;
}

来看第三种数据类型

这种数据类型的特点是模数很小，ab都很大 此时需要用到Lucas定理来对数据的范围进行处理 Lucas定理/卢卡斯定理:

{a \choose b} \equiv {a\%p \choose b\%p} \cdot {{\left \lfloor \frac{a}{p}  \right \rfloor }  \choose{{\left \lfloor \frac{b}{p}  \right \rfloor }}} \quad (mod \quad p)

证明这里不关心，有兴趣可以b站搜索一下相关证法

利用Lucas定理可以将问题规模变小，方便解题 在写代码时候要特别注意取模问题，因为数据很大，相乘时候非常容易溢出

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll qmi(ll a, ll k, ll p)
{
    // a ^ p % q， 快速幂模板
    ll res = 1;
    while (k)
    {
        if (k & 1)
            res = (res * a % p) % p;
        k >>= 1;
        a = (a * a % p) % p;
    }
    return res;
}

ll C(ll a, ll b, ll p)
{
    // C(a, b) = a! / (b!(a - b)!) = (a * (a - 1) * (a - 2) * ... * (a - b + 1)) / b!
    if(b > a)    return 0; //这一行特判加上， 下一行其实可有可无
    if(b == a)  return 1;
    ll res = 1;
    // 循环看不懂的话多看看上面这段公式， 其实就是手算时候的方法， 不要被定义搞了
    for (int i = 1, j = a; i <= b; i++, j--)
    {
        res = (res * j) % p;
        res = (res * qmi(i, p - 2, p)) % p;
    }
    return res;
}

ll lucas(ll a, ll b, ll p)
{
    // 递归处理
    if(a < p && b < p)
        return C(a, b, p);
    // 对p取模后肯定都小于p了，所以用C， 而整除p之后不一定小于p， 还需要递归
    // return的取模非常麻烦， 但是一定要注意
    return (C(a % p, b % p, p) * lucas(a / p, b / p, p) % p) % p;
}

int main()
{
    //ios::sync_with_stdio(false);
    int n;
    cin >> n;
    while (n--)
    {
        ll a, b, p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }
    return 0;
}