abc295e
这题主要是一个小trick
\[E(x)= \sum P(x=i) \times i=\sum P(x \geq i)
\]
那么后面这个就很好算了
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const int N = 2005;
ll d[N], n, m, tot, x, c[N][N], k, ans, a[N][N];
ll power(ll a, ll b) {
ll t = 1, y = a % mo;
while (b) {
if (b & 1) t = t * y % mo;
y = y * y % mo;
b /= 2;
}
return t;
}
void solve(int x) {
ll sum = 0;
fo(i, 0, k - d[x - 1] - 1) {
sum = c[tot][i] * a[x - 1][i] % mo * a[m - x + 1][tot - i] % mo;
ans = (ans + sum) % mo;
}
}
int main()
{
// freopen("data.in","r",stdin);
scanf("%lld %lld %lld", &n, &m, &k);
fo(i, 1, n) {
scanf("%lld", &x);
d[x]++;
if (!x) tot++;
}
fo(i, 0, n) c[i][0] = 1;
fo(i, 1, n) {
fo(j, 1, i) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mo;
}
fo(i, 0, n) a[0][i] = 1;
fo(i, 1, m) {
a[i][0] = 1;
fo(j, 1, n) {
a[i][j] = a[i][j - 1] * (ll)i % mo;
}
}
d[0] = 0;
fo(i, 1, m) d[i] += d[i - 1];
fo(i, 2, m) {
if (d[i - 1] < k) {
solve(i);
}
}
ll inv = power(a[m][tot], mo - 2);
ans=ans*inv%mo;
ans=(ans+1)%mo;
printf("%lld", ans);
return 0;
}