Lucas 定理 学习笔记

· · 个人记录

C_n^m 求法：

  3. 当 m>n 时，C_n^m=0。
# 插板法 **插板法（Stars and bars）** 是用于求一类给相同元素分组的方案数的一种技巧，也可以用于求一类线性不定方程的解的组数。 **正整数和的数目** 问题一：现有 $n$ 个 完全相同 的元素，要求将其分为 $k$ 组，保证每组至少有一个元素，一共有多少种分法？ 考虑拿 $k - 1$ 块板子插入到 $n$ 个元素两两形成的 $n - 1$ 个空里面。 因为元素是完全相同的，所以答案就是 $\dbinom{n - 1}{k - 1}$。 本质是求 $x_1+x_2+\cdots+x_k=n$ 的正整数解的组数。 非负整数和的数目 问题二：如果问题变化一下，每组允许为空呢？ 显然此时没法直接插板了，因为有可能出现很多块板子插到一个空里面的情况，非常不好计算。 我们考虑创造条件转化成有限制的问题一，先借 $k$ 个元素过来，在这 $n + k$ 个元素形成的 $n + k - 1$ 个空里面插板，答案为 $$\binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}$$ 虽然不是直接求的原问题，但这个式子就是原问题的答案，可以这么理解： 开头我们借来了 $k$ 个元素，用于保证每组至少有一个元素，插完板之后再把这 $k$ 个借来的元素从 $k$ 组里面拿走。因为元素是相同的，所以转化过的情况和转化前的情况可以一一对应，答案也就是相等的。 由此可以推导出插板法的公式： $\dbinom{n + k - 1}{n}$。 本质是求 $x_1+x_2+\cdots+x_k=n$ 的非负整数解的组数（即要求 $x_i \ge 0$）。 **不同下界整数和的数目** 问题三：如果再扩展一步，要求对于第 $i$ 组，至少要分到 $a_i,\sum a_i \le n$ 个元素呢？ 本质是求 $x_1+x_2+\cdots+x_k=n$ 的解的数目，其中 $x_i \ge a_i$。 类比无限制的情况，我们借 $\sum a_i$ 个元素过来，保证第 $i$ 组至少能分到 $a_i$ 个。也就是令 $$x_i^{\prime}=x_i-a_i$$ 得到新方程： $$\begin{aligned} (x_1^{\prime}+a_1)+(x_2^{\prime}+a_2)+\cdots+(x_k^{\prime}+a_k)&=n\\ x_1^{\prime}+x_2^{\prime}+\cdots+x_k^{\prime}&=n-a_1-a_2-\cdots-a_k\\ x_1^{\prime}+x_2^{\prime}+\cdots+x_k^{\prime}&=n-\sum a_i \end{aligned}$$ 其中 $$x_i^{\prime}\ge 0$$ 然后问题三就转化成了问题二，直接用插板法公式得到答案为 $$\binom{n - \sum a_i + k - 1}{n - \sum a_i}$$ **不相邻的排列** $1 \sim n$ 这 $n$ 个自然数中选 $k$ 个，这 $k$ 个数中任何两个数都不相邻的组合有 $\dbinom {n-k+1}{k}$ 种。 # 逆元 若 $a \cdot x \equiv 1 \pmod p$，则称 $x$ 为 $a \bmod b$ 的逆元。 $(a,x,p \in\mathbb{N}^{*})

根据裴蜀定理，a \perp p （互质）。

根据费马小定理，当 p 为质数且逆元存在时，有 a^{p-1} \equiv 1 \pmod p。

所以有 a \cdot a^{p-2} \equiv 1 \pmod p。

则 a^{p-2} 为 a \bmod p 的逆元。

那有可能求 C_n^m 时不互质 (n,m \ge p)，怎么解决？

Lucas 定理

结论：

若 1 \le n \le m 且 p 为质数，则有：

C_n^m \bmod p = (C_{n \bmod p}^{m \bmod p}\times C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor}) \bmod p

证明：

C_m^r=\frac{m!}{r! \cdot (m-r)!}=\frac{(m-1)!}{(r-1)! \cdot (m-r)!}\cdot\frac{m}{r} \equiv 0 \pmod m

根据二项式定理：

(a+b)^n=\sum_{i=0}^{n}C_n^i\cdot a^i\cdot b^{n-i}

有

(1+x)^m=\sum_{r=0}^{m}C_m^r \cdot x^r=1+\sum_{r=1}^{m-1}C_m^r \cdot x^r+x^m \equiv (1+x^m) \pmod m

令 n=am+b，其中 a=\lfloor \frac{n}{m} \rfloor,b=n \bmod m，则有

\begin{aligned}(1+x)^n &=(1+x)^{am}\cdot(1+x)^b \\&= ((1+x)^{m})^a\cdot(1+x)^b\\&\equiv (1+x^m)^a\cdot (1+x)^b \pmod m\\&\equiv(\sum_{i=0}^{a}C_a^i \cdot x^{im})\cdot(\sum_{j=0}^{b}C_b^j \cdot x^{j}) \pmod m\end{aligned}

又根据二项式定理有：

(1+x)^n=\sum_{r=0}^{n}C_n^r\cdot x^r

所以，根据待定系数法，有 r=im+j,i=\lfloor \frac{r}{m} \rfloor,j=r \bmod m,a=\lfloor \frac{n}{m} \rfloor,b=n \bmod m。 带回则有 Lucas 定理。

实现

用于 n,m \ge p，可能 n,m 与 p 不互质的情况。

对于+C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor}， 继续使用 Lucas 定理。

对于C_{n \bmod p}^{m \bmod 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) * Lucas(n / p, m / p, p)) % p;
}

时间复杂度为 O(f(p) + g(n)\log n)，其中 f(n) 为预处理组合数的复杂度，g(n) 为单次求组合数的复杂度。

例题

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

算法见上。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
int farc[N];
inline int Pow(int a,int b,int p){int s=1ll;while(b){if(b&1ll)s=s*a%p;a=a*a%p;b>>=1ll;}return s%p;}
inline int C(int n,int m,int p){if(m>n)return 0;return farc[n]*Pow(farc[m],p-2ll,p)%p*Pow(farc[n-m],p-2ll,p)%p;}
inline int Lucas(int n,int m,int p){if(!m)return 1ll;return 1ll*Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    int T;cin>>T;while(T--){
        int n,m,p;cin>>n>>m>>p;farc[0]=1;
        for(int i=1;i<=p;++i)farc[i]=(farc[i-1]*i)%p;
        cout<<Lucas(n+m,n,p)<<'\n';
    }
    return 0;
}