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:

#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);
}