Lucas定理模板如何应用于特定数论问题？

本文共计521个文字，预计阅读时间需要3分钟。

Lucas定理：用于求组合数C(n, m)模p的值，其中p是素数（n取模p的组合）。公式表示为：Lucas(n, m, p)=C(n % p, m % p) * Lucas(n // p, m // p, p)。Lucas(x, 0, p)=1。简单理解就是将n分块，每块p个元素，分别计算组合数。

Lucas定理：

Lucas定理是用来求 C(n,m) mod p的值,p是素数（从n取m组合，模上p）。
描述为:
Lucas(n,m,p)=C(n%p,m%p)* Lucas(n/p,m/p,p)
Lucas(x,0,p)=1;

简单的理解就是：

以求解n! % p 为例，把n分段，每p个一段，每一段求得结果是一样的。但是需要单独处理每一段的末尾p,2p,...,把p提取出来，会发现剩下的数正好又是(n/p)! ，相当于

划归了一个子问题，这样递归求解即可。

这个是单独处理n！的情况，当然C(n,m)就是n！/(m! *（ｎ－ｍ）！），每一个阶乘都用上面的方法处理的话，就是Lucas定理了

Lucas最大的数据处理能力是p在10^5左右。