首先我们可以考虑在已知原排列的情况下，如何判断这个序列是否能按题意得到 \(p\) 这个排列。设原排列为 \(q\)。
记 \(a_i\) 表示在 \(q\) 的第 \(i\) 个位置上，有多少个 \(j\) 满足 \(1 \leq j < i\) 且 \(q_j>q_i\)。如果所有的 \(a_i\) 都已经 \(\leq k\) 了，那么 \(q\) 就已经不能在操作了，此时就得不到 \(p\)。所以在 \(q\) 中一定有一些 \(a_i\) 是 \(> k\)。又因为必须要最小化操作数，所以对于每个 \(q_{i-1} > q_i\) 且 \(a_i > k\) 的位置都会把 \(q_i\) 与 \(q_{i-1}\) 交换，使 \(a_i\) 减少 \(1\)，直到 \(a_i\) 的值刚好 \(=k \) 时便不去动它了。而那些 \(a_i \leq k\) 的点我们肯定不会主动去动它，这样就能最小化操作数了。
记 \(b_i\) 表示在 \(p\) 中的 \(a_i\)。可以 \(\mathcal{O(n^2)}\) 预处理求出。
有了这个分析，就可以去考虑怎样通过 \(p\) 去推出原排列。由于 \(> k\) 的点一定会被最小操作次数变为 $ =k$，于是在 \(p\) 中 \(b_i = k\) 的点一定是从 \(\ge k\) 交换过来的，并且每一次交换都是从后面换到前面，所以这些点在原排列中可以是其后面 \(n-i+1\) 个点中的任意一个。再根据乘法原理，就可以得到原排列的个数为 \(\displaystyle\prod_{i=1}^{n}(n-i+1) \times [b_i=k]\)。
复杂度 \(\mathcal{O(n^2)}\)。
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
int n,k;
ll ans=1;
int p[5005];
int a[5005],b[5005],c[5005];
int main(){
cin>>n>>k;
for(int i=1;i<=n;++i)scanf("%d",&p[i]);
for(int i=1;i<=n;++i)for(int j=1;j<i;++j)if(p[j]>p[i])a[i]++;
for(int i=1;i<=n;++i)if(a[i]==k)ans=(ans*(ll)(n-i+1))%mod;
cout<<ans;
return 0;
}