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$ 个元素，不分首尾的围成一个圆的排列叫做圆排列，求其方案个数。

解法

笛卡尔树（没听到讲）

多重集的排列组合

严格次小生成树

树套树