记录编号	612210	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	hope I can sort	最终得分	100
用户昵称	2_16鸡扒拌面	是否通过	通过
代码语言	C++	运行时间	0.800 s
提交时间	2026-02-11 14:58:39	内存使用	3.75 MiB

#include<bits/stdc++.h>
using namespace std;

const int MOD=998244353,N=5005;
int a[N],dp[N],nd[N];

int qp(int a,int b){
	int r=1;
	while(b){
		if(b&1)r=1ll*r*a%MOD;
		a=1ll*a*a%MOD;
		b>>=1;
	}
	return r;
}

int main(){
    freopen("hopeicansort.in","r",stdin);
    freopen("hopeicansort.out","w",stdout); 
	int n,m;
	cin>>n>>m;
	int c0=0;
	for(int i=1;i<=n;++i)
    {
		cin>>a[i];
		if(!a[i]) ++c0;
	}
	int k0=0;
	for(int i=1;i<=c0;++i) 
        if(a[i]) 
            ++k0;
	int mx=k0<c0?k0:n-c0;
	if(mx<k0) mx=k0;
	int T=1ll*n*(n-1)/2%MOD,invT=qp(T,MOD-2);
	dp[k0]=1;
	for(int t=0;t<m;++t)
    {
		for(int k=0;k<=mx;++k) nd[k]=0;
		nd[0]=(dp[0]+1ll*dp[1]*invT)%MOD;
		for(int k=1;k<=mx;++k)
        {
			int d=1ll*k*k%MOD*invT%MOD;
			nd[k]=(1ll*dp[k]*(1-d+MOD)+1ll*dp[k+1]*(k+1)%MOD*(k+1)%MOD*invT)%MOD;
		}
		for(int k=0;k<=mx;++k) dp[k]=nd[k];
	}
	cout<<dp[0];
	return 0;
}