[数学记录]AT2170 [AGC007C] Pushing Balls

**题意** ： 在一条直线上有 $n$ 个球与 $n+1$ 个洞，球和洞相间分布。 记 $d_i$ 为第 $i$ 段两个对象之间的距离，满足 $d_i-d_{i-1}=x (i>1)$ ，并给定 $d_1,x$ ，这样就确定了所有对象的位置。 每次随机选择一个球，将其向某个随机的方向推动。 当球经过某个洞时，若该洞中已经有球，则会滚过这个洞，否则掉入洞中并停止。  共进行 $n$ 次操作，操作结束后，每个球都一定进洞了。 求所有球移动的期望总距离，以实数形式回答。 $n\leq 2\times10^5$ ，时限$\texttt{2s}$。 ------------ 神必题。 题目给出的 $d$ 是一个等差序列，这个性质看起来非常刻意，也应该非常关键，然而并没有很好的切入点。 本着未知过半直接莽的原则，先手玩一下吧。下面是 $n=3$ 的情况。 $$\square\quad d\quad\circ\quad d+x\quad\square\quad d+2x\quad\circ\quad d+3x\quad\square\quad d+4x\quad\circ\quad d+5x\quad\square$$ 上面是初始状态，看看推一步之后会形成那些子问题。 - 向左推第一个球 $$\square\!\!\!\!\!\circ\quad d\quad+\quad d+x\quad\square\quad d+2x\quad\circ\quad d+3x\quad\square\quad d+4x\quad\circ\quad d+5x\quad\square$$ $$\square\quad d+2x\quad\circ\quad d+3x\quad\square\quad d+4x\quad\circ\quad d+5x\quad\square$$ - 向右推第一个球 $$\square\quad d\quad+\quad d+x\quad\square\!\!\!\!\!\circ\quad d+2x\quad\circ\quad d+3x\quad\square\quad d+4x\quad\circ\quad d+5x\quad\square$$ $$\square\quad 3d+3x\quad\circ\quad d+3x\quad\square\quad d+4x\quad\circ\quad d+5x\quad\square$$ - 向左推第二个球 $$\square\quad d\quad\circ\quad d+x\quad\square\!\!\!\!\!\circ\quad d+2x\quad+\quad d+3x\quad\square\quad d+4x\quad\circ\quad d+5x\quad\square$$ $$\square\quad d\quad\circ\quad 3d+6x\quad\square\quad d+4x\quad\circ\quad d+5x\quad\square$$ - 向右推第二个球 $$\square\quad d\quad\circ\quad d+x\quad\square\quad d+2x\quad+\quad d+3x\quad\square\!\!\!\!\!\circ\quad d+4x\quad\circ\quad d+5x\quad\square$$ $$\square\quad d\quad\circ\quad d+x\quad\square\quad 3d+9x\quad\circ\quad d+5x\quad\square$$ - 向左推第三个球 $$\square\quad d\quad\circ\quad d+x\quad\square\quad d+2x\quad\circ\quad d+3x\quad\square\!\!\!\!\!\circ\quad d+4x\quad+\quad d+5x\quad\square$$ $$\square\quad d\quad\circ\quad d+x\quad\square\quad d+2x\quad\circ\quad 3d+12x\quad\square$$ - 向右推第三个球 $$\square\quad d\quad\circ\quad d+x\quad\square\quad d+2x\quad\circ\quad d+3x\quad\square\quad d+4x\quad+\quad d+5x\quad\square\!\!\!\!\circ$$ $$\square\quad d\quad\circ\quad d+x\quad\square\quad d+2x\quad\circ\quad d+3x\quad\square$$ 不难发现，这是个线性的问题，每一段空位的长度对答案的贡献是线性的。 于是，我们可以只记录空位长度的期望。 子问题中，各个空位长度的期望是 ： $$\square\quad \dfrac{8d+5x}{6}\quad\circ\quad \dfrac{8d+15x}{6}\quad\square\quad \dfrac{8d+25x}{6}\quad\circ\quad \dfrac{8d+35x}{6}\quad\square$$ 居然还是等差序列！有 NOI2019D2T2 那味儿了…… 一般地，新等差序列的首项为 $d+\dfrac{2d+5x}{2n}$ ，公差为 $x+\dfrac{2x}{n}$ （可以通过讨论第一段和第二段得到） 此外，球移动的期望距离为 $d+\dfrac{1}{2n}\sum_{i=1}^{2n-1}ix=d+\dfrac{(2n-1)x}{2}$ 于是，对等差序列做 $n$ 次操作即可得知答案。 ```cpp #include<algorithm> #include<cstdio> #define db double using namespace std; int main() { int n;db d,x; scanf("%d%lf%lf",&n,&d,&x); db ans=0; while(n){ ans+=d+x*(2*n-1)/2; db _d=d+(2*d+5*x)/(2*n),_x=x+2*x/n; d=_d;x=_x;n--; }printf("%.10f",ans); return 0; } ```