Lucas 学习笔记

· · 个人记录

1. 前置知识

扩展欧几里得：对于不完全为 0 的非负整数 a,b，\gcd(a,b) 表示 a,b 的最大公约数，必然存在整数对 x,y 使得 \gcd(a,b)=ax+by。

费马小定理：a^{p-1}\equiv 1\pmod p

逆元：

求解公式 (a/b)\% p 时，因 b 可能会过大，会出现爆精度的情况，所以需变除法为乘法：

设 c 是 b 的逆元，则有 b\times c≡1\pmod p；

则 (a/b)\%p\equiv (a/b)\times 1\%p\equiv (a/b)\times b\times c\%p\equiv a\times c \pmod p;

即 a/b\equiv a\times c\pmod p。

公式：

b\times c\equiv 1\pmod p b\equiv c^{-1} \pmod p

费马小定理求逆元：因为 x^{p-1}\equiv 1\pmod p，提取一个 x 得 x^{p-1}\equiv x\times x^{p-2}\equiv 1\pmod p，即 x 的逆元为 x^{p-2}。

注意：根据费马小定理，x 与 p 互质时才可以用此方法。

扩展欧几里得求逆元：从 b\times c\equiv 1\pmod m 可以得出关系式：k\times m+1=b\times c\Rightarrow b\times c+(-k)\times m=1 完全符合扩展欧几里得算法。

线性递推求解逆元：

inv[1]初始化为1
递推公式为：inv[i]=(p-p/i)*inv[p%i]%p
//其中p为模数，i为要求逆元的数，inv[i]为i的逆元

证明：

设 t=m/i,k=m\%i；

\Rightarrow t\times i+k\equiv 0\pmod m \Rightarrow -t\times i-k\equiv 0\pmod m \Rightarrow -t\times i\equiv k\pmod m \Rightarrow -t\times 1/k\equiv 1/i\pmod m \because 1/i\times i\equiv 1\pmod m \therefore$ 可以用 $inv[i]$ 代替 $1/i \Rightarrow -t\times inv[k]\equiv inv[i]\pmod m

再替换 t,k 得

\Rightarrow inv[i]=(m-m/i)\times inv[m\%i]%m

公式得证。

二项式定理：

(a+b)^n=\sum_{k=0}^{n}C_{n}^{k}a^{n-k}b^{k}

证明：

假设当 n=m 的时候二项式定理成立，那么当 n=m+1 时：

(a+b)^{m+1}\\ =a(a+b)^{m}+b(a+b)^{m}\\ =a\sum_{k=0}^{m} C_{m}^{k}a^{m-k}b^{k}+b\sum_{k=0}^{m} C_{m}^{k}a^{m-k}b^{k}\\ =a(\sum_{k=1}^{m} C_{m}^{k}a^{m-k}+a^{m})+b(\sum_{k=1}^{m-1} C_{m}^{k}a^{m-k}b^{k}+b^{m})\\ =a^{m+1}+b^{m+1}+\sum_{k=1}^{m}C_{m}^{k}a^{m-k+1}+\sum_{k=1}^{m}C_{m}^{k-1}a^{m-k+1}b^{k}\\ =a^{m+1}+b^{m+1}+\sum_{k=1}^{m}[(C_{m}^{k}+C_{m}^{k-1})]a^{m-k+1}b^{k}\\ =a^{m+1}+b^{m+1}+\sum_{k=1}^{m}C_{m+1}^{k}a^{m-k+1}b^{k}\\ =\sum_{k=0}^{0}C_{m+1}^{k}a^{m-k+1}b^{k}+\sum_{k=m+1}^{m+1}C_{m+1}^{k}a^{m-k+1}b^{k}+\sum_{k=1}^{m}C_{m+1}^{k}a^{m-k+1}b^{k}\\ =\sum_{k=0}^{m+1}C_{m+1}^{k}a^{m+1-k}b^{k}\\ =\sum_{k=0}^{m}C_{n}^{k}a^{n-k}b^{k}

2. Lucas定理

概述：

对于非负整数 m,n 和质数 p，组合数 C_{n}^{m}\equiv \prod_{i=0}^{k}C_{n_{i}}^{m_{i}}\,\,\,\,\,\,\,\,\,\,\,\,\pmod p\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,式1

其中 n 的 k 位 p 进制展开式：n=n_{k}p^{k}+...+n_{1}p^{1}+n_{0}p^{0}

其中 m 的 k 位 p 进制展开式：m=m_{k}p^{k}+...+m_{1}p^{1}+m_{0}p^{0}

式1成立，则：C_{n}^{m}=C_{n_{k}}^{m_{k}}\times ...\times C_{n_{1}}^{m_{1}}\times C_{n_{0}}^{m_{0}}=\prod_{i=1}^{k}C_{n_{i}}^{m_{i}}\times C_{n_{0}}^{m_{0}}

其中 \prod_{i=1}^{k}C_{n_{i}}^{m_{i}}=C_{\left \lfloor \frac{n}{p} \right \rfloor}^{\left \lfloor \frac{m}{p} \right \rfloor}\,\,\,,C_{n_{0}}^{m_{0}}=C_{n \mod p}^{m \mod p} \,\,\,\,\,\,\,\,\,\,\,\,\pmod p

所以可得 C_{n}^{m}=C_{\left \lfloor \frac{n}{p} \right \rfloor}^{\left \lfloor \frac{m}{p} \right \rfloor}\times C_{n \mod p}^{m \mod p}\,\,\,\,\,\,\,\,\,\,\,\,\pmod p\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,式2

当 n<m 时，C_{n}^{m}=0。

证明：

设 x 是任意小于 p 的正整数，则：C_{p}^{x}=\frac{p!}{x!(p-x)!}=\frac{p\cdot (p-1)!}{x\cdot (x-1)!\cdot (p-x)!}=\frac{p}{x}\cdot C_{p-1}^{x-1}

由于 x<p 且 p 为质数，所以 x 存在模 p 意义下的逆元，故：C_{p}^{x}\equiv p\cdot inv(x)\cdot C_{p-1}^{x-1}\,\,\,\,\,\,\,\,\,\,\,\,\pmod p

显然等号右边的式子是 p 的倍数，故 C_{p}^{x}\equiv 0\,\,\,\,\,\,\,\,\,\,\,\,\pmod p

以上证明当 x<p 时，C_{p}^{x}=0\,\,\,\,\,\,\,\,\,\,\,\,\pmod p。

已知二项式定理：(1+x)^{n}=\sum_{i=0}^{n}C_{n}^{i}x^{i}。由于 (1+x)^{p}=\sum_{i=0}^{p}C_{p}^{i} 对于 i\in [1,p-1] 的项模 p 都为 0，所以 (1+x)^{p}\equiv C_{n}^{n}x^{p}+c_{n}^{0}x^{0}\equiv x^{p}+1\,\,\,\,\,\,\,\,\,\,\,\,\pmod p。

设 \begin{cases} \left \lfloor \frac{m}{p} \right \rfloor=q_{m}\\\left \lfloor \frac{n}{p} \right \rfloor=q_{n} \end{cases}，\begin{cases} m\mod p=r_{m}\\n\mod p=r_{n} \end{cases}，则 \begin{cases} m=q_{m}\cdot p+r_{m}\\n=q_{n}\cdot p+r_{n} \end{cases}。

则：

(1+x)^{n}\\ =(1+x)^{q_{n}\cdot p+r_{n}}\\ =[(1+x)^{p}]^{q_{n}}\cdot (1+x)^{r_{n}}\equiv (1+x^{p})^{q_{n}}\cdot (1+x)^{r_{n}}\\ =\sum_{i=0}^{q_{n}}C_{q_{n}}^{i}x^{i\cdot p}\sum_{j=0}^{r_{n}}C_{r_{n}}^{j}x^{j}\\ =\sum_{i=0}^{q_{n}}\sum_{j=0}^{r_{n}}C_{q_{n}}^{i}C_{r_{n}}^{j}x^{i\cdot p+j}\,\,\,\,\,\,\,\,\,\,\,\,\pmod p

则设 k=i\cdot p+j,k\in[0,n]，得 (1+x)^{n}\equiv \sum_{k=0}^{n}C_{q_{n}}^{\left \lfloor \frac{k}{p} \right \rfloor}C_{r_{n}}^{k\mod p}x^{k}\,\,\,\,\,\,\,\,\,\,\,\,\pmod p

由二项式定理，得 (1+x)^{n}\equiv \sum_{k=0}^{n}C_{n}^{k}x^{k} \equiv \sum_{k=0}^{n}C_{q_{n}}^{\left \lfloor \frac{k}{p} \right \rfloor}C_{r_{n}}^{k\mod p}x^{k}\,\,\,\,\,\,\,\,\,\,\,\,\pmod p

令 k=m，等式两边消除 x^{k} 单取二项式系数得 C_{n}^{m}\equiv C_{q_{n}}^{\left \lfloor \frac{m}{p} \right \rfloor}C_{r_{n}}^{m\mod p}=C_{\left \lfloor \frac{n}{p} \right \rfloor}^{\left \lfloor \frac{m}{p} \right \rfloor}C_{n\mod p}^{m\mod p}

定理得证。

3.总结

（自我感觉）挺难的一个算法。

参考资料：

Shaoxing No.1 Middle School 内部学习资料

https://www.cnblogs.com/Lrefrain/p/11353765.html

https://blog.csdn.net/jk_chen_acmer/article/details/79305269

https://blog.csdn.net/jk_chen_acmer/article/details/79297068

https://blog.csdn.net/jk_chen_acmer/article/details/79271069

模板题：P3807

套公式即可。

#include<bits/stdc++.h>
using namespace std;
long long t;
int ksm(long long a,long long b,long long p)
{
    long long ans=1,x=a;
    while(b)
    {
        if(b&1) ans*=x,ans%=p;
        x*=x;x%=p;b>>=1;
    }
    return ans%p;
}
long long C(long long m,long long n,long long p)
{
    if(n<m) return 0;
    if(m>n-m) m=n-m;
    long long a=1,b=1;
    for(long long i=0;i<m;++i) {a=a%p*(n-i)%p;b=b%p*(i+1)%p;}
    return a%p*ksm(b,p-2,p)%p;
}
long long lucas(long long n,long long m,long long p)
{
    if(m==0) return 1;
    return C(n/p,m/p,p)%p*C(n%p,m%p,p)%p;
}
void work()
{
    long long n,m,p;
    cin>>n>>m>>p;
    cout<<lucas(n,n+m,p)%p<<"\n";
}
int main()
{
    cin>>t;
    while(t--) work();
    return 0;
}

4.扩展

扩展卢卡斯

待填坑。