首页 > 其他 > 详细

P3807 【模板】卢卡斯定理

时间:2018-08-24 22:07:06      阅读:178      评论:0      收藏:0      [点我收藏+]

P3807 【模板】卢卡斯定理

\(C_{m + n}^{m} \% p\) ( \(1\le n,m,p\le 10^5\) )


错误日志: 数组开小(洼地hi阿偶我姑父阿贺佛奥UFO爱我帮你)


Pre

好的我们继续恶补数学
首先复习一下 \(O(N)\) 求质数逆元的方法\[inv[1] = 1\]\[inv[i] = (p - p / i) * inv[p \% i] \% p (i >= 2)\]

LL inv[maxn];
void get_inv(LL n){
    inv[1] = 1;
    for(LL i = 2;i <= n;i++)inv[i] = (p - p / i) * inv[p % i] % p;
    }

然后是 \(O(m)\)\(C_{n}^{m} \% p\)\[C_{n}^{m}\% p = \frac{n!}{m!(n - m)!}\% p\]\[=\frac{(n - m + 1) * (n - m +2) * ... * n}{m!}\% p\]\[=(\frac{n - m + 1}{1}\% p) * (\frac{n - m + 2}{2}\% p) * ... * (\frac{n}{m}\% p)\]
其中除法取模可以用上面的逆元计算, 求解一个组合数的复杂度为 \(O(m)\)

P3807 【模板】卢卡斯定理

原文:https://www.cnblogs.com/Tony-Double-Sky/p/9532173.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!