Codeforces 1380G 费马小定理求逆元

       题目给定两种箱子，一种给你一定数量金币，一种吃掉你所有金币。然后你要安排箱子顺序，使得获得的金币期望最小。问你放 $1$ 到 $k$ 个吃金币箱子的排放所能得到的最小期望。结果取模。
       贪心的想，吃金币的箱子肯定放金币多的。然后我们均匀摆放其他拿金币的箱子。使得期望最小。除法取模就求一波逆元相乘即可。
       如图均匀摆放使得期望最小。

       代码如下：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int maxn = 3e5 + 5;
const LL mod = 998244353;

LL qmod(LL a, LL b){
    LL ans = 1;
    while(b){
        if(b&1) ans = ans*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return ans;
}

LL c[maxn], sum[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    LL n, ni, cnt = 1;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> c[i];
    ni = qmod(n, mod - 2);
    sort(c + 1, c + 1 + n);
    for(int i = 1; i <= n; i++)
        sum[i] = (sum[i - 1] + c[i])%mod;
    while(cnt < n){
        LL k = 1, ans = 0, l;
        for(int i = n - cnt; i >= 1; i = l - 1, k++){
            l = max(i - cnt + 1, 1LL);
            ans = (ans + k*(sum[i] - sum[l] + c[l])%mod + mod)%mod;
        }
        cout << ans*ni%mod << " ";
        cnt++;
    }
    cout << 0 << endl;

return 0;}

本文地址：https://blog.csdn.net/weixin_43485513/article/details/107416243