一、求解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]。
相关练习:
CF 785D Anton and School - 2题解
HDU 4349 Xiao Ming's Hope 题解