CF1753C
思路点拨
考虑一共有 \(s\) 个 \(0\) ，\(n-s\) 个 \(1\) 。最终序列的形态就是 \(s\) 个 \(0\) 在最前面，后面全部都是 \(1\) 。
考虑在前 \(s\) 个位置中有 \(k\) 个 \(1\) ，那么只需要将这 \(k\) 个 \(1\) 移动到后面就可以了。考虑第一次有效操作的概率，有 \(\dfrac{n(n-1)/2}{k^2}\) 的概率一次完成,令其为 \(p\) ,则期望操作的次数为：
\[\sum (1-p)^{i-1}p\times i=p\sum (1-p)^{i-1}i \]考虑 \(\sum (1-p)^{i-1}i\) 的值，将这个值乘上 \((1-p)\) ,然后原式与之相减：
\[\sum (1-p)^{i-1}i-\sum (1-p)^{i}i=\sum (1-p)^{i-1}=\dfrac{1}{(1-(1-p))^2}=\dfrac{1}{p^2} \]然后带回原式得到 \(p\sum (1-p)^{i-1}i=\dfrac{1}{p}\) 。
这个时候第一次有效操作的答案就得到了，\(\dfrac{k^2}{n(n-1)/2}\) 。
最终答案就是 \(k\) 次有效操作的期望和，\(\sum_{i=1}^k \dfrac{i^2}{n(n-1)/2}\) 。
标签：dfrac,sum,操作,考虑,杂题,20240131 From： https://www.cnblogs.com/Diavolo/p/17999192