题意
题目链接
翻译来自神仙yyb
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 >= ; i--) {
long double s = d1 * * N + N * ( * N - ) * x;
ans += s / / N;
s = s - ( * d1 + * N * x - * x) / / N;
d1 = (( * N - ) * d1 + d1 + * x + * d1 + * x) / / N;
N--;
x = (s - * N * d1) / N / ( * N - );
// if(i > 990) printf("%.10lf\n", (double)x);
}
printf("%.15lf", (double)ans);
return ;
}