P8236 [AGM 2022 资格赛] 魔法的力量 题解

发表于 分类于

本文迁移自洛谷原文。

说句题外话，这题刚搬过来时精度要求是 $10^{-10}$ 级别的，人直接崩溃

然后顺便拿到了在洛谷上的一血

题解：

显然如果不考虑价值只考虑算进答案的次数的话，所有堆都是相同的。

所以我们可以计算每一堆石子期望被算进答案的次数。（如果合并的一堆产生了贡献，组成它的所有堆都相当于被算进了答案一次）

设 $f(n)$ 表示还剩下 $n$ 堆石子的时候，每堆石子以后被算进答案的次数的期望。

由于每堆石子是等价的，所以他们被选中的概率相同。

总共有 $\frac{n\times(n-1)}{2}$ 种选法，包含“某一堆”的有 $n-1$ 种选法，所以选择的两堆石子中包括“某一堆”的概率就是 $\frac{2}{n}$。同理，不包括它的概率就是 $\frac{n-2}{n}$。

所以，$f(n)=(1+f(n-1))\times \frac{2}{n} + f(n-1)\times(\frac{n-2}{n})=\frac{2}{n}+f(n-1)$

线性递推就可以求出 $f$ 了，最后答案就是 $f(n)\times\sum{a_i}$。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define ld long double
inline void solve(){
	ll n;ld x,sum=0,ml=0;
	cin>>n;
	for(int i=1;i<=n;++i)cin>>x,sum+=x;
	for(int i=2;i<=n;++i)ml+=(ld)(2)/(ld)(i);
	cout<<fixed<<setprecision(9)<<sum*ml<<'\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;
	//cin>>T;
	for(;T--;)solve();
	return (0-0);
}