同余式：

设m是给定的一个正整数，a、b是整数，若满足m|(a-b)，则称a与b对模m同余，记为a≡b(mod m)，或记为a≡b(m)。这个式子称为模m的同余式。
a≡b(mod m) 等价于 a，b分别除以m，得到的余数相同。

乘法逆元

概念：如果ax ≡ b (mod p) ,且gcd(a, p) = 1(a, p互质，是逆元存在的充要条件), 则称a 的逆元为 x。
逆元的含义：在模以p的条件下，一个数 a 如果有逆元 x 存在, 那么除以 a 相当于乘以 x。 求解逆元的方法（只介绍常用的有两种，其他方法自行寻找）：
1.拓展欧几里得算法（算法证明请点击我另外一篇博客）
简单说明一下，就是有两个整数a, b,存在有x，y 使满足贝祖等式 ax + by = gcd(a, b).
求得的 x 和 y（求得的其中一个很可能是负数)。
当a关于模以b的逆元存在，有gcd(a, b) = 1, 原式化简为： ax + by = 1，
方程两边同时模以b：
ax % b + by % b = 1 % b
ax % b = 1 % b
ax ≡ 1(mod b)
所以a的乘法逆元为x， 同理b的乘法逆元为y
因为x或y有可能是负数，所以a的逆元为 (x % p + p) % p， b的逆元为 (y % p + p) % p.
代码实现 int exgcd(int a, int b, int &x, int &y) { //返回gcd(a, b) if (!b) { x = 1; y = 0; return a; } int res = exgcd(b, a % b, y, x); y -= a / b * x; return res; } int main() { int a, b, x, y; cin >> a >> b; cout << exgcd(a, b, x, y) == 1 ? (x % b + b) % b : 0 << endl; //0代表逆元不存在 return 0; } 时间复杂度O(lg(mod)) , mod为模的大小 2.费马小定理
假设a是一个整数，p是一个质数，而整数a不是p的倍数,那么gcd(a, p) = 1.
则有 a^(p-1）≡1（mod p）
所以 a * a ^(p-2) ≡ 1 (mod p)
所以a关于模p的逆元为 x = a^(p-2) (mod p),用快速幂即可解决
代码如下 typedef long long ll; ll pow_mod(ll a, ll b, ll mod) { ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; } ll solve(ll a, ll p) { //费马小定理求a关于b的逆元 return pow_mod(a, p - 2, p); } 时间复杂度O(lg(mod))

组合数运算

公式：$C(n, r) = frac {n!} {r! * (n - r)!}$
我们的目标就是求取$C(n, r) \% mod$ 的值 一.运用逆元或者拓展欧几里得算法 1.求取1到n的阶乘对mod取模的结果存入数组ans[]中
2.求取 $C(n, r)$时，先利用“拓展欧几里得算法”或者“费马小定理+快速幂”，求出ans[r]的逆元存入临时变量 a1。
3.计算ans[] * a1 % mod 存入临时变量a2 (a2 即为$frac {n!} {r!} \% mod$),(式子不理解的话看上面逆元的含义)
4.求取ans[n-r]的逆元存入临时变量a3
5.$C(n, r) = a2 * a3 \% mod$ 一开始求取ans[]的时间复杂度O(n),求m次组合数总的时间复杂度为O(mnlg(mod)).
代码如下: void init(ll mod) { //第一步 for (int i = 1; i <= n; i++) ans[i] = ans[i-1] * i % mod; } ll pow_mod(ll a, ll b, ll mod) { ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; } ll niyuan(ll a, ll b) { return pow_mod(a, b - 2, b); } ll C(ll a, ll b, ll mod) { //计算C(a, b) % mod return ans[a] * niyuan(ans[b], mod) % mod * niyuan(ans[a-b], mod) % mod; } 二，运用卢卡斯定理(Lucas)进行求解
证明的话自行百度吧。。自己会用就好了。。
核心内容就是一条式子: $C(n, m) \% p = (C(n/p, m/p) \% p) * (C(n\%p, m\%p) \% p) \% p$
其中n，m很大，而p相对而言很小。
代码如下： ll Lucas(ll n, ll m, ll mod) { return m ? Lucas(n / mod, m / mod, mod) * C(n % mod, m % mod, mod) % mod : 1; }