算法
(期望、组合) $O(NM)$
其实这题实际上是组合问题,因为这里是等概率!
注意到第 $k$ 小的数为 $X$ $\Leftrightarrow$ $A_k$ 等于在满足 $\geqslant X$ 的数至少有 $k$ 个中最小的 $X$
而 $\geqslant X$ 的数至少有 $k$ 个 $\Leftrightarrow$ $< X$ 的个数不足 $k$ 个
可以考虑对所有的 $X$ 求出 $A_k \leqslant X$ 的概率是多少
$A_k \leqslant X$ 意味着不超过 $X$ 的数至少有 $k$ 个,所以我们求出在 $0$ 中至少有 $k’$ 个数不超过 $X$ 的概率即可!
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using mint = modint998244353;
// combination mod prime
struct modinv {
int n; vector<mint> d;
modinv(): n(2), d({0,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(-d[mint::mod()%n]*(mint::mod()/n)), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} invs;
struct modfact {
int n; vector<mint> d;
modfact(): n(2), d({1,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(d.back()*n), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} facts;
struct modfactinv {
int n; vector<mint> d;
modfactinv(): n(2), d({1,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(d.back()*invs(n)), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} ifacts;
mint comb(int n, int k) {
if (n < k || k < 0) return 0;
return facts(n)*ifacts(k)*ifacts(n-k);
}
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n);
rep(i, n) cin >> a[i];
int z = 0;
sort(a.rbegin(), a.rend());
while (a.size() and a.back() == 0) {
a.pop_back();
z++;
}
mint ans;
rep(x, m+1) {
int sm = 0;
for (int na : a) if (na <= x) sm++;
rep(i, z+1) {
if (sm+i < k) {
mint now = comb(z, i);
now *= mint(x).pow(i); // <= x 的贡献为 1,> x的贡献为 0
now *= mint(m-x).pow(z-i);
ans += now;
}
}
}
ans /= mint(m).pow(z);
cout << ans.val() << '\n';
return 0;
}