ABC295 E
给你一个长度为 \(N\) 的序列 \(A\) 满足 \(\forall i\in [1,N],A_i\in[0,M]\)，其中 \(M\) 是一个给定的常数
执行以下两种操作
- 不断把序列中的一个 \(0\) 换成在 \([1, M]\) 中均匀随机的一个数，直到序列中没有 \(0\)
- 对整个序列升序排序
求序列第 \(K\) 个数的期望值，对 \(998244353\) 取模
考虑从权值的角度去做
假设 \(X\) 可以在 \([1, M]\) 内取值，为 \(i\) 的概率是 \(p_i\)， 则 \(X\) 的期望值是：
\[E(X)=\sum_{i=1}^M i \times p_i
\]
发现 \(p_M\) 被加了 \(M\) 次， \(p_{M-1}\) 被加了 \(M-1\) 次，\(p_{M-2}\) 被加了 \(M-2\) 次……
一个类似后缀和之和的东西，可以写成
\[E(X)=\sum_{i=1}^{M}\sum_{j=i}^{M} p_j
\]
的形式
所以也就是
\[E(X)=\sum_{i=1}^{M}P(X\ge i)
\]
考虑枚举权值 \(X\)，那就只用算出对于每个 \(X\) 有 \(A_k\ge X\) 的概率即可
这相当于在操作 \(1\) 之后至少有 \(N+1-K\) 个 \(j\) 令 \(A_j\ge X\)
那二项式分布即可，减去原序列非 \(0\) 已经 \(\ge X\) 的个数，剩下的记为 \(p\)，再算出随机的数中至少有 \(p\) 个 \(\ge X\) 的概率
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int N = 5555;
const ll mod = 998244353;
int a[N];
int n, m, k;
ll binom[N][N];
ll f_pow(ll a, ll k = mod - 2){
ll base = 1;
for(; k; k >>= 1, a = (a * a) % mod){
if(k & 1)
base = (base * a) % mod;
}
return base;
}
void add(ll &x, ll k){
x += k;
if(x > mod)
x -= mod;
}
int main(){
for(int i = 0; i < N; i++){
binom[i][0] = 1;
for(int j = 1; j <= i; j++)
binom[i][j] = (binom[i-1][j-1] + binom[i-1][j]) % mod;
}
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
ll ans = 0;
ll invm = f_pow(m);
for(int X = 1; X <= m; X++){
int need = n - k + 1;
int zeronum = 0;
for(int j = 1; j <= n; j++){
if(a[j] >= X)
need--;
if(a[j] == 0)
zeronum++;
}
if(need < 0 || need > zeronum){
add(ans, need < 0 ? 1 : 0);
continue;
}
ll p = (m - X + 1) * invm % mod;
ll q = ((1 - p) % mod + mod) % mod;
for(int j = need; j <= zeronum; j++){
ll k = binom[zeronum][j] * f_pow(p, j) % mod * f_pow(q, zeronum - j) % mod;
k %= mod;
add(ans, k);
}
}
printf("%lld\n", ans % mod);
return 0;
}