卢卡斯定理

简单来说就是快速计算 \(\binom{n}{m} \bmod p\) 。

卢卡斯定理

如果 \(p\) 是质数，有 \(\binom{n}{m} \equiv \binom{n \bmod p}{m \bmod p} \binom{n/p}{m/p} \pmod{p}\) ，其中 \(n/p\) 和 \(m/p\) 表示整除。

直接递归调用，预处理阶乘，单次询问时间复杂度 \(O(p + \frac{\log n}{\log p})\) 。

扩展卢卡斯

这已经不能算定理了，从头到尾就是一个算法。

对于 \(p\) 不是质数的情况，考虑将 \(p\) 质因数分解，对于每个质因子 \(x^k\) ，求出 \(\binom{n}{m} \bmod x^k\) 后扩展中国剩余定理合并。

那么问题转换为对于质数 \(x\) 和指数 \(k\) 求 \(\binom{n}{m} \bmod x^k\) 。

考虑组合数的通项公式 \(\binom{n}{m} = \frac{n!}{m!(n-m)!}\) ，分别求出 \(n!\), \(m!\), \((n-m)!\) ，特别地，由于它们可能是 \(x\) 的倍数，需要将 \(x\) 单独提出来。 也就是要求 \(n! = x^a b\) 中的 \(a\) 和 \(b\) 。

将 \(n! = 1 \times 2 \times 3 ... \times n\) 中 \(x\) 的倍数单独提出来，这些部分都除掉一个 \(x\) 就是 \(\lfloor \frac{n}{x} \rfloor!\) ，递归计算。 对于其他部分，每 \(x^k\) 分为一块，每一个完整的块的乘积相同，算出一个完整的块的乘积（也就是 \((x^k-1)!\) ）后再算零散部分的乘积即可。

预处理阶乘，单次询问时间复杂度 \(O(p + \frac{\log n}{\log p})\) 。