CF1523E题解

OMG_wc · 2021-06-03 14:01:19 · 题解

题意：

给定 n,m，由 1\sim n 构成的排列一共有 n! 个，每一个排列存在一个有效值 k 定义为：

前 k-1 个数中，任意两个数的差的绝对值 \ge m ，第 k 个数会和之前某个数的差的绝对值 <m 。

求任意选一个排列有效值的期望，也就是 \frac{\sum k}{n!} 。

显然可以对每个有效值 i，求出相应的概率为 P_i ，那么最终答案就是 \sum\limits_{i=1}^nP_ii 。不过 P_i 有点不太好算，因为第 i 步终止的方案数很难算。

稍微变形一下，\sum\limits_{i=1}^nP_ii=\sum\limits_{i=1}^n\sum\limits_{j=i}^n P_i=\sum\limits_{i=1}^n S_i ，改成计算后缀概率和 S_i 。

仔细想想，S_i 就是相当于是到了第 i-1 步还活着的概率，这样就不用计算终止步的概率了。

要计算 S_i， 先考虑在 n 个位置上选 i-1 个位置，满足相邻所选的位置之间至少有 m-1 个空，再乘以每次选这些位置的概率，

即 \frac{i-1}{n}\times\frac{i-2}{n-1}\times\frac{i-3}{n-2}\times\cdots\times\frac{1}{n-i+2} 。