解法
第一问
第一问比较好求，设状态\(f[i]\)为有\(i\)个叶子节点时的期望深度。考虑从上一个状态分裂会多对总深度做\(f[i-1]+2\)的贡献，可以知道：
\[ f[i] = \frac{f[i-1] * (i-1) + f[i-1] + 2}{i} = f[i-1] + \frac{2}{i} \]
第一问比较好求，设状态\(f[i]\)为有\(i\)个叶子节点时的期望深度。考虑从上一个状态分裂会多对总深度做\(f[i-1]+2\)的贡献，可以知道：
\[ f[i] = \frac{f[i-1] * (i-1) + f[i-1] + 2}{i} = f[i-1] + \frac{2}{i} \]
一道概率期望类 DP。
我们设状态不考虑当前轮数：这样太难设计了，我太菜不会。考虑设计全局的状态：\(f[i][j]\)意义为考虑前\(i\)张卡牌，且游戏结束时只发动了\(j\)张纸牌的概率。那么答案就是：
这道题还是挺神仙的，式子比较好推但是高斯消元部分有点麻烦。
首先我们枚举终点\(t\)，设状态\(f[i][j]\)为人在\(i,j\)时转移到\(t\)的概率。考虑下面的式子：
这道 DP 出的很好，考察了选手模型转换的能力。
第\(i\)个人说：“有\(ai\)个人分数比我高，\(bi\)个人分数比我低。”
每一句话都可以看作是一维坐标上的一条线段\([a_i+1,n-b_i]\)，表示这一段线段上的人成绩相等。显然，对一每一种合法情况，这些线段都不会相交（允许完全重合）。所以将线段按左端点排序，这个以坐标位关键字的\(dp\)方程应该写成：
\[ dp[i] = dp[i-l] + min(\text{线段长度}, \text{线段个数}) \]
这道题其实就是高斯消元裸题。依照题意可以列出形如以下的方程：
\[ \sum_{i = 1}^n (x_a [i] – x_0 [i])^2 = c \]
其中\(c\)表示球的半径。一共有\(n+1\)个这样的方程，可以考虑上下相减消掉常数，这样就构造出了一个\(n\)个方程的方程组。最终方程组：
\[ \begin{cases} 2\sum_{i = 1}^n x_1[i] x_2[i] = \sum_{i = 1}^n (x_1[i])^2 – (x_2[i])^2 \\ 2\sum_{i = 1}^n x_2[i] x_3[i] = \sum_{i = 1}^n (x_2[i])^2 – (x_3[i])^2 \\ 2\sum_{i = 1}^n x_3[i] x_4[i] = \sum_{i = 1}^n (x_3[i])^2 – (x_4[i])^2 \\ \dots \end{cases} \]
扔到高斯消元里就搞定了。
这道题看数据范围可以联想到状压 \(DP\)。考虑设计一个状态：\(dp[S]\)代表女人的集合，其中集合长度\(|S|\)提供了另外一个信息，换句话说，\(dp[S]\)代表了考虑前\(|S|\)个男人对应的女人集合的转移个数。不难推出下面的式子：
\[ dp[S] = \sum_{(i, |S|) \in compatible} dp[S’], S’ \cup i = S \]