Lucas定理学习笔记()

概念

当 \(p\) 是一个质数时,有

实现

引理:

考虑
\[\dbinom{p}{n} \bmod p
\]的取值,注意到展开之后其为如下形式
\[\dbinom{p}{n} = \dfrac{p!}{n!(p-n)!}
\]显然,分子中一定有质因子 \(p\) ,因此仅当 \(n=0\) 或 \(n=p\) 时,\(n!(p-n)!\) 的质因子中有 \(p\) (即 \(p!\) 能被消干净),结果为 \(1\) ,否则结果为 \(0\) ,即
\[\dbinom{p}{n} \bmod p = [n=0 \lor n=p]
\]进而我们可推出
\[\begin{aligned}

(a+b)^p &= \sum_{n=0}^{p}\dbinom{p}{n} a^n b^{p-n}

\\

&\equiv \sum_{n=0}^{p} [n=0 \lor n=p]a^nb^{p-n} &\pmod{p}

\\

&\equiv a^p + b^p &\pmod{p}

\end{aligned}
\]将其推广到二项式,得到
\[\begin{aligned}

(ax^n+by^m)^p &\equiv a^px^{np}+b^py^{mp} &\pmod{p}

\\

&\equiv ax^{np}+by^{mp} &\pmod{p}

\end{aligned}
\]

考虑

的取值,注意到展开之后其为如下形式

显然,分子中一定有质因子 \(p\) ,因此仅当 \(n=0\) 或 \(n=p\) 时,\(n!(p-n)!\) 的质因子中有 \(p\) (即 \(p!\) 能被消干净),结果为 \(1\) ,否则结果为 \(0\) ,即

进而我们可推出

将其推广到二项式,得到

证明:考虑二项式 \((1+x)^n\) 在 \(x^m\) 处的系数模 \(p\) 的结果 \(\dbinom{n}{m} \bmod p\)

利用上述引理,我们可以得到

我们将其看作 \((1+x^p)^{\lfloor \frac{n}{p} \rfloor}\) 与 \((1+x)^{n \bmod p}\) 的卷积,考虑这两个式子对 \((1+x)^n\) 产生的贡献

  • \((1+x^p)^{\lfloor \frac{n}{p} \rfloor}\) 展开后得到的项的次数均为 \(p\) 的倍数
  • \((1+x)^{n \bmod p}\) 展开后得到的项的次数最多为 \(p-1\)

因此,对于 \(x^m\) 的系数仅有一种产生贡献的方案,考虑一下这个贡献怎么来的:就是 \((1+x^p)^{\lfloor \frac{n}{p} \rfloor}\) 中取 \(p\) 的倍数次项,这部分的系数即为 \(\dbinom{\lfloor \dfrac{n}{p} \rfloor}{\lfloor \dfrac{m}{p} \rfloor}\) ,然后再 \((1+x)^{n \bmod p}\) 中取剩余部分,这部分系数即为 \(\dbinom{n \bmod p}{m \bmod p}\)

所以我们可以得出结论(Lucas 定理):

其中 \(p\) 为质数

P3807 【模板】卢卡斯定理/Lucas 定理

#include <cstdio>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7;

ll fac[N];

ll T, n, m, p;

template<class T>
inline T mi(T _a, T _b, T _Mod) {
    T _res = 1;

    for (; _b; _a = _a * _a % _Mod, _b >>= 1)
        (_b & 1) && (_res = _res * _a % _Mod);

    return _res;
}

inline ll C(ll n, ll m) {
    return (m > n) ? 0 : ((fac[n] * mi(fac[m], p - 2, p)) % p * mi(fac[n - m], p - 2, p) % p);
}

inline ll Lucas(ll n, ll m) {
    return m ? (C(n % p, m % p) * Lucas(n / p, m / p) % p) : 1;
}

signed main() {
    scanf("%lld", &T);

    for (; T; --T) {
        scanf("%lld%lld%lld", &n, &m, &p);
        fac[0] = 1;

        for (int i = 1; i <= p; ++i)
            fac[i] = (fac[i - 1] * i) % p;

        printf("%lld\n", Lucas(n + m, n));
    }

    return 0;
}

扩展

Lucas 定理中对于模数要求必须为质数,那么对于模数不是质数的情况,就需要用到 exLucas 定理,即扩展 Lucas 定理

前置芝士:中国剩余定理

第一部分

根据唯一分解定理,将模数 \(p\) 分解

显然,\(q_i^{k_i}\) 两两互质,我们便可以构造如下的同余方程组

用中国剩余定理合并即可得出答案

第二部分

现在的问题转化为了求 \(\dbinom{n}{m} \bmod q^k\) 的值(其中 \(q\) 保证为质数)

注意到

但是 \(m!,(n-m)!\) 这两部分不一定能求出模 \(q^k\) 意义下的逆元,我们可以把上下 \(3\) 个部分中的所有含 \(q\) 项的东西提取出来,即

此时下面的部分与 \(q^k\) 互质,就可以直接求逆元了

第三部分

我们现在考虑求 \(\dfrac{n!}{q^x} \bmod q^k\) 的值

先考虑 \(n! \bmod p^k\) 的值,例如我们要计算 \(19! \bmod 3^2\)

因为

我们注意这个式子的前面两项

  • \(3^6\) 即 \(q^{\lfloor \frac{n}{q} \rfloor}\) ,在递归过程中会被约掉
  • \(6!\) 即 \(\lfloor \frac{n}{q} \rfloor!\) ,递归解决即可

对于中间几个括号的部分,注意到

同理可得后面的每一部分数字的乘积等于前面的数字的乘积,且每个部分相差 \(p^k\) ,用快速幂解决即可

对于最后面残余下的 \(20\) ,我们暴力计算即可

整理一下,我们可以得到

第四部分

我们考虑如何求出第二部分中 \(x,y,z\) 的值

令 \(h(n)\) 为 \(n!\) 中 \(q\) 的次数,即 \(h(n)=x\)

考虑当前求 \(n!\) 中 \(q\) 的倍数产生的贡献和下面求 \(\lfloor \dfrac{n}{q} \rfloor\) 中 \(q\) 的倍数产生的贡献

P4720 【模板】扩展卢卡斯定理/exLucas

#include <cstdio>
typedef long long ll;
using namespace std;

ll n, m, p;

template<class T>
inline T mi(T _a, T _b, T _Mod) {
    T _res = 1;

    for (; _b; _a = _a * _a % _Mod, _b >>= 1)
        (_b & 1) && (_res = _res * _a % _Mod);

    return _res;
}

template<class T>
inline T exgcd(T a, T b, T &x, T &y, T d = 0) {
    return b ? (d = exgcd(b, a % b, y, x), y -= a / b * x) : (x = 1, y = 0, d = a), d;
}

inline ll inv(ll a, ll b) {
	ll x = 0, y = 0;
    return exgcd(a, b, x, y), (x % b + b) % b;
}

inline ll calc(ll n, ll p, ll pk) {
    if (!n)
        return 1;

    ll ans = 1;

    for (ll i = 1; i <= pk; ++i)
        if (i % p)
            ans = (ans * i) % pk;

    ans = mi(ans, n / pk, pk);

    for (ll i = 1; i <= n % pk; ++i)
        if (i % p)
            ans = (ans * i) % pk;

    return ans * calc(n / p, p, pk) % pk;
}

inline ll C(ll n, ll m, ll p, ll pk) {
    if (n < m)
        return 0;

    ll f1 = calc(n, p, pk), f2 = calc(m, p, pk), f3 = calc(n - m, p, pk), cnt = 0;

    for (ll i = n; i; i /= p)
        cnt += i / p;

    for (ll i = m; i; i /= p)
        cnt -= i / p;

    for (ll i = n - m; i; i /= p)
        cnt -= i / p;

    return f1 * inv(f2, pk) % pk * inv(f3, pk) % pk * mi(p, cnt, pk) % pk;
}

inline ll CRT(ll x, ll p, ll mod) {
    return inv(p / mod, mod) * (p / mod) * x;
}

inline ll exLucas(ll n, ll m, ll p) {
    ll t = p, ans = 0;

    for (ll i = 2, k; i * i <= p; ++i) {
        k = 1;

        while (!(t % i))
            k *= i, t /= i;

        ans = (ans + CRT(C(n, m, i, k), p, k)) % p;
    }

    if (t > 1)
        ans = (ans + CRT(C(n, m, t, t), p, t)) % p;

    return ans;
}

signed main() {
    scanf("%lld%lld%lld", &n, &m, &p);
    printf("%lld", exLucas(n, m, p));
    return 0;
}
————————

概念

当 \(p\) 是一个质数时,有

实现

引理:

考虑
\[\dbinom{p}{n} \bmod p
\]的取值,注意到展开之后其为如下形式
\[\dbinom{p}{n} = \dfrac{p!}{n!(p-n)!}
\]显然,分子中一定有质因子 \(p\) ,因此仅当 \(n=0\) 或 \(n=p\) 时,\(n!(p-n)!\) 的质因子中有 \(p\) (即 \(p!\) 能被消干净),结果为 \(1\) ,否则结果为 \(0\) ,即
\[\dbinom{p}{n} \bmod p = [n=0 \lor n=p]
\]进而我们可推出
\[\begin{aligned}

(a+b)^p &= \sum_{n=0}^{p}\dbinom{p}{n} a^n b^{p-n}

\\

&\equiv \sum_{n=0}^{p} [n=0 \lor n=p]a^nb^{p-n} &\pmod{p}

\\

&\equiv a^p + b^p &\pmod{p}

\end{aligned}
\]将其推广到二项式,得到
\[\begin{aligned}

(ax^n+by^m)^p &\equiv a^px^{np}+b^py^{mp} &\pmod{p}

\\

&\equiv ax^{np}+by^{mp} &\pmod{p}

\end{aligned}
\]

考虑

的取值,注意到展开之后其为如下形式

显然,分子中一定有质因子 \(p\) ,因此仅当 \(n=0\) 或 \(n=p\) 时,\(n!(p-n)!\) 的质因子中有 \(p\) (即 \(p!\) 能被消干净),结果为 \(1\) ,否则结果为 \(0\) ,即

进而我们可推出

将其推广到二项式,得到

证明:考虑二项式 \((1+x)^n\) 在 \(x^m\) 处的系数模 \(p\) 的结果 \(\dbinom{n}{m} \bmod p\)

利用上述引理,我们可以得到

我们将其看作 \((1+x^p)^{\lfloor \frac{n}{p} \rfloor}\) 与 \((1+x)^{n \bmod p}\) 的卷积,考虑这两个式子对 \((1+x)^n\) 产生的贡献

  • \((1+x^p)^{\lfloor \frac{n}{p} \rfloor}\) 展开后得到的项的次数均为 \(p\) 的倍数
  • \((1+x)^{n \bmod p}\) 展开后得到的项的次数最多为 \(p-1\)

因此,对于 \(x^m\) 的系数仅有一种产生贡献的方案,考虑一下这个贡献怎么来的:就是 \((1+x^p)^{\lfloor \frac{n}{p} \rfloor}\) 中取 \(p\) 的倍数次项,这部分的系数即为 \(\dbinom{\lfloor \dfrac{n}{p} \rfloor}{\lfloor \dfrac{m}{p} \rfloor}\) ,然后再 \((1+x)^{n \bmod p}\) 中取剩余部分,这部分系数即为 \(\dbinom{n \bmod p}{m \bmod p}\)

所以我们可以得出结论(Lucas 定理):

其中 \(p\) 为质数

P3807 【模板】卢卡斯定理/Lucas 定理

#include <cstdio>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7;

ll fac[N];

ll T, n, m, p;

template<class T>
inline T mi(T _a, T _b, T _Mod) {
    T _res = 1;

    for (; _b; _a = _a * _a % _Mod, _b >>= 1)
        (_b & 1) && (_res = _res * _a % _Mod);

    return _res;
}

inline ll C(ll n, ll m) {
    return (m > n) ? 0 : ((fac[n] * mi(fac[m], p - 2, p)) % p * mi(fac[n - m], p - 2, p) % p);
}

inline ll Lucas(ll n, ll m) {
    return m ? (C(n % p, m % p) * Lucas(n / p, m / p) % p) : 1;
}

signed main() {
    scanf("%lld", &T);

    for (; T; --T) {
        scanf("%lld%lld%lld", &n, &m, &p);
        fac[0] = 1;

        for (int i = 1; i <= p; ++i)
            fac[i] = (fac[i - 1] * i) % p;

        printf("%lld\n", Lucas(n + m, n));
    }

    return 0;
}

扩展

Lucas 定理中对于模数要求必须为质数,那么对于模数不是质数的情况,就需要用到 exLucas 定理,即扩展 Lucas 定理

前置芝士:中国剩余定理

第一部分

根据唯一分解定理,将模数 \(p\) 分解

显然,\(q_i^{k_i}\) 两两互质,我们便可以构造如下的同余方程组

用中国剩余定理合并即可得出答案

第二部分

现在的问题转化为了求 \(\dbinom{n}{m} \bmod q^k\) 的值(其中 \(q\) 保证为质数)

注意到

但是 \(m!,(n-m)!\) 这两部分不一定能求出模 \(q^k\) 意义下的逆元,我们可以把上下 \(3\) 个部分中的所有含 \(q\) 项的东西提取出来,即

此时下面的部分与 \(q^k\) 互质,就可以直接求逆元了

第三部分

我们现在考虑求 \(\dfrac{n!}{q^x} \bmod q^k\) 的值

先考虑 \(n! \bmod p^k\) 的值,例如我们要计算 \(19! \bmod 3^2\)

因为

我们注意这个式子的前面两项

  • \(3^6\) 即 \(q^{\lfloor \frac{n}{q} \rfloor}\) ,在递归过程中会被约掉
  • \(6!\) 即 \(\lfloor \frac{n}{q} \rfloor!\) ,递归解决即可

对于中间几个括号的部分,注意到

同理可得后面的每一部分数字的乘积等于前面的数字的乘积,且每个部分相差 \(p^k\) ,用快速幂解决即可

对于最后面残余下的 \(20\) ,我们暴力计算即可

整理一下,我们可以得到

第四部分

我们考虑如何求出第二部分中 \(x,y,z\) 的值

令 \(h(n)\) 为 \(n!\) 中 \(q\) 的次数,即 \(h(n)=x\)

考虑当前求 \(n!\) 中 \(q\) 的倍数产生的贡献和下面求 \(\lfloor \dfrac{n}{q} \rfloor\) 中 \(q\) 的倍数产生的贡献

P4720 【模板】扩展卢卡斯定理/exLucas

#include <cstdio>
typedef long long ll;
using namespace std;

ll n, m, p;

template<class T>
inline T mi(T _a, T _b, T _Mod) {
    T _res = 1;

    for (; _b; _a = _a * _a % _Mod, _b >>= 1)
        (_b & 1) && (_res = _res * _a % _Mod);

    return _res;
}

template<class T>
inline T exgcd(T a, T b, T &x, T &y, T d = 0) {
    return b ? (d = exgcd(b, a % b, y, x), y -= a / b * x) : (x = 1, y = 0, d = a), d;
}

inline ll inv(ll a, ll b) {
	ll x = 0, y = 0;
    return exgcd(a, b, x, y), (x % b + b) % b;
}

inline ll calc(ll n, ll p, ll pk) {
    if (!n)
        return 1;

    ll ans = 1;

    for (ll i = 1; i <= pk; ++i)
        if (i % p)
            ans = (ans * i) % pk;

    ans = mi(ans, n / pk, pk);

    for (ll i = 1; i <= n % pk; ++i)
        if (i % p)
            ans = (ans * i) % pk;

    return ans * calc(n / p, p, pk) % pk;
}

inline ll C(ll n, ll m, ll p, ll pk) {
    if (n < m)
        return 0;

    ll f1 = calc(n, p, pk), f2 = calc(m, p, pk), f3 = calc(n - m, p, pk), cnt = 0;

    for (ll i = n; i; i /= p)
        cnt += i / p;

    for (ll i = m; i; i /= p)
        cnt -= i / p;

    for (ll i = n - m; i; i /= p)
        cnt -= i / p;

    return f1 * inv(f2, pk) % pk * inv(f3, pk) % pk * mi(p, cnt, pk) % pk;
}

inline ll CRT(ll x, ll p, ll mod) {
    return inv(p / mod, mod) * (p / mod) * x;
}

inline ll exLucas(ll n, ll m, ll p) {
    ll t = p, ans = 0;

    for (ll i = 2, k; i * i <= p; ++i) {
        k = 1;

        while (!(t % i))
            k *= i, t /= i;

        ans = (ans + CRT(C(n, m, i, k), p, k)) % p;
    }

    if (t > 1)
        ans = (ans + CRT(C(n, m, t, t), p, t)) % p;

    return ans;
}

signed main() {
    scanf("%lld%lld%lld", &n, &m, &p);
    printf("%lld", exLucas(n, m, p));
    return 0;
}