摘要：
以下内容转自：http://blog.csdn.net/zengaming/article/details/63681754一、解C（n，m），公式1：公式2：公式2可以这样理解。从n个项目中取m有两种情况：（1）不要取第n个项目，所以从第一个n-1中取m；（2） 取第n篇文章，然后从前面的n-1中取m-1；所以答案是这两种情况的总和。求解C（n，m）%p，其中p是一个大素数。当n、m和p较大时，使用公式2
下面内容转自: http://blog.csdn.net/zengaming/article/details/63681754
一、求解C(n, m)
公式一：
公式二：
公式二可以这么理解，从n个物品中取m个有2种情况：(1)不取第n个物品，于是从前n-1个中取m个; (2)取第n个物品，于是从前n-1个中取m-1; 所以答案是这两种情况的和
二、求解C(n, m)%p，p为大质数
当n,m,p都很大的时候，用公式二肯定不行了，费时间又费内存，这时候要用公式一，问题是取模时怎样可以把除法转化为乘法？
费马小定理： 若p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1， 即a^(p-1) ≡ 1 （mod p），所以a^(p-2) ≡ 1/a (mod p)
公式三：
这里求阶乘的时候要一边乘一边取模，求p-2次方的时候要要快速幂
三、求解C(n, m)%p，p为小质数
Lucas定理：n,m是非负整数，p是质数，将n,m写成p进制的形式，即：n=(a[k], a[k-1]...., a[0])p，m=(b[k], b[k-1]..., b[0])p，则
公式四：
公式五：
在对上面公式证明之前，我们先证明一下下面这个公式
公式六：
证明公式六：
证明公式五：
四、范德蒙恒等式
公式七：
证明：
1.
2.可以这么理解：从n+m个球中取k个球，相当于将球分为两部分，分别有n个球和m个球；结果相当于从n个球中取i个的球情况下，从m个球中取k-i个球，i的范围是[0,k]。