题目链接：https://uoj.ac/problem/22

做法

经典 trick 。

简单来说，对于 $x$ 个有标号的数字，让指定的数字站在开头的概率是多少？

答案：$\frac{1}{x}$ 。

证法：

  1. 从随机性的角度考虑，第一个位置是某个数字的概率为 $\frac{1}{x}$ 。
  2. 从式子的角度分析：$\frac{(x-1)!}{x!}=\frac{1}{x}$ 。

现在规定有 $y$ 个数字必须在某些数字前面，且对于第 $i$ 个数字，其必须在前面的数字包括其自己所构成的集合为 $S_i$ 。

如果满足：$S_{i}\subseteq S_{i-1}$ 。

那么概率的计算公式为：$\prod \frac{1}{|S_{i}|}$ 。

证法：

我们顺序考虑，假如第一个数字是 $x$ ，$S_1/x$ 的元素都要在其后面，那么为 $\frac{1}{S_1}$ ，显然剩下元素仍然是随机的，现在把 $S_1/S_2$ 的元素删掉，考虑 $S_2$ 的元素，其仍然是随机的，且不受前面影响，完全是一个子问题，那么直接乘就行了。

证毕。

这是一个很经典的概率 trick ，但是一定要谨记其的使用范围。

比如我稍微改变一下上面的条件，让 $S_i$ 不包含 $x$ 就已经错了。

例如：$1,2$ 都要在 $3$ 前面，那么：$\frac{1}{4}$ ，显然是错的。

为什么？原因是接下来的序列并不是一个完全的子问题，原因是：

例如 $13$ ，这个时候放 $2$ ，$23$ 的情况有两种：$213,123$ ，而 $32$ 的情况只有一种：$132$ ，所以并不满足不受前面影响这句话。

当然，也可以采用式子严谨证明：

显然，结果为：

定义 $|S_0|=n+1$ 。

公式为：$(\prod\limits_{i=1}^{m} C_{|S_{i-1}|-1}^{|S_i|}(|S_{i-1}|-1-|S_{i}|)!)\frac{(S_{m}-1)!}{S_{m}!}$ 。

展开可以发现就是结论中的式子。而上面的反例显然就是不满足这条计算公式，所以也就不能使用结论中的计算式进行计算。

利用这个 trick ，这道题目就随便做了，做法就不详写了，自己想想。

UPD：看了官方题解突然发现，貌似这道题目不用这个 trick 也能做，本质上是把官方题解的式子优化了一下。