在基础的数学理论中逆元是一个不可缺少的概念，也在除法取模的过程中用到。在组合数求取过程中，因为阶乘数一般偏大，所以对组合数取模也是算法题目中一般的处理方式。组合数学也是一个比较有趣的方向，需要的是思维、推理还有对组合数概念的了解。
求乘法逆元
在求取逆元之前应该先明确逆元的作用，用一句话来讲就是将除法变乘法。整数对模数之模逆元存在的充分必要条件是该数和模数互素，若此模逆元存在，在模数下的除法可以用和对应模逆元的乘法来达成，此概念和实数除法的概念相同。
- 逆元的定义
逆元的定义如下公式所示，注意这里的 $x$ 是 $a\bmod{b}$ 的逆元，记作 $a^{-1}$ 。
\[a*x\equiv1\pmod{p}\]- 除法取模
四则运算中除了除法以外都可以直接取模，但是除法比较特殊需要逆元的帮助。
\[(a/b)\mod{p}=a*b^{-1}\mod{p}\]扩展欧几里得定理
求取乘法逆元的其中一个方法就是扩展欧几里得定理即exgcd，该定理可以求取 $ax+by=\gcd(a,b)$ 的整数解，亦可以用来求取 $a$ 的逆元 $x$ 。
// Extended Euclid's Theorem function.
int exgcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int g = exgcd(b, a % b, y, x);
y -= a / b * x;
return g;
}
int inv(int a, int p) {
int x, y;
int gcd = exgcd(a, p, x, y);
// get the inverse element
return (x % p + p) % p;
}
用扩展欧几里得求取逆元之后(a / b) % p可以换成a * inv(b, p) % p来让除法对 $p$ 取模。
扩展欧几里得定理的使用前提是 $\gcd(a,p)=1$ ，否则逆元不存在
费马小定理
通常取模的对象是一个特殊的正整数即质数1e9+7，质数总是特殊的那个，当模数为质数时可以用费马小定理求逆元。
当模数是素数时可以用以下模板进行计算乘法逆元。
int fastpow(int a, int b, int p) {
int ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % p;
}
a = a * a % p;
b >>= 1;
}
return ans;
}
// When p is prime, the inverse of a mod p.
int inv(int a, int p) { return fastpow(a, p - 2, p); }
组合数
组合数的意义就不多赘述了，求取组合数的时候一般靠的是公式法还有神奇的杨辉三角。但前者无法避免除法取模，后者无法避免内存浪费比较少用，需要进行取舍。
- 排列组合
- 选择方式
这里的差别可以这么理解，选择出来的数是没有顺序的，所以把排序方式的个数除去之后就有了 $C_{n}^{m}=\dfrac{A_{n}^{m}}{m!}$ 。
卢卡斯定理
除了硬着头皮求逆元进行组合数的取模，当模数是质数时可以采用卢卡斯定理来解决大组合数取模的问题。
// Used to store the number of factorial number.
int f[1000010];
int init(int n, int p) {
f[0] = 1;
for (int i = 1; i < 1000005; i++) {
f[i] = (f[i - 1] * i) % p;
}
}
int fastpow(int a, int b, int p) {
int ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % p;
}
a = a * a % p;
b >>= 1;
}
return ans;
}
int inv(int a, int p) { return fastpow(a, p - 2, p); }
int C(int n, int m, int p) {
return f[n] * inv(f[m], p) % p * inv(f[n - m], p) % p;
}
int lucas(int n, int m, int p) {
if (m == 0) {
return 1;
}
// optimize with Lucas theorem
return (C(n % p, m % p, p) * lucas(n / p, m / p, p)) % p;
}