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

0x00 题目翻译

最初数轴上由 $n$ 个点 $x_1,x_2,x_3,\dots,x_n$，每次随机取两个，把它们拿走后再把它们的平均数 $\dfrac{x_i+x_j}{2}$ 放回数轴，最后剩下一个点，求这个点坐标的期望。

0x01 解题思路

1. 猜想结论

$ans_n=\dfrac{\sum_{i=1}^{n}a_i}{n}$

2. proof

3.对输出的处理

要求输出 $p\times q^{-1}$，这里我们需要用乘法逆元。

显而易见 $998244353$ 是质数，乘法逆元可以通过 $q^{998244353-2}$ 得到，需要快速幂。

0x02 AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int p=998244353;
int fpow(int n,int k){
    if(k==1){
        return n;
    }
    else if(k==0){
        return 1;
    }
    long long ans=1;
    while(k) {
        if(k&1)
            ans=ans*n%p;
        n=n*n%p;
        k>>=1;
    }
    return ans;
}
int inv(int n){
    return fpow(n,p-2);
}
void solve(){
    int n,s=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        s+=t;
        s%=p;
    }
    for(int i=2;i*i<=max(n,s)&&i<=min(n,s);i++){
        if(n%i==0&&s%i==0){
            n/=i,s/=i;
        }
    }
    cout<<inv(n)*s%p<<endl;
}
signed main(){
    int t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}