[COGS 4161] hope I can sort 题目解析

该问题本质是：   

- 每步随机选一对 \(i<j\)，仅当 \(a_i=1\) 且 \(a_j=0\) 时交换。  

- 交换只可能减少 \(k\)（前段错位 1 与后段错位 0 交换），不可能增加 \(k\)。  

- 状态转移概率为：  

                               \(P(k \to k-1) = \frac{k^2}{T}, \quad P(k \to k) = 1 - \frac{k^2}{T}\)

 其中T=n*(n+1)/2,即总共有多少组可以交换 

- 用 DP 计算 \(m\) 步后 \(k=0\) 的概率即可。  

- 复杂度 \(O(m \cdot \min(c_0,c_1))\)，可过。

本题中\(c_0,c_1\)代表0的个数和1的个数

#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;
}

 2026.2.11 创建题解