题解：P10867 [HBCPC2024] Points on the Number Axis A

· · 题解

题目翻译

爱丽丝正在数字轴上玩单人游戏。

数字轴上有 n 个点。每次，玩家选择两个点。这两点将被删除，它们的中点将被添加。当轴上只有一个点时，游戏结束。形式上，如果两个选定点是 x_i 和 x_j，则 \dfrac{x_i+x_j}{2} 将在操作后添加。

为了愉快地玩这个游戏，爱丽丝总是随机选择两个点。

现在爱丽丝有一个问题：最后一个点的预期位置在哪里。

可以证明，答案可以用 \frac{p}{q} 的形式表示，你只需要输出 p \cdot q^{-1} \bmod 998244353 的值。

题意简介

从数轴上选取两个点删去，并添加删去两点的中点。

然后求解最后一个点的期望。

思路

显而易见的，选每对点的可能都是相同的。 因为选择每一对点的可能性相同，所以答案就是所有点期望的平均数。

AC代码

话不多说，上代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod =998244353;
int f(int n,int k) {
    if (k<0)
        return 0;
    int res = 1;
    n%=mod;
    for (; k; k>>= 1,n=(n*n)%mod) {
        if (k&1) {
            res=(res*n)%mod;
        }
    }
    return res;
}
signed main() {
    int n,x=0;
    cin>>n;
    for(int i=1,a; i<=n; i++) {
        cin>>a;
        x=x+a;
        x%=mod;
    }
    x*=f(n,mod-2);
    x%=mod;
    cout<<x;
    return 0;
}