卢卡斯定理
卢卡斯定理
文章转载自算法学习笔记(25): 卢卡斯定理 - 知乎 (zhihu.com)，如有侵权，请联系作者删除
卢卡斯定理是一个与组合数有关的数论定理，在算法竞赛中用于求组合数对某质数的模。
这里接下来直接介绍卢卡斯定理，原文章的引入和证明不会涉及qwq。如果想看的话可以看看原作者的文章：算法学习笔记(25): 卢卡斯定理 - 知乎 (zhihu.com)
直接根据定义\(\binom{m}{n}=\frac{m!}{n!(m-n)!}\)计算，很容易溢出，当然我们可以边乘边除，但有点麻烦。于是我们有另外一种思路，利用递推式：\(\binom{m}{n}=\binom{m-1}{n-1}+\binom{m-1}{n}\)（这个递推式可以从杨辉三角中得到），这种方法相对不容易溢出，时间复杂度为\(O(n^2)\)。
但是，然而，实际上，组合数的增长速度是非常快的，如\(\binom{300}{150}\)则有89位数字，比宇宙中的原子数还多。所谓递推不容易溢出，那如果结果本身就溢出了，你又怎么办呢？
所幸算法竞赛中的题目常常会要求将结果对某个质数\(p\)取模，这样一来，溢出的问题就不用太担心了。我们干脆直接回到最原始的方法：\(\binom{m}{n}=\frac{m!}{n!(m-n)!}\)。只不过，现在我们要把除法变成求逆元，也即：\(\binom{m}{n}=m!·inv(n!)·inv[(m-n)!](mod\ p)\)。
模\(p\) 意义下阶乘和逆元都可以\(O(n)\)预处理出来，然后直接\(O(1)\)查询即可（实际上不预处理逆元直接\(O(log\ n)\)求也绰绰有余）。这基本上是最常用的求组合数方法。
绕了一圈，怎么还没提到卢卡斯定理呢？嗯……一般来说，这个方法够用了。偏偏，有时候，\(p\)可能比\(m\)小……
这下麻烦了。如果\(p\)比\(m\)小，就不能保证\(n\)和\(m-n\)的逆元存在了（它们可能是\(p\)的倍数）。当然还是可以用杨辉三角递推，但\(O(n^2)\)还是太不理想。于是，本文的主角——卢卡斯定理终于要出场了。
卢卡斯定理
对于非负整数\(m,n\)和质数\(p\) ，\(\binom{m}{n}\equiv \prod_{i=0}^k \binom{m_i}{n_i}(mod\ p)\) ，其中\(m=m_kp^k+······+m_1p+m_0、n=n_kp^k+······+n_1p+n_0\)是\(m\)和\(n\)的 \(p\)进制展开。
但其实，我们一般使用的是这个可以与之互推的式子：
\(\binom{m}{n}=\binom{m\ mod\ p}{n\ mod\ p}·\binom{\lfloor m/p \rfloor}{\lfloor n/p \rfloor}(mod\ p)\)
当\(m<n\)时，规定\(\binom{m}{n}=0\)（待会讲这个定义的含义）。
就像辗转相除法那样，可以利用这个式子递归求解，递归出口是 \(n=0\)。其实这篇文章只需要这个好记的公式就够了，你甚至可以马上写出卢卡斯定理的板子：
// 需要先预处理出fact[]，即阶乘 |
时间复杂度为\(O(p+log_p\ m)\)，前提是：
阶乘和逆元都采取递推的方式预处理出来，（只需要预处理\(p\)以内的即可），每次调用\(C\)函数都是\(O(1)\)，一共要调用\(log_p\ m\)次，总的时间复杂度即为\(O(p+log_p\ m)\)。
没想到吧o(*≧▽≦)ツ，全文只需要这个代码模板即可（ε=ε=ε=┏(゜ロ゜;)┛逃）。
定理的证明maybe以后会补充？？？因为都是数学符号，看得有点烦了。
