7.常用模板
7.1快速幂
利用公式
模板如下：
| long long power(long long a,long long b,int mod) { //计算a的b次方对mod取模的值 long long res=1; while(b){ if(b&1)res=res*a%mod; //判断b为奇数，等价于b%2==1 b>>=1; //b的二进制右移一位，等价于b/=2 a=a*a%mod; } return res; } |
7.2逆元
根据费马小定理，若a和p互素，那么ap-2和a互为逆元。逆元的作用是，模p意义下，除以p和乘以p的逆元是等价的。
求逆元直接调用快速幂即可：
| long long inv(long long x,int mod){ //求x的逆元（模mod意义下） return power(x,mod-2,mod); } |
以上两个模板mod可以写在全局变量里，这样函数就可以少一个参数。
有了逆元以后，组合数的模板就可以改写成这样：
| long long |
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
算法笔面试宝典 文章被收录于专栏
算法笔面试真题解析
投递字节跳动等公司6个岗位