「解题报告」[AGC007C] Pushing Balls
APJifengc
·
·
题解
首先我们可以考虑将原问题转化成更简单的问题。类似于等差数列的求和法，我们可以将同样的问题反过来进行计算一遍，并且将这两次计算加和，这两个问题的答案显然是相等的。而根据期望的线性性，我们可以考虑每段距离的贡献，那么可以发现将两个问题中每段距离对应加和后得到的新问题的答案是相等的，而后者变成了每个位置距离均相等的更简单的问题。那么我们就只需要考虑每段距离都相等的情况（即 d=1,x=0 的情况）即可，最后将答案乘上 \frac{2d + (2n - 1) x}{2} 即可。
那么接下来考虑每段距离都相等怎么做。我们转化一下问题，将球与洞都看作元素排列成一个长度 2n+1 的序列，考虑其中的 2n 段距离。发现，每段距离正好对应着一种让球滚入洞中的方案。而若选择的这一段是中间的某一段，操作之后会使得相邻的三段合并成一整段；若选择的边缘的两段，则会使边缘的两个元素直接删除。
那么我们的问题可以重新描述成这样：有 2n 个数，每次随机选择一个数，若这个数在边缘，那么删除最边缘上两个数；否则将这个数相邻的三个数加和合并。问进行 n 次操作后，选择的数的总和的期望值。
我们可以发现这样一件事情：若进行合并操作，那么每个数被合并的概率都是相同的，即合并后新的数可能出现在 2n-2 个位置中的任意一个。那么这意味着，这 2n-2 段的期望长度也都是相同的。那么我们设 d_i 表示在进行 i 次操作后，每一段的期望长度是多少。那么有：
d_0 = 1, d_i = \frac{(2n'-1) d_{i - 1} + 3d_{i - 1}}{2n'} = \frac{n'+1}{n'} d_{i - 1}
每一次推球期望距离显然就是 $d_i$，那么答案就等于 $\frac{2d + (2n - 1) x}{2} \sum_{i = 0}^{n - 1} d_i$。可以直接递推计算，同时也可以推出 $d_i$ 的通项公式再计算，易得 $d_i = \frac{n + 1}{n + 1 - i}$。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, d, x;
int main() {
scanf("%d%d%d", &n, &d, &x);
double k = (2 * d + (2 * n - 1) * x) / 2.0;
double a = 0;
for (int i = 0; i <= n - 1; i++) a += 1.0 * (n + 1) / (n + 1 - i);
printf("%.12lf\n", k * a);
return 0;
}
```