2015-2016 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest Problem H. Hans Zimmer

引理1： 长为的线段随机切刀分成条线段，最短线段长度期望为，第短线段长度为

考虑一个直观等价的事实，随机切刀等价于个随机变量满足，最短段为(具体证明不会。。)

另一个比较直观的引理2(证明不会，概率论太差了呜呜呜)：

再一个比较直观的引理3：

证明(终于有我会的了)：

那么最短线段的期望长度:

最长线段的期望长度(容斥做法)：

第短线段的递推做法(容斥做法不会呜呜呜)：

考虑第2短的线段期望长度，相当于给都减去，答案就是此时的最短线段期望长度+原先最短线段期望长度。

由此可以数学归纳法求出

回到原题，此时可以枚举确定横纵切的刀数 答案为：

精度上用函数解决即可