组合数取模常用函数与方法总结

2019-04-13 16:04发布

站内文章 / 模拟电子
14702 0 1289

组合数取模常用函数与方法总结

这一类题目一般是先手算出答案的组合表达式，然后套用组合数取模的一些模板实现 一般是两种思路，一种是硬算（牺牲时间），一种打出阶乘表（牺牲空间） 有时候需要的话还可以打出逆元表
 另外lucas定理在处理mod比较小时很有用
 用到的函数：

1、快速幂：qmod(a,b,mod)    计算a的b次方在模mod下的值

注意的是尽量写成非递归形式，不然可能TLE
 LL qmod(LL a,LL b,LL mod) //快速幂 { LL ans=1; a=a%mod; while(b) { if(b&1==1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; }

2、求逆元  inv(a,p)   利用费马小定理求a在模p下的乘法逆元（p是素数）

LL inv(LL a,LL p) //求a在模p下的乘法逆元（p是素数） { return qmod(a,p-2,p); }

3、计算组合数 C(n,m) 

一种是利用算好的阶乘表fac[]和逆元表inve[]计算，如下 LL C(LL n,LL m) //组合数 { if(n<0 || m<0 || m>n) return 0; if(n==m) return 1; return fac[n]*inve[m]%p*inve[n-m]%p; }另一种方式是直接计算 LL C(LL n, LL m) { if(n<0 || m<0 || m > n) return 0; LL ans = 1; for(int i=1; i<=m; i++) { LL a = (n + i - m) % p; LL b = i % p; ans = ans * (a * inv(b, p) % p) % p; } return ans; }

4、lucas优化

其实一般都可以加一个lucas优化
 LL Lucas(LL n, LL m,LL p) { if(m == 0) return 1; return C(n % p, m % p,p) * Lucas(n / p, m / p,p) % p; }

热门文章