在跨年的晚上玩手机被妈妈骂了赶来写题……呜呜呜……但是A题了还是很开心啦，起码没有把去年的题目留到明年去做ヾ(◍°∇°◍)ﾉﾞ也祝大家2019快乐！
这题显然的 kth min-max 容斥就不说了，不会的还是百度吧……记录一下后面的 dp。感觉挺强强的，%题解……
首先，min - max 容斥的公式为 ： \(max_{K}(S) = \sum_{T\subseteq S}(-1)^{|T|-K}\binom{|T|-1}{K-1}min(T)\)
但是最后面的 \(min(T)\) 显然不能 \(2 ^ {n}\) 枚举，但又是非线性的求和。所以我们需要一点不一样的dp……考虑到 \(n - K <= 10\)，实际上也就是说在上面公式中出现的 \(\binom{|T| - 1}{K - 1}\) 中的 \(K - 1\) 最大不会超过 11。从这个地方入手，设 在前 \(x\) 个元素组成的集合中， \(g_{x, i, j}\) 为所有 \(min(T) = j\) 且 \(|T| = i\) 的子集的方案数，
而\(f_{x, j, k} = \sum_{i = 1}(-1)^{i - k}\binom{i - 1}{k - 1}*g_{x, i, j}\)
考虑向集合中加入第 \(i\) 个元素，不加入的直接继承上一次的。
加入的则需要分析一下（下面的就只讨论包含第 \(i\) 个元素的情况）
考虑从 \(f_{x - 1, j - v, k - 1}\) 转移过来（\(v\) 为 \(p[i]\)）
分析：\(f_{x - 1, j - v, k - 1} = \sum_{i = 1}(-1)^{i - k + 1}\binom{i - 1}{k - 2}*g_{x - 1, i, j - v}\)
为了便于观察，我们尽量把 \(f_{x, j, k}\) 也写成一样的形式
\(f_{x, j, k} = \sum_{i = 1}(-1)^{i - k + 1}\binom{i}{k - 1}*g_{x - 1, i, j - v}\)
因为我们有 \(\binom{n}{m} = \binom{n - 1}{m}+\binom{n - 1}{m - 1}\)
所以 \(f_{x, j, k} - f_{x - 1, j- v, k - 1} = \sum_{i = 1}(-1)^{i - k + 1}\binom{i - 1}{k - 1}*g_{x, i, j - v} = -f_{x - 1, j - v, k}\)
所以，完整的式子是：
\(f_{x, j, k} = f_{x - 1, j, k} + f_{x - 1, j - v, k - 1} - f_{x - 1, j - v, k}\)
这样就可以愉快地递推啦。不过还有一个小小的细节，就是边界的问题。我们只需要每次保存 \(f_{x, 0, 0} = 1\) 即可，因为会从 \(0\) 转移出去的当且仅当 \(v = j\) 即集合中仅有一个元素时。此时显然有 \(f_{x, p[x], 1} = 1\)。
#include <bits/stdc++.h>
using namespace std;
#define maxn 2005
#define maxm 20000
#define mod 998244353
#define int long long
int n, K, m, f[][maxm][];
int ans, now, pre, p[maxn];
int inv[maxm], finv[maxm], fac[maxm]; int read()
{
int x = , k = ;
char c; c = getchar();
while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * k;
} void Up(int &x, int y) { x = (x + y) % mod; if(x < ) x += mod; }
void init()
{
fac[] = , inv[] = inv[] = ; finv[] = ;
for(int i = ; i < maxm; i ++) fac[i] = fac[i - ] * i % mod;
for(int i = ; i < maxm; i ++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for(int i = ; i < maxm; i ++) finv[i] = finv[i - ] * inv[i] % mod;
} int C(int n, int m)
{
if(n < m || n < || m < ) return ;
return fac[n] * finv[m] % mod * finv[n - m] % mod;
} int Qpow(int x, int timer)
{
int base = ;
for(; timer; timer >>= , x = x * x % mod)
if(timer & ) base = base * x % mod;
return base;
} void DP()
{
now = , pre = ; f[pre][][] = ;
for(int i = ; i <= n; i ++, swap(now, pre), f[pre][][] = )
for(int j = ; j <= m; j ++)
for(int k = ; k <= K; k ++)
{
f[now][j][k] = f[pre][j][k];
if(j < p[i]) continue;
Up(f[now][j][k], f[pre][j - p[i]][k - ]);
Up(f[now][j][k], -f[pre][j - p[i]][k]);
}
} signed main()
{
n = read(), K = read(), m = read(); init();
for(int i = ; i <= n; i ++) p[i] = read();
K = n - K + ; DP();
for(int i = ; i <= m; i ++)
Up(ans, f[pre][i][K] * m % mod * inv[i] % mod);
printf("%lld\n", ans);
return ;
}