AGC007

Description

题目链接 懒得写详细题意了, 放个链接

(nle 2*10^5) 个球, (n+1) 个坑, 排成数轴, 球坑交替. 相邻球-坑距离为等差数列 (d). 给定首项与公差. 每次随机选一个球并随机往一个方向推, 求期望经过距离总和

Solution

手玩观察一下, 球不可能没坑掉, 每次推完一个球后变成 (n-1) 个球的子问题.

对于每一个子问题, 只考虑推第一个球的期望距离 ((frac{sum_{i=1}^{2n}d_i}{2n})) , 其他的在子问题中处理.

考虑对于任意一个子问题, 假设有 (n) 个球, 则有 (2n) 个子状态, 每个子状态的概率 (frac 1{2n})

子状态中 (d') 可根据当前问题的 (d) 经过线性运算得出, 推第一个球的期望距离也可由 (d) 线性运算得出.

因此, 我们可以将这 (2n) 个子问题合并, 合并的子问题中 (d''_i = E[d'_i]). 下面观察 (d'') :

下面的图中, 记o为球, d为当前子问题的(期望)每段段长, _为坑, 新d''是从左往右标号的.
   o     o     o     o     考虑每种球掉落方案, 边界球往边界坑掉 是 特殊情况, 其余:
 d1 d2 d3 d4 d5 d6 d7 d8   将相邻的三个d加在一起合成一段, 其他不变. 记段为(l,r)
_     _     _     _     _  那么l=1..2n-2, 考虑每个di (1<=i<=n) 的贡献

(lle i-2) 时, (d_i o d''_{i-2}). (l=i-1) 时, (d_i o d''_{i-1}). (lge i) 时, (d_i o d''_{i}) , 总的来看就是

(d''_i = d_i+d_{i+2}+i*d_{i+2}+d_{i+1}+(2n-2-i+1)*d_i=(2n-i)d_i+d_{i+1}+(i+1)d_{i+2})

(=(2n+2)d_0+3Delta + (2n+4)iDelta) , 于是原问题等差, 合并后子问题等差, (cdots), 都等差.

实现很简单

Code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i)
#define ri rd<int>
typedef long double db;
using namespace std;

template<class T> inline T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x;
}

int n;
db d0, delta, ans;

inline db calc(db d0, db delta, db len) {
	return len * d0 + delta * len * (len + 1) / 2;
}

int main() {
	
	n = ri(), d0 = ri(), delta = ri(), d0 -= delta;
	per (i, n, 1) {
		ans += calc(d0, delta, 2 * i) / (2 * i);
		d0 = (2 * i + 2) * d0 + 3 * delta;
		delta *= (2 * i + 4);
		d0 /= 2 * i;
		delta /= 2 * i;
	}

	printf("%.15Lf
", ans);

	return 0;
}