自动搬运

查看原文

来自洛谷，原作者为

	Otomachi_Una_ We will never forget those days, thanks for everything.

搬运于2025-08-24 22:37:59，当前版本为作者最后更新于2022-05-08 17:00:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一道蒟蒻做不出来的喵喵题

题目简述

给定长度为 $n$ 的序列 $a,b$。$p$ 是 $1$ 到 $n$ 的排序，求：

$$(\dfrac{1}{n!} \sum_p \prod_{i=1}^n \min (a_i,b_{p_i})) $$

解题思路

我们把 $a,b$ 合并为一个新的数组 $c$。其中如果本来属于 $a$ 的染红，否则染蓝。对 $c$ 的数值从大到小排序，本题相当于这样的问题：

在 $c$ 中不重复的配对 $n$ 对红蓝对，配对的权值是后面的数的权值，求所有配对权值的和。

考虑 $\text{dp}$ 解决。假设 $f[i][j]$ 表示 $c[1,i]$ 当中配对了 $j$ 个的方案数。

转移方程：

$$f[i][j]=f[i-1][j-1]\times c[i]\times (tmp-(j-1))+f[i-1][j] $$

这里 $tmp$ 是 $c[1,i-1]$ 中与 $c[i]$ 不同色的数的个数。

时间复杂度 $\mathcal O(n^2)$ 常数比较小，完结撒花。

参考代码

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int MAXN=5e3+5;
const int MOD=998244353;
ll f[MAXN<<1][MAXN];
int cnt[2][MAXN*2];
struct element{
	ll val,sub; 
}a[MAXN<<1];int n,A;
bool cmp(element x,element y){
	return x.val>y.val;
} 
ll ksm(ll a,int b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b=b>>1;
	}
	return res;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>A,a[i]=element{A,0};
	for(int i=1;i<=n;i++)
		cin>>A,a[i+n]=element{A,1};
	sort(a+1,a+2*n+1,cmp);
	for(int i=1;i<=2*n;i++){
		cnt[0][i]=cnt[0][i-1],
		cnt[1][i]=cnt[1][i-1];
		cnt[a[i].sub][i]++;
	}
	f[0][0]=1;
	for(int i=1;i<=2*n;i++){
		ll tmp=cnt[!a[i].sub][i];
		f[i][0]=1;
		for(int j=1;j<=min(n,i);j++){
			if(j<=tmp)
				f[i][j]=f[i-1][j-1]*a[i].val%MOD*(tmp-(j-1))%MOD;
			f[i][j]=(f[i-1][j]+f[i][j])%MOD;
		}
	}
	ll res=1;
	for(int i=1;i<=n;i++)
		res=res*i%MOD;
	cout<<ksm(res,MOD-2)*f[2*n][n]%MOD;
	return 0;
}