You are given an integer sequence $A = (A_1, \dots, A_N)$ of length $N$. Find the number, modulo $998244353$, of permutations $P = (P_1, \dots, P_N)$ of $(1, 2, \dots, N)$ such that:Problem Statement
Constraints
Input
Input is given from Standard Input in the following format:
$N$ $K$ $A_1$ $\ldots$ $A_N$
Output
Print the answer.
Sample Input 1
4 2 1 1 2 2
Sample Output 1
4
Four permutations satisfy the condition: $P = (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3)$.
Sample Input 2
10 3 3 1 4 1 5 9 2 6 5 3
Sample Output 2
697112
先提一个问题，如果保证给出来的是一个排列，有多少种可能？
考虑从小到大插入数字，这样能保证插入的时候这个数无论在已插入的数的哪里，都是最大的。定义 \(dp_{i,j}\) 为插入了前 \(i\) 大的数，此时有 \(j\) 个顺序对的方案数。
这个数有 \(j+1\) 中方式使答案不变，因为如果他插到了顺序对之间，或者查到了序列的末尾，顺序对数量不变。同理，有 \(i-j\) 种方式使顺序对数量加一。
那么排列的情况我们会了，不是排列怎么办？如果这个数前面有 \(c\) 个和他一样的，如果他插到了一个和他一样的数的后面，顺序对数量也不会增加。而插入的地方两边一定不是顺序对（至多相等）。所以方程变为 \(dp_{i,j}=dp_{i-1,j}\times (j+1+c)+dp_{i-1,j-1}\times (i-j-c)\)
#include<bits/stdc++.h>
using namespace std;
const int N=5005,P=998244353;
int n,k,dp[N][N],c[N],ans,inv[N],iv[N],a[N];//dp[i][j]表示按照从小到大顺序插入，已经插入前i大的数，有j个顺序对
int main()
{
scanf("%d%d",&n,&k);
for(int i=1,x;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
inv[1]=iv[1]=iv[0]=1;
for(int i=1;i<=n;i++)
{
inv[i]=1LL*(P-P/i)*inv[P%i]%P;
iv[i]=iv[i-1]*inv[i]%P;
}
dp[1][0]=1;
for(int i=2,cnt=0;i<=n;i++)
{
if(a[i]==a[i-1])
++cnt;
else
cnt=0;
for(int j=0;j<=k;j++)//
{
dp[i][j]=1LL*dp[i-1][j]*(j+1+cnt)%P;
if(j)
(dp[i][j]+=1LL*dp[i-1][j-1]*(i-j-cnt)%P)%=P;
}
}
ans=dp[n][k];
// printf("%d",ans);
// for(int i=1;i<=n;i++)
// ans=1LL*ans*iv[c[i]]%P;
printf("%d",ans);
return 0;
}