Lucas定理及应用
额，前两天刚讲了数据结构，今天我来讲讲组合数学中的一种奇妙优化——Lucas
先看这样一个东西
没学过lucas的肯定会说：还不简单？处理逆元，边乘边膜呗
是，可以，但注意一下数据范围
你算这一次，你需要跑25000下
那么你如果求C199999 1~C199999 52222 呢？
你会发现你的复杂度上天了
所以我们会用到一个神奇的定理：Lucas定理
定理内容如下：
Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)
不好玩，是吗？
那么我来证明一下
由二项式定理可得，cmn等于（x+1）^m中n次项的系数
那么我们按Lucas展开
原式=(x+1)^(p^k*ak)*(x+1)^(p^(k-1)*a(k-1))*……*(x+1)^(p*a1)+(x+1)^(1*a0)
=[(x+1)^(p^k)]^ak……
由费马小定理可知，其%p后可转化为 (x+1)^ak*(x+1)^a(k-1)*……*(x+1)^a1*(x+1)^a0
原题转化为求上式的n次项的系数
同理，由于每一项已经消去了p^k次方 故即求每一项中的bk次项系数 即为Lucas
有什么用呢？
以前的组合数，我们一位一位地算（累死了）
现在的组合数，我们只用算%p出来的（这不就是log p m次吗？）
O(n)到O（logn）
大有长进啊
大家应该都会
下面看几道好题
combination【bzoj2928】
裸的板子，不说什么
《瞿葩的数字游戏》T3-三角圣地
带了预处理阶乘的Lucas
[SHOI2015]超能粒子炮·改
lucas合并
礼物，古代猪文
扩展Lucas
版权声明：本文为ztz11原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。