题目描述
http://codeforces.com/contest/1380/problem/G
Solution
我们先转换一下题意
首先，求期望可以看成求和，然后选 $k$ 个假宝箱相当于将前 $k$ 大去掉，剩下的 $n-k$ 个分成 $k$ 段
长度为 $cnt_i$ 的一段的贡献是 $\sum_{i=1}^{cnt_i}i\times a_i$
贪心可得 $a_i$ 递增，然后 $cnt_i$ 的差距不会超过 $1$
具体实现我们可以枚举 $k$，对于一个 $k$，我们每次分配 $k$ 个即可
时间复杂度 $O(n\log n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <cstring>
#define maxn 300010
#define ll long long
using namespace std;
const int p = 998244353;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1) {
if (n & 1) s = s * x % p;
x = x * x % p;
}
return s;
}
int n, a[maxn];
ll s[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n; ll inv = pow_mod(n, p - 2);
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1, greater<int>());
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
for (int k = 1; k <= n; ++k) {
ll ans = 0;
for (int i = k + 1, j = 1; i <= n; i += k, ++j)
ans = (ans + j * (s[min(i + k - 1, n)] - s[i - 1])) % p;
ans = ans * inv % p;
cout << (ans + p) % p << " ";
}
return 0;
}
|