错排
概念
对于一个 $n$ 个元素的排列，若一个排列中所有的元素都不在自己的位置上，这样的一个排列称为一个错排。
一般将 $n$ 个元素的错排数量记作 $D_n$.
通过递推，可以在 $\mathcal{O}(n)$ 的复杂度内处理出 $D_1,D_2\cdots, D_n$.
递推式
推导过程不唯一。
第一步，在 $[1, n-1]$ 中任取一个元素 $i$，将 $n$ 连向 $i$，方法数量为 $(n-1)$.
第二步，确定 $i$ 连向哪个元素，分类讨论：
- $i$ 连向 $n$.此时剩下的 $n-2$ 个元素要满足错排，对答案贡献为 $(n-1)\times D_{n-2}$.
- $i$ 不连向 $n$.此时，相当于有 $n-1$ 个元素需要满足错排，对答案贡献为 $(n-1)\times D_{n-1}$.根据加法原理，得到递推式：
$$
\begin{align}
D_{n}=(n-1)\times(D_{n-1}+D_{n-2})\tag{n>2}
\end{align}
$$
特殊地，$D_1=0$，$D_2=1$.
求逆元 & 组合数
扩展欧几里得
概述
扩展欧几里得算法是用来在已知 $a,b$ 的情况下求解一组 $x,y$，使满足 $ax+by=gcd(a,\,b)=d$.
$\gcd(a, b)$ 为 $a, b$ 的最大公因数，方程一定有整数解。
特解
要计算 $\gcd(a,\,b)$，并求出满足条件的 $x,y$.
将下一个状态 $b$ 和 $(a\%b)$ 表示为：$b\cdot x_1+(a\%b)\cdot y_1=d$
则：
$$
\begin{align}
\because b\cdot x_1+(a\%b)\cdot y_1=d,\\
\text{又}\because a\%b=a-\left\lfloor\frac{a}{b}\right\rfloor\times b\\
\end{align}
$$
$$
\begin{aligned}\therefore gcd(a,\,b)=d&=b\cdot x_1+(a-\left\lfloor\frac{a}{b}\right\rfloor\times b)\cdot y_1\\
&=b\cdot x_1+a\cdot y_1-\left\lfloor\frac{a}{b}\right\rfloor\times b\times y_1\\
&=a\times y1+b\times(x_1-\left\lfloor\frac{a}{b}\right\rfloor\times y_1)
\end{aligned}
$$
所以满足条件的 $x=y_1,\,y=x_1-\left\lfloor\frac{a}{b}\right\rfloor\times y_1$.
int exgcd(int a, int b, int &x, int &y) {//函数返回值为gcd(a,b)
if(b == 0) {
x = 1;//gcd(a,b) = a = 1a+0b
y = 0;
return a;
}
int r = exgcd(b, a % b, x, y);//先递归
int t = x;//再计算x,y
x = y;
y = t - a / b * y;
return r;
}
时间复杂度为：$\mathcal{O}(\min(\log a, \log b))$，即 $\mathcal{O}(\log n)$ 级别。
通解
假设特解为 $(x_0,y_0)$，满足 $ax_0+by_0=gcd(a,\,b)=d$，
则有：
$$
a(x_0+k\frac{b}{d})+b(y_0-k\frac{a}{d})=d\tag{k为整数}
$$
所以方程的通解为：
$$
x=x_0+k\frac{b}{d}\\y=y_0-k\frac{a}{d}
$$
对于其它二元一次不定方程$ax+by=c$（$c$为任意正整数）只有当 $d\mid c$ 时才有整数解，通解形式：
$$
x=\frac{c}{d}x_0+k\frac{b}{d}\\y=\frac{c}{d}y_0-k\frac{a}{d}
$$
同余方程（模方程）
概述
指形如 $ax\equiv b\pmod c$ 的一种方程。其中 $a,b,c$ 是参数，$a,c$ 是正整数，$b$ 是小于 $c$ 的非负整数，$ x$ 是未知数。
解同余方程
根据同余定义，$ax\equiv b\pmod c$ 可化为 $xa+kc=b$. 其中 $a,b,c$ 已知，$x,k$ 未知，所以能用扩展欧几里得解同余方程。
通解
如果 $b\nmid gcd(a,c)$，方程无整数解.
否则同扩展欧几里得酸法，求得通解：
$$
x=\frac{b}{d}x_0+k\frac{c}{d}\\k=\frac{b}{d}p_0-k\frac{a}{d}
$$
其中 $k\in \Bbb{Z}$.
最小非负整数解
因为 $x=\frac{b}{d}x_0+k\frac{c}{d}$，其中 $x_0$ 是方程 $xa+kc=gcd(a,\,c)$ 的特解， $\frac{b}{d}x_0$ 是原同余方程的特解，
若 $x>0$，则有 $x\equiv \frac{b}{d}x_0 \pmod{ \frac{c}{d}} $。最小非负整数解为 $\frac{b}{d}x_0\,\%\,\frac{c}{d}$.
若 $x<0$，同理，最小非负整数解为 $(\frac{b}{d}x_0\bmod \frac{c}{d}+\frac{c}{d} )\bmod\frac{c}{d}$.
综上，最小非负整数解为：
$$
x=(\frac{b}{d}x_0\bmod\frac{c}{d}+\frac{c}{d})\bmod \frac{c}{d}
$$
乘法逆元
概述
给定两个整数 $a$ 和 $p$，假设存在 $x$ 使得 $ax\equiv 1\pmod p)$，称 $x$ 为 $a$ 关于 $p$ 的乘法逆元。
$a$ 关于 $p$ 的逆元存在的充分必要条件是 $\gcd(a,p)=1$.
在模意义下，乘一个数 $x$ 的逆元，可以理解为除以 $x$.
求一个数的逆元
将上面式子变形，变成 $ax+kp=1$，用扩展欧几里得能够求出一个 $x$.
如果 $p$ 是质数，有另一种方法求 $a$ 关于 $p$ 的逆元（费马小定理）
$$
a^{p-1}\bmod p=(a^{p-2}\times a)\bmod p=(x\times a)\bmod p=1
$$
所以 $a$ 关于 $p$ 的逆元是 $a^{b-2}\bmod b$ 的值，用快速幂优化。
时间复杂度：均为 $\mathcal{O}(\log n)$ 级别。
线性预处理逆元
在 $\mathcal{O}(n)$ 的时间复杂度内，求出任意 $n$ 个数的逆元，一般用于处理 $1\sim n$ 的逆元。
设我们要处理出 $a_1, a_2\cdots, a_n$ 的逆元。
第一步，预处理出前缀积数组 $\operatorname{pre}_i=\prod_{j=1}^ia_i$.
第二步，求出 $\operatorname{pre}_n$ 的逆元 $\operatorname{pre\_inv}_n$，复杂度 $\mathcal{O}(\log n)$.
第三步，通过 $\operatorname{pre\_inv}_i$，求出 $\operatorname{pre\_inv}_{i-1}$.
在模意义下，$\operatorname{pre\_inv}_i=\frac{1}{a_1\times a_{2}\times \cdots \times a_{i}}$，$\operatorname{pre\_inv}_{i-1}=\frac{1}{a_1\times a_2\times\cdots\times a_{i-1}}=\operatorname{pre\_inv}_{i}\times a_i$.
第四步，通过 $\operatorname{pre\_inv}_i$，求出 $\operatorname{inv}_i$.
在模意义下，$\operatorname{inv}_i=\operatorname{pre}_{i-1}\times \operatorname{pre\_inv}_{i}$.
在上面的步骤中，$\operatorname{pre\_inv}_i$ 即为 $i$ 的阶乘的逆元，在处理组合数时常用。
有另一种方法也可以处理逆元，时间复杂度相同，但不好记，而且证明麻烦，不需要掌握。
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (p - p / i) * inv[p % i] % p;
}
预处理组合数
预处理后，$\mathcal{O}(1)$ 地求解 $[1, n]$ 范围内的组合数，对大质数取模的结果。
记 $\operatorname{fac}_n=n!$，根据组合数的定义式：
$$
C_n^m=\frac{n!}{m!(n-m)!}=\frac{\operatorname{fac}_n}{\operatorname{fac}_m\times \operatorname{fac}_{n-m}}
$$
可以得到：
$$
C_n^m \bmod p = \operatorname{fac}_n (\operatorname{fac}_m)^{-1}(\operatorname{fac}_{n-m})^{-1}
$$
所以预处理出 $[1, n]$ 的阶乘，以及阶乘的逆元，每次即可 $\mathcal{O}(1)$ 求组合数。
int fac[], inv_fac[];
fac[0] = 1;
for(int i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % p;
inv_fac[n] = power(fac[n], p - 1);
for(int i = n - 1; i >= 0; i--)
inv_fac[i] = inv_fac[i + 1] * (i + 1) % p;