S 知识点总结（？）

威尔逊定理

定理

(p − 1)! ≡ −1 (mod  p)

证明

集合的差：$A \setminus B = \{x |x \isin A \land x \not \isin B \}$。

$\overline{x}$ 表示模 p 余 x 的数组成的集合。

当 p = 2 时，命题显然成立。

以下设 p ≥ 3，此时我们要证 Z_p 中所有非零元素的积为 $\overline{-1}$。

我们知道 Z_p 中所有非零元素 a 都有逆元 a⁻¹，于是 Z_p 中彼此互逆的元素乘积为 $\overline{1}$。

但是要注意 a 和 a⁻¹ 可能相等。若 a = a⁻¹，则 a² ≡ 1 (mod  p)，即

0 ≡ a² − 1 ≡ (a + 1)(a − 1) (mod  p)

从而 a ≡ 1 (mod  p) 或 a ≡ −1 (mod  p)。

这说明 $\mathbf{Z}_p \setminus \{\overline{0},\overline{1},\overline{-1}\}$ 中所有元素的乘积为 $\overline{1}$, 进而 Z_p 中所有非零元素的积为 $\overline{-1}$。

应用

阶乘与素数

在某些情况下，有必要考虑以某个素数 p 为模的公式，包含分子和分母中的阶乘，就像在二项式系数公式中遇到的那样。

只有当阶乘同时出现在分数的分子和分母中时，这个问题才有意义。否则，后续项 p! 将减少为零。但在分数中，因子 p 可以抵消，结果将是非零。

因此，要计算 n! mod  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)! mod p 很容易计算，可以应用 Wilson 定理：

(p − 1)! ≡ −1 (mod  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_pn)，因此算法的总时间复杂度为 O(plog_pn).

如果预先计算阶乘 0!, 1!, 2!, …, (p − 1)! 模 p，那么时间复杂度为 O(log_pn).

？

错排列

问题

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

解法

笛卡尔树（没听到讲）

多重集的排列组合

严格次小生成树

树套树