S 知识点总结（？）
威尔逊定理
定理
$$
(p-1)! \equiv -1 \pmod p
$$
证明
集合的差：$A \setminus B = {x |x \isin A \land x \not \isin B }$。
$\overline{x}$ 表示模 $p$ 余 $x$ 的数组成的集合。
当 $p=2$ 时，命题显然成立。
以下设 $p\geq 3$，此时我们要证 $\mathbf{Z}_p$ 中所有非零元素的积为 $\overline{-1}$。
我们知道 $\mathbf{Z}_p$ 中所有非零元素 $a$ 都有逆元 $a^{-1}$，于是 $\mathbf{Z}_p$ 中彼此互逆的元素乘积为 $\overline{1}$。
但是要注意 $a$ 和 $a^{-1}$ 可能相等。若 $a=a^{-1}$，则 $a^2\equiv 1\pmod p$，即
$$
0\equiv a^2-1\equiv (a+1)(a-1)\pmod p
$$
从而 $a\equiv 1\pmod p$ 或 $a\equiv -1\pmod p$。
这说明 $\mathbf{Z}_p \setminus {\overline{0},\overline{1},\overline{-1}}$ 中所有元素的乘积为 $\overline{1}$, 进而 $\mathbf{Z}_p$ 中所有非零元素的积为 $\overline{-1}$。
应用
阶乘与素数
在某些情况下，有必要考虑以某个素数 $p$ 为模的公式，包含分子和分母中的阶乘，就像在二项式系数公式中遇到的那样。
只有当阶乘同时出现在分数的分子和分母中时，这个问题才有意义。否则，后续项 $p!$ 将减少为零。但在分数中，因子 $p$ 可以抵消，结果将是非零。
因此，要计算 $n! \bmod p$，而不考虑阶乘中出现因数 $p$。写下素因子分解，去掉所有因子 $p$，并计算乘积模。
用 $(n!)_p$ 表示这个修改的因子。例如：
$$
(7!)p \equiv 1 \cdot 2 \cdot \underbrace{1}{3} \cdot 4 \cdot 5 \underbrace{2}_{6} \cdot 7 \equiv 2 \bmod 3
$$
这种修正的阶乘，可用于快速计算各种带取模和组合数的公式的值（吗？）。
计算余数的算法
计算上述去掉因子 $p$ 的阶乘模 $p$ 的余数。
$$
\begin{aligned}
(n!)p &= 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}{p} \cdot (p+1) \cdot (p+2) \cdot \ldots \cdot (2p-1) \cdot \underbrace{2}{2p} \
&\quad \cdot (2p+1) \cdot \ldots \cdot (p^2-1) \cdot \underbrace{1}{p^2} \cdot (p^2 +1) \cdot \ldots \cdot n \pmod{p} \\
&= 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}{p} \cdot 1 \cdot 2 \cdot \ldots \cdot (p-1) \cdot \underbrace{2}{2p} \cdot 1 \cdot 2 \
&\quad \cdot \ldots \cdot (p-1) \cdot \underbrace{1}_{p^2} \cdot 1 \cdot 2 \cdot \ldots \cdot (n \bmod p) \pmod{p}
\end{aligned}
$$
可以清楚地看到，除了最后一个块外，阶乘被划分为几个长度相同的块。
$$
\begin{aligned}
(n!)p&= \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}{1\text{st}} \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 2}{2\text{nd}} \cdot \ldots \\
& \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}{p\text{th}} \cdot \ldots \cdot \quad \underbrace{1 \cdot 2 \cdot \cdot \ldots \cdot (n \bmod p)}_{\text{tail}} \pmod{p}.
\end{aligned}
$$
块的主要部分 $(p-1)!\ \mathrm{mod}\ p$ 很容易计算，可以应用 Wilson 定理：
$$
(p-1)!\equiv -1\pmod p
$$
总共有 $\lfloor \frac{n}{p} \rfloor$ 个块，因此需要将 $\lfloor \frac{n}{p} \rfloor$ 写到 $-1$ 的指数上。可以注意到结果在 $-1$ 和 $1$ 之间切换，因此只需要查看指数的奇偶性，如果是奇数，则乘以 $-1$。除了使用乘法，也可以从结果中减去 $p$。
最后一个部分块的值可以在 $O(p)$ 的时间复杂度单独计算。
这只留下每个块的最后一个元素。如果隐藏已处理的元素，可以看到以下模式：
$$
(n!)_p = \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 2} \cdot \ldots \cdot \underbrace{ \ldots \cdot (p-1)} \cdot \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 1} \cdot \underbrace{ \ldots \cdot 2} \cdots
$$
这也是一个修正的阶乘，只是维数小得多。它是：
$$
\left(\left\lfloor \frac{n}{p} \right\rfloor !\right)_p
$$
因此，在计算修改的阶乘 $(n!)_p$ 中，执行了 $O(p)$ 个操作，剩下的是计算 $(\lfloor \frac{n}{p} \rfloor !)_p$，于是有了递归，递归深度为 $O(\log_p n)$，因此算法的总时间复杂度为 $O(p \log_p n)$.
如果预先计算阶乘 $0!, 1!, 2!, \dots, (p-1)!$ 模 $p$，那么时间复杂度为 $O(\log_p n)$.
？
错排列
问题
设 $a$ 是 $1$ 到 $n$ 的一个全排列，求满足 $\forall i \isin [1,n] ,a_i \not = i$ 的排列数量。
解法
正难则反，求 $\exists i \isin [1,n] ,a_i = i$ 的排列数。
于是令一个排列的相等的地方为 $p$，大小为 $k$（$\forall i \isin [1,k],a_{p_i}=p_{i}$），显然，它对答案的贡献为 $(n-k)!$，观察到 $p$ 中具体有哪些元素我们并不关心，我们只关心它有多少元素，可以得出答案为：
$$
\sum_{i=0}^{n}(-1)^i\operatorname{C}^i_n(n-i)!=\sum_{i=0}^{n}(-1)^i\frac{n!}{i!}
$$
圆排列
问题
从 $n$ 个不同元素中取出 $m$ 个元素，不分首尾的围成一个圆的排列叫做圆排列，求其方案个数。