欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

agc007C - Pushing Balls(期望 等差数列)

程序员文章站 2022-05-30 09:34:08
题意 题目链接 翻译来自神仙yyb Sol 又是一道神仙题。。 我开始的思路是枚举空位,但是还是不能做,GG 标算过于神仙,其中一些细节我也理解不了 题目给出的实际是一个首项为$d$,公差为$x$的等差数列 $sum = 2dn + \frac{2n(2n - 1)x}{2}$ 此时的期望为$\fr ......

题意

翻译来自

agc007C - Pushing Balls(期望 等差数列)

sol

又是一道神仙题。。

我开始的思路是枚举空位,但是还是不能做,gg

标算过于神仙,其中一些细节我也理解不了

题目给出的实际是一个首项为$d$,公差为$x$的等差数列

$sum = 2dn + \frac{2n(2n - 1)x}{2}$

此时的期望为$\frac{sum}{2n}$

考虑修改之后会有那些值发生改变

$d' = \frac{(2n - 2)d + d + 2x + 3d + 3x)}{2n}$(考虑第一个位置怎么变)

$sum' = \frac{d + (d + x) + (2n - 2)x + d + (2n - 1) x + d}{2n}$

$x' = \frac{sum -2nd}{n(2n - 1)}$

不断推下去即可

#include<bits/stdc++.h>
using namespace std;
long double n, d1, x, ans;
int main() {
    cin >> n >> d1 >> x;
    for(int i = n; i >= 1; i--) {
        long double s = d1 * 2 * n + n * (2 * n - 1) * x;
        ans += s / 2 / n;
        s = s - (4 * d1 + 4 * n * x - 2 * x)  / 2 / n;
        d1 = ((2 * n - 2) * d1 + d1 + 2 * x + 3 * d1 + 3 * x) / 2 / n;
        n--;
        x = (s - 2 * n * d1) / n / (2 * n - 1);
    //    if(i > 990) printf("%.10lf\n", (double)x);
    }
    printf("%.15lf", (double)ans);
    return 0;
}