Link

华中师范大学2023新生赛 H 龙

Question

有 \(m\) 个宝石孔，有 \(n\) 个宝石，每个宝石可以提升 \(a_i\) 点战斗力

每次镶嵌一个宝石，被选中的宝石会随机选择一个宝石孔进去，如果这个孔原来有宝石，则原来的宝石会被损坏

你可以任意决定镶嵌宝石的顺序，她想知道，如果把着 \(n\) 颗宝石都镶嵌进去，期望战力提升的最大值是多少？

Solution

显然，珠子从小到大插入最后的期望收益更高

当一颗珠子被嵌入时，它最后留下的几率就是固定的

从大到小考虑，设 \(p_i\) 表示第 \(i\) 颗珠子最后留下的概率（从大到小排序后）

\[p_{i+1}=p_i\times\frac{m-1}{m} \]

最后的期望就是 \(\sum p_i\times a_i\)

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL TT=998244353;
const int maxn=1e6+5;

LL read(){
    LL ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}

LL n,m,a[maxn];
LL qsm(LL a,LL b=TT-2){
    LL ret=1;
    while(b){if(b&1) ret=ret*a%TT;a=a*a%TT;b>>=1;}
    return ret;
}


int main(){
    freopen("H.in","r",stdin);
    LL n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    LL E=1,ans=0;
    sort(a+1,a+1+n,greater<int>());
    for(int i=1;i<=n;i++){
        ans=(ans+a[i]*E%TT)%TT;
        E=(E*(m-1))%TT;E=E*qsm(m)%TT;
    }
    cout<<ans<<endl;
    return 0;
}