jzoj6442

题意

初始时有\(n\)个空位，边界视为已经被填，n个人依次填入东西，每次只能在距离被填位置的距离最大的空位填，求第\(i\)个人将东西填入\(j\)的概率。\(n\le 1000\)

做法

每次是将东西填入某段空位的中间，空位长度是偶数的有两个位置可以填，先钦定填较左边这个
令奇数空段为\(s_1\)个，偶数空段为\(s_2\)个，那么我们一次性将\(s_1+s_2\)个都填进去
这样的化总共会填\(O(logn)\)次

然后对于每层dp一下即可

原文：https://www.cnblogs.com/Grice/p/12873016.html