在跨年的晚上玩手机被妈妈骂了赶来写题……呜呜呜……但是A题了还是很开心啦，起码没有把去年的题目留到明年去做ヾ(◍°∇°◍)ﾉﾞ也祝大家2019快乐！
这题显然的 kth min-max 容斥就不说了，不会的还是百度吧……记录一下后面的 dp。感觉挺强强的，%题解……
首先，min - max 容斥的公式为 ： (max_{K}(S) = sum_{Tsubseteq S}(-1)^{|T|-K}inom{|T|-1}{K-1}min(T))
但是最后面的 (min(T)) 显然不能 (2 ^ {n}) 枚举，但又是非线性的求和。所以我们需要一点不一样的dp……考虑到 (n - K <= 10)，实际上也就是说在上面公式中出现的 (inom{|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}inom{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}inom{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}inom{i}{k - 1}*g_{x - 1, i, j - v})
因为我们有 (inom{n}{m} = inom{n - 1}{m}+inom{n - 1}{m - 1})
所以 (f_{x, j, k} - f_{x - 1, j- v, k - 1} = sum_{i = 1}(-1)^{i - k + 1}inom{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[2][maxm][20]; int ans, now, pre, p[maxn]; int inv[maxm], finv[maxm], fac[maxm]; int read() { int x = 0, k = 1; char c; c = getchar(); while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * k; } void Up(int &x, int y) { x = (x + y) % mod; if(x < 0) x += mod; } void init() { fac[0] = 1, inv[0] = inv[1] = 1; finv[0] = 1; for(int i = 1; i < maxm; i ++) fac[i] = fac[i - 1] * i % mod; for(int i = 2; i < maxm; i ++) inv[i] = (mod - mod / i) * inv[mod % i] % mod; for(int i = 1; i < maxm; i ++) finv[i] = finv[i - 1] * inv[i] % mod; } int C(int n, int m) { if(n < m || n < 0 || m < 0) return 0; return fac[n] * finv[m] % mod * finv[n - m] % mod; } int Qpow(int x, int timer) { int base = 1; for(; timer; timer >>= 1, x = x * x % mod) if(timer & 1) base = base * x % mod; return base; } void DP() { now = 1, pre = 0; f[pre][0][0] = 1; for(int i = 1; i <= n; i ++, swap(now, pre), f[pre][0][0] = 1) for(int j = 1; j <= m; j ++) for(int k = 1; 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 - 1]); Up(f[now][j][k], -f[pre][j - p[i]][k]); } } signed main() { n = read(), K = read(), m = read(); init(); for(int i = 1; i <= n; i ++) p[i] = read(); K = n - K + 1; DP(); for(int i = 1; i <= m; i ++) Up(ans, f[pre][i][K] * m % mod * inv[i] % mod); printf("%lld ", ans); return 0; }