这两天看到求幂模的时候有一种很快的方法，在组合数求模的lucas方法中也适用。假设未知数分别为a、b、p，需要求a^b%p。根据数学原理，我们可以知道a^(b+c)=a^b*a^c。所以这里，我们把b的二进制拆分，从b最小的一位开始看，每次只看b一位上的数，如果是1，说明这个位上需要乘a，计算累乘a模p，再看下一位。这里我们可以用位运算b&1判断b的最小一位是否是1，再用b>>=1抛掉这位，循环这两步。
假如b有n位，那么它的二进制有log2(n)位数，所以一共循环需要log2(n)次，这样算法复杂度就成了log(n)。而如果用循环乘a模p的方法，需要循环n次，算法复杂度是O(n)。因此这种求幂模的方法在大计算量上的速度上提高了许多。
贴代码：LL quick_mod(LL a, LL b){ LL ans = 1; a %= p; for(; b ; b >>= 1,a = a * a % p){ if(b & 1){ ans = ans * a % p; b--; } } return ans; }遇到组合数求模：假设未知数分别为m、n、p，需要求C(m,n)%p。(0<=m<=n)求组合数的数学公式：C(m,n) = n! / （m! *(n - m)!）数学的世界很奇妙，我们知道，模运算的加法，减法，乘法和四则运算类似，即：模运算与基本四则运算有些相似。(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p但对于除法却不成立，即(a / b) % p ≠ (a % p / b % p) % p 。数学家们于是提出“逆元”的概念来解决这个问题。什么是逆元呢？数论中的解释：对于正整数 a 和 p，如果有 ax≡1(modp)，那么把这个同余方程中 x 的最小正整数解叫做 a 模 p 的逆元。即建立式子 ax%p=1 ， x的最小正整数解就是 a 的逆元。求取 (a / b % p) 等同于 求取 (a∗(b的逆元)%p) 。 因此，求模运算的除法问题就转化为就一个数的逆元问题了。
而求取一个数的逆元，有两种方法

1. 拓展欧几里得算法
2. 费马小定理

在ACM中比较常见的情况是p是质数（很常见的有998244353）如果n,m<=1e5，这时我们可以利用费马小定理b^(p-1)%p=1可以得到b的逆元是b^(p-2)，使用上述的快速幂函数求解即可。
多组输入的时候可以增加一个 预处理函数，存储各个阶乘与逆元，方便进行C(n,m)的运算。 其中：fac[m] 表示 m! ; inv[m] 表示 m! % mod的逆元。 代码如下：void init(){ fac[0]=1; for (int i = 1; i < maxn; i++) fac[i] = (fac[i-1] * i) % p; inv[maxn-1] = quick_mod(fac[maxn-1], p-2);//Fac[N]^{p2} for (LL i = maxn - 2; i >= 0; i--) inv[i] = inv[i+1] * (i + 1) % p; }如果n,m很大，能达到1e18，但是p很小 <= 1e5 ，我们可以利用lucas定理
Lucas定理：C(n, m) % p = C(n / p, m / p) * C(n%p, m%p) % p
LL Lucas(LL n, LL m){ if(m == 0) return 1; return C(n % p, m % p) * Lucas(n / p, m / p) % p; }