问题求解II-HW05 题解

方法一：容斥

考虑对有多少个数被“确定”地放在了正确的位置上进行容斥，最终方案数为

$$ \begin{align} ans &= \sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)! \\ &= n!\sum_{k=0}^n\frac{(-1)^k}{k!} \end{align} $$

方法二：递推

令 $f(n)$ 表示长度为 $n$ 的序列的错排数。考虑数字 $1$ 的位置，因为需要错排，所以有 $n-1$ 种放法。不妨设 $1$ 被放在了 第 $k$ 个位置，接下来考虑 $k$ 的位置：

• $k$ 被放在了第一个位置，那么剩下的 $n-2$ 个数构成错排，共有 $f(n-2)$ 种放法。
• $k$ 不被放在第一个位置，那么 $k$ 此时有了一个我们新安排的“禁忌位置”，从而这 $n-1$ 个数构成错排，共有 $f(n-1)$ 种放法。

因此，$f(n)=(n-1)(f(n-1)+f(n-2))$，递推即可，时间复杂度为 $O(n)$。

在这样的数据规模下，我们无法接受将 $AB$ 的结果算出后再判断是否正确。这里我们为大家介绍 Freivalds 算法：

• 令 $\vec{r}$ 为长度为 $n$ 的随机01向量。
• 计算 $C\vec{r}$ 和 $A(B\vec{r})$，比较两个结果是否相同。

如果 $AB=C$，那么结果必定相同；下面证明如果 $AB\neq C$，结果相同的概率小于 $\frac{1}{2}$：

令 $D=(AB-C)$，则 $D$ 是非零矩阵，不妨设 $d_{ij}\neq 0$。令 $D\vec{r}=\vec{p}$，因为 $A(B\vec{r})=C\vec{r}$，所以 $\vec{p}=\vec{0}$，那么关注第 $i$ 行的结果，有

$$ \sum_{k=0}^nd_{ik}r_k=d_{ij}r_k+\sum_{k\neq j}d_{ik}r_k=0 $$

令后一项为 $y$，即 $d_{ij}r_k+y=p_i=0$，我们有

$$ Pr(p_i=0) = Pr(p_i=0|y=0)Pr(y=0)+Pr(p_i=0|y\neq 0)Pr(y\neq 0) $$

又

$$ \begin{align} Pr(p_i=0|y=0) &= Pr(r_k=0)=\frac{1}{2} \\ Pr(p_i=0|y\neq 0) &= Pr(r_k=1\wedge d_{ij}=-y)\leq Pr(r_k=1)=\frac{1}{2} \end{align} $$

所以

$$ \begin{align} Pr(p_i=0) &= Pr(p_i=0|y=0)Pr(y=0)+Pr(p_i=0|y\neq 0)Pr(y\neq 0) \\ &\leq \frac{1}{2}Pr(y=0)+\frac{1}{2}Pr(y\neq 0) \\ &= \frac{1}{2}Pr(y=0) + \frac{1}{2}(1-Pr(y=0)) \\ &= \frac{1}{2} \end{align} $$

从而

$$ Pr(D\vec{r}=0) = Pr\left(\bigwedge_{k=1}^n p_k=0\right)\leq Pr(p_i=0)\leq \frac{1}{2} $$

综上，这是一个符合单边蒙特卡洛的测试，我们只要重复多次就可以将错误的概率降到很低。