数论 · Lucas 定理

· · 个人记录

前言

在 A 了 Lucas 模板之后，十几天才弄懂证明。

UPDATE

定理

组合数取模

对于整数 a,\ b,\ p（p 为素数），a=\sum_{i=0}^ka_ip^i,\ b=\sum_{j=0}^{k}b_jp^j。

简而言之就是把 a,\ b 转化为 p 进制下的数。

有 \dbinom{a}{b} \equiv \dbinom{a_k}{b_k} * \dbinom{a_{k-1}}{b_{k-1}}\cdots \equiv \prod_{i=0}^k \dbinom{a_i}{b_i} \pmod p。

证明

先提出一个用二项式定理证的一个柿子 (1+x)^p \equiv 1+x^p \pmod p。

都要看烂了，就不证了。

根据 a 的 p 进制下拆分，我们有：(1+x)^p=(1+x)^{a_0}* ((1+x)^{p})^{a_1}* ((1+x)^{p^2})^{a_2}* \cdots ((1+x)^{p^k})^{a_k}。

再结合最上面的柿子，就有 (1+x)^p \equiv (1+x)^{a_0}* (1+x^p)^{a_1}* (1+x^{p^2})^{a_2}* \cdots * (1+x^{p^k})^{a_k} \pmod p。

然后我们考虑左边的柿子，其中 x^b 次方的系数就是 C_a^b。

又 b=\sum_{j=0}^{k}b_jp^j，

所以在右边的每一个括号的次数 a_k 中，我们挑 b_k 次，再乘起来，就可以得到 x^b 项。对于第 k 个括号，就有 \dbinom{a_k}{b_k} 中挑 b_k 次的方式。

这样就得到了 \dbinom{a}{b} \equiv \dbinom{a_0}{b_0}* \dbinom{a_1}{b_1}* \cdots * \dbinom{a_k}{b_k} \pmod p。

按照这个柿子，我们就可以递归求解 \dbinom{a}{b} \% \ p了。

证毕！

代码

其中，\dbinom{n}{m} = \dfrac {n!}{m!* (n-m)!}，这个可以预处理出每个数的阶乘再带入求值，除法直接用 逆元 即可。

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

#define int long long
#define rint register int
const int maxn = 1e5 + 5;
int T, n, m, p;
int a[maxn];

inline int read ()
{
    int x = 1, s = 0;
    char ch = getchar ();
    while (ch < '0' or ch > '9') {if (ch == '-') x = -1; ch = getchar ();}
    while (ch >= '0' and ch <= '9') s = s * 10 + ch - '0', ch = getchar ();
    return s * x;
}

inline int pow (int x, int t)
{
    int res = 1;
    x %= p;
    while (t >= 1)
    {
        if (t & 1) 
            res = res * x % p, t -= 1;
        t /= 2, x = x * x % p; 
    }
    return res;
}

inline int inv (int x)
{
    return pow (x, p - 2);
}

inline int cm (int n, int m)
{
    if (m > n) return 0;
    return ((a[n] * inv (a[m])) % p * inv (a[n - m]) % p);
}

inline int lucas (int a, int b)
{
    if (!b) return 1;
    return cm (a % p, b % p) * lucas (a / p, b / p) % p;
}

signed main ()
{
    a[0] = 1;
    T = read ();
    while (T--)
    {
        n = read (), m = read (), p = read ();
        for (rint i (1); i <= p; ++i) 
            a[i] = a[i - 1] * i % p;
        printf ("%lld\n", lucas (n + m, n));
    }
    return 0;
}

——End——