一开始本来想 VP 这一场，后来想起自己看过这场的 D，也知道这场的风评，就释怀地笑了。

下文将题面中的 改为 。

题面说是算期望操作次数，对于这种问题，常用的套路有如下两种：一是通过 列式子，二是通过期望的线性性将其转化成若干个事件的概率相加。本题显然用第二种跟方便一些。

我们将答案变为 。这么定义是因为最后一次较为特殊。

如何算这个概率呢？注意到原题面中选的过程的概率是很复杂的，每一步的分母都不一样。不过分母都是“当前剩余的折线个数”。这样的概率模型容易被转化成如下形式：等概率随机一个长为 的排列 。从小到大枚举 ，如果当前的 所对应分割线是有效的，就割 。

这个转化的正确依赖于如下结论：对于一个长度为 的排列 ， 的概率是 。由上述结论可得，我们每次割一条线的时候，剩余的每条线恰好是我们当前割的这条线的概率都是 。这也恰好是原概率模型的分母。

那么我们可以算一条线 被算进答案的概率了。这条线满足条件当且仅当其在排列 中在线 与 之前。而这个概率自然就是 ，注意需要 ，当 时这条线没有贡献。也可以同理算出每条形如 的直线被算进答案的概率。都加起来即可。

时间复杂度 。