七、常用模板

7.1 快速幂

利用公式，可以直接用底数平方、指数除以2的方式，这样指数降到0只需要log(n)次，因此复杂度仅需O(logn)，比朴素的模拟乘方法的O(n)要优秀很多。
模板如下：

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 lon