浅谈Lucas定理
本篇随笔简单讲解一下数学知识部分的Lucas定理。
一、Lucas定理的概念及应用
听说过组合数取模么？
也就是求：
[C_n^m ext{mod} p
]
可以边乘边取模。但是有点慢。
Lucas定理就是解决这个问题的产物。
其内容是：（p为质数）
[C_n^m=C_{n ext{mod} p}^{m ext{mod} p} imes C_{ndiv p}^{mdiv p}quad ( ext{mod} p)
]
二、Lucas定理的理解与实现
实现的时候，只需要对这个东西继续递归调用Lucas定理即可。也就是，对于(C_{ndiv p}^{mdiv p})继续调用，最后就会出现一个连乘。
于是我们发现，这个东西又除又模的，很像进制拆解。
没错。
也就是说，这个Lucas定理就相当于把(n,m)变成了(p)进制数，然后对(p)进制下的每一位都计算组合数，最后乘起来。
三、Lucas定理的证明
略。