数论篇7——组合数 & 卢卡斯定理(Lucas)
组合数
组合数就是高中排列组合的知识,求解组合数C(n,m),即从n个相同物品中取出m个的方案数。
求解方式
求解通式:$C^{m}_{n}=\dfrac {n!}{m!\left( n-m\right) !}$
性质1:$C^{m}_{n}=C_{n}^{n-m}$
性质2:$C^{m}_{n}=C^{m-1}_{n-1}-i+C^{m}_{n-1}$
打表递推
根据性质2:$C^{m}_{n}=C^{m-1}_{n-1}+C^{m}_{n-1}$
组合数算出来特别大,往往都会要求取余,这里取$P=1e9+7$。时间复杂度$O(n^2)$
; #define N 1000 int comb[N][N]; int main() { ; i < N; i++) { comb[i][] = comb[i][i] = ; ; j < i; j++) { comb[i][j] = comb[i - ][j] + comb[i - ][j - ]; comb[i][j] %= P; //cout << comb[i][j] << endl; } } }
逆元法
因为大部分题都有求余,可利用逆元的原理(没求余的题目,自己找一个比较大的素数作为P,也可以用逆元做)
线性递推求逆元
当$p$为质数时有$a^{-1}=(p-[p/a])\cdot (p\%a)^{-1}\%p$
求阶乘的逆元
根据通式:$C^{m}_{n}=\dfrac {n!}{m!\left( n-m\right) !}$,有$C^{m}_{n}=n!\cdot inv[m!] \cdot inv[(n-m)!]$
设 $finv(i)=inv(i\ !)$
则根据:$finv(i-1)=\frac{1}{\ (i-1)\ !}=\frac{1}{i\ !}\times i =finv(i)\times i$
有:$finv(i) = finv(i-1)\times inv(i)$
初始化时间复杂度$O(n)$,求$C^{m}_{n}$为$O(1)$
; ; ], Finv[N+], inv[N+];//fact是阶乘,Finv是阶乘的逆元 void init() { inv[] = ; //线性递推求逆元 ; i <= N; i++) { inv[i] = (P - P / i) * 1ll * inv[P % i] % P; } fact[] = Finv[] = ; ; i < N; i++) { fact[i] = fact[i - ] * 1ll * i % P;//求阶乘 Finv[i] = Finv[i - ] * 1ll * inv[i] % P;//求阶乘的逆元 } } int C(int n, int m) {//comb(n, m)就是C(n, m) || m > n) ; return fact[n] * 1ll * Finv[n - m] % P * Finv[m] % P; }
卢卡斯定理
现在有了新问题,如果$n$和$m$非常大,$p$为素数,比如求$C_n^m \% p \ ,\ n\leqslant 10^{18},m\leqslant 10^{18},p\leqslant 10^{9}$
$C_n^m\ \%\ p = C(n / p, m / p) * C(n\ \%\ p, m\ \%\ p)\ \%\ p$
或者写成这样更准确$Lucas(n,m)\ \%\ p=Lucas(n/p,m/p)*C(n\ \%\ p,m\ \%\ p)\ \%\ p$
证明请看此 lucas_百度百科,没仔细看证明,所以对不对我也不知道。
写成递归,代码就这么短:
LL Lucas(LL n, LL m, int p){ ; }
具体C的实现要看情况。
P较小时,打表
typedef long long ll; const int N = 1e5 ; ;//取一个小于N的素数 ll fact[P + ], inv[P + ], Finv[P + ];//阶乘打表 void init() { inv[] = ; //线性递推求逆元 ; i <= P; i++) { inv[i] = (P - P / i) * 1ll * inv[P % i] % P; } fact[] = Finv[] = ; ; i < P; i++) { fact[i] = fact[i - ] * 1ll * i % P;//求阶乘 Finv[i] = Finv[i - ] * 1ll * inv[i] % P;//求阶乘的逆元 } } ll C(ll n, ll m){//组合数C(n, m) % p ; return fact[n] * Finv[n - m] % P * Finv[m] % P; } ll Lucas(ll n, ll m){ ; }
P较大时,没法打表,用快速幂算逆元
typedef long long ll; const int N = 1e9 ; ; ll quickPower(ll a, ll b) { ll res = ; a %= P; while (b) { )res = (res % P) * (a % P) % P; a = (a % P) * (a % P) % P; b >>= ; } return res; } ll inv(ll x) {//x关于p的逆元,p为素数 ); } ll C(ll n, ll m) { ; ll up = , down = ;//分子分母; ; i <= n; i++) up = up * i % P; ; i <= m; i++) down = down * i % P; return up * inv(down) % P; } ll Lucas(ll n, ll m) { ); return C(n % P, m % P) * Lucas(n / P, m / P) % P; }
最新文章
- 获取centos6.5系统信息脚本
- Unity 5 中的全局光照技术详解
- 在做基于LBS应用的一些随笔
- HDU3732 背包DP
- 泛型,存放N张图片
- python中的binascii
- CRM PrincipalObjectAccess(POA)
- canvas-7globleCompositeOperation2.html
- Orcle11g用户密码恢复
- SQLite 中的各种限制
- No enclosing instance of type Test is accessible. Must qualify the allocation with an enclosing instance of type Test (e.g. x.new A() where x is an instance of Test).
- JS闭包作用域解析
- wiki中文语料的word2vec模型构建
- Python课程第四天作业
- h5py快速入门指南
- PHP7语法知识(二):流程控制语句、函数、字符串、数组
- [转帖] BIO与NIO、AIO的区别
- Bootstrap图像
- url组成
- 20155205 2016-2017-2 《Java程序设计》第8周学习总结