前置知识
做这题前，您需要认识这个式子：
\[kthmax(S)=\sum_{\varnothing\neq T\subseteq S}{|T|-1\choose k-1} (-1)^{|T|-k} min(T)
\]
如果不会可以来这里。
思路
题目要求第\(k\)小。为了方便，以下令\(k=n-k+1\)，即变为求第\(k\)大。
很显然，这题是让我们求这个东西：
\[\sum_{T\neq\varnothing}{|T|-1\choose k-1} (-1)^{|T|-k} min(T)
\]
然而\(n \leq 1000\) 的数据很明显不能暴力枚举每一个\(T\)。为了优化复杂度，我们考虑一个类似于背包的\(DP\)。
设\(f_{x,j,k}\)表示前\(x\)个元素，满足\(\sum p=j\)，以\(k\)为基准的\(\sum_T {|T|-1 \choose k-1} (-1)^{|T|-k}\)的大小。可能你会奇怪为什么要记录\(k\)，先往后面看。
考虑转移。显然要根据\(T\)中是否有\(x\)这个元素进行分类讨论。
当\(T\)中没有\(x\)，直接转移，\(f_{x,j,k}+=f_{x-1,j,k}\)。
当\(T\)中有\(x\)时，显然前两维由\(f_{x-1,j-v}(v=p_x)\)转移而来，有
\[\begin{align*}
f'_{x,j,k}&=\sum_{x\in T} {|T|-1 \choose k-1}(-1)^{|T|-k}\\
&=\sum_T {|T| \choose k-1} (-1)^{|T|-k+1}//把x丢掉，转为考虑x-1时的T，此时\sum_p = j-v\\
&=\sum_T [{|T|-1 \choose k-1}+{|T|-1 \choose k-2}](-1)^{|T|-k+1}\\
&=\sum_T {|T|-1 \choose k-1}(-1)^{|T|-k}(-1)+\sum_T {|T|-1 \choose (k-1)-1} (-1)^{|T|-(k-1)}\\
&=f_{x-1,j-v,k-1}-f_{x-1,j-v,k}
\end{align*}
\]
最终我们得到转移方程：
\[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\)。
发现这东西时空复杂度都是\(O(nm(n-k))\)，似乎要炸空间，所以还需要把第一维滚掉。
最后统计答案时枚举\(\sum p\)然后随便搞搞就好啦。
代码
#include<bits/stdc++.h>
namespace my_std{
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,x,y) for (int i=(x);i>=(y);i--)
#define go(x) for (int i=head[x];i;i=edge[i].nxt)
#define sz 10010
#define mod 998244353
typedef long long ll;
template<typename T>
inline void read(T& t)
{
t=0;char f=0,ch=getchar();
double d=0.1;
while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
if(ch=='.')
{
ch=getchar();
while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();
}
t=(f?-t:t);
}
template<typename T,typename... Args>
inline void read(T& t,Args&... args){read(t); read(args...);}
void file()
{
#ifndef ONLINE_JUDGE
freopen("a.txt","r",stdin);
#endif
}
// inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;
ll ksm(ll x,int y)
{
ll ret=1;
for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;
return ret;
}
ll inv(ll x){return ksm(x,mod-2);}
int n,m,K;
int p[sz];
ll dp[2][sz][15];
int main()
{
file();
read(n,K,m);K=n-K+1;
rep(i,1,n) read(p[i]);
int c=0,cc=1;
dp[0][0][0]=1;
rep(i,1,n)
{
swap(c,cc);
rep(j,0,m) rep(k,0,K) dp[c][j][k]=0;
dp[c][0][0]=1;
rep(j,1,p[i]-1) rep(k,1,K) dp[c][j][k]=dp[cc][j][k];
rep(j,p[i],m)
rep(k,1,K)
dp[c][j][k]=(dp[cc][j][k]+dp[cc][j-p[i]][k-1]-dp[cc][j-p[i]][k]+mod)%mod;
}
ll ans=0;
rep(i,1,m) ans=(ans+dp[c][i][K]*inv(i)%mod*m%mod)%mod;
cout<<ans;
return 0;
}