考虑重新刻画一个序列的生成，设原数列为 \((0,0)\)，将所有数从小到大排序后依次加入。
例如 \((2,3,1)\) 是这样生成的：
\[(0,0)\to(0,1,0)\to(0,2,1,0)\to(0,2,3,1,0) \]于是问题变成多少种方案使得这样的序列存在 \(k+1\) 个位置 \(i\) 满足 \(a_i\lt a_{i+1}\)。
设 \(f_{i,j}\) 表示插入了前 \(i\) 小的数字，存在 \(j\) 个位置满足前一个小于后一个。
考虑如何从 \(i\) 转移到 \(i+1\)。
令 \(cnt\) 表示当前序列中有多少个数字和 \(a_i\) 相同，\(x=cnt+j\)，\(y=i+1-x\)，\(x\) 的含义是多少个空插进去使得满足条件的位置不变，\(y\) 的含义是多少个空插进去使得满足条件的位置增加 \(1\)，手玩一下不难得到。则有 \(f_{i+1,j}\gets f_{i+1,j}+f_{i,j}\times x,f_{i+1,j+1}\gets f_{i+1,j+1}+f_{i,j}\times y\)。
转移跟 \(i\) 没关系，直接把 \(i\) 这一维去掉就好了，最终答案就是 \(f_{k+1}\)。
时间复杂度 \(\mathcal O(n^2)\)。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5005, mod = 998244353;
int n, k;
int a[N];
int f[N], g[N];
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int mul(int a, int b) { return 1ll * a * b % mod; }
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
sort(a, a + n);
f[0] = 1;
int lst = 0, cnt = 0;
for (int i = 0; i < n; ++i) {
if (lst != a[i]) {
cnt = 0;
lst = a[i];
}
memset(g, 0, sizeof (int) * (i + 2));
for (int j = 0; j <= i; ++j) {
int t = f[j];
if (!t) continue;
int x = cnt + j, y = (i + 1) - x;
g[j] = add(g[j], mul(t, x)), g[j + 1] = add(g[j + 1], mul(t, y));
}
++cnt;
memcpy(f, g, sizeof (int) * (i + 2));
}
printf("%d", f[k + 1]);
return 0;
}