进阶组合数问题

90 阅读 0 评论 60 点赞

我是靠谱客的博主跳跃海燕，最近开发中收集的这篇文章主要介绍进阶组合数问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

进阶组合数问题

如 $C(10^9,10^5)pmod{p},p>10^9$

这时候不能用预处理阶乘+费马小定理做。

而是回归定义：

$C ( n , m ) = n ! m ! ( n − m ) ! = ( n − m + 1 ) × ( n − m + 2 ) ⋯ × n m ! C(n,m)=dfrac{n!}{m!(n-m)!}=dfrac{(n-m+1)times (n-m+2)dotstimes n}{m!}$

复杂度： $O (m + l o g m)$

$l o g m$ 是下面的逆元，使用费马小定理即可。

当 $C (n, m) (m o d p)$ 的 $p$ 较小时，不能用 $k s m +$ 费马小定理了，因为 $n \geq p$ ，在计算式时我们取模 $f a c [n] (m o d p)$ 会变成0，导致答案不对。

所以要利用 $L u c a s$ 定理进行计算！

P6870 [COCI2019-2020#5] Zapina

常规组合数学+dp

P2606 [ZJOI2010]排列计数

小顶堆+树形dp+组合数+Lucas的题，较好

以上就是跳跃海燕为你收集整理的进阶组合数问题的全部内容，希望文章能够帮你解决进阶组合数问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。