「AGC007C」Pushing Balls - 概率期望

题目链接：传送门

Description

在一条直线上有 $n$ 个球和 $n + 1$ 个坑共$2n + 1$ 个“物品”，$i$ 个球在第$i$ 和第$i + 1$个坑之间。

球与坑之间是有距离的，这些距离组成了首项为 $a$，公差为 $x$的等差数列。

即第i个物品和第 $i + 1$ 个物品之间的距离是 。

小 A 会进行$n$ 轮操作，每轮操作中，先从剩下的球中等概率地选择一个，然后等概率地选择一个方向，这个球将会朝这个方向滚，直到遇到一个里面没有球的坑并落进去留在里面。

然后这一轮的收益为球滚的距离。

请求出期望收益。

Hint

1 <= N <= 200000 1 <= a, x <= 100

Sample Input

1 3 3

Sample Output

2 1 0

Solution

首先把“操作”换一种表述：等概率选择相邻的两个物品，并拿走他们，收益为两物品之间的距离，这样就不必区分球和坑了。

我们会发现，每次操作后的“期望局面”仍然是一个等差数列

记$m$为现在剩下的区间数，一开始$m=2n$，计算得到

$a'=\frac{(m+2)a+5x}{m}$$x'=\frac{m+4}{m}x$

然后每次

这样就能$O(n)$计算了

Summary

$a'$和$x'$还有$Ans$如何计算开始一直不知道怎么推的，后来自己静下心来画了个图暴力算了下发现居然推出来了。所以以后做题还是不能太浮躁，像这种题要在草稿纸上多验算一下，不能只是在脑海中想一下大概的方法。

Code

#include <bits/stdc++.h>
using namespace std;
double N;
double a, x;
int main()
{
#ifdef hk_cnyali
    freopen("C.in", "r", stdin);
    freopen("C.out", "w", stdout);
#endif
    scanf("%lf%lf%lf", &N, &a, &x);
    double Ans = 0;
    double M = 2 * N;
    while (M)
    {
        Ans += (2 * a + (M - 1) * x) / 2;
        a = ((M + 2) * a + 5 * x ) / M;
        x = (M + 4) * x / M;
        M -= 2;
    }
    printf("%.20lf\n", Ans);
    return 0;
}