0. 写在前面

在程序设计中，可能会碰到多种类型的计数问题，其中不少涉及到组合数的计算，所以笔者写下这么一篇文章，期望能解决一些常规的组合数求模问题。以下部分内容改编自AekdyCoin的《组合数求模》，而且为了感谢他对（懵懂的）笔者的启发，这篇文章的标题与其文章相同。另外，感谢Picks将多项式运算的技巧在中国进行推广，感谢51nod提供了许多有趣的数论题目，感谢fotile96开源了他的FFT模板。 在接下来的内容中，文章将围绕C(n,m)modp进行分析，其中C(n,m)表示从n个人中选出m个人跪sd0061的方案数。

author: skywalkert
original article: http://blog.csdn.net/skywalkert/article/details/52553048
last update time : 2017-03-30

1. 枚举法

这一部分的内容主要是利用基本定义C(n,m)=n!m!(n−m)!=n(n−1)⋯(n−m+1)1⋅2⋯m来进行分析的。

1.1 直接枚举

如果n−m<m，不妨将n−m视作m，所以我们只需要考虑m≤n2的情况。 若1,2,⋯,m在模p意义下有乘法逆元，则考虑直接计算分子、分母在模意义下的值，利用扩展欧几里得算法O(logp)求逆即可，这样做求C(n,m)的复杂度是O(m)的。注意p可以不是质数。 如果需要求C(n,1),C(n,2),⋯,C(n,m)，也可以利用上述方法做到O(mlogp)，这是因为C(n,m)=C(n,m−1)⋅n−m+1m 如果能提前O(m)预处理1,2,⋯,m的逆元，则上述问题可以做到O(m)，这是因为m=x⋅⌊mx⌋+(mmodx)⇒x⋅⌊mx⌋+(mmodx)≡0(modm)⇒x−1≡−⌊mx⌋(mmodx)−1(modm) 注意，当m不为质数时，(mmodx)不一定与m互质，所以上述做法需要有m是质数的条件。

1.2 预处理

由于C(n,m)=n(n−1)⋯(n−m+1)1⋅2⋯m=(n−1)⋯(n−m+1)1⋅2⋯(m−1)(1+n−mm)=C(n−1,m−1)+C(n−1,m),