排列组合 C(n,m) |
您所在的位置:网站首页 › 中俄签证互免政策 › 排列组合 C(n,m) |
一、求解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 题解 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |