P8321 『JROI-4』沈阳大街 2 做题记录

给定两个长度为 $n$ 的序列 $A,B$，满足：

• $\forall 1\le i<n,A_i \ge A_{i+1}$
• $A_n\ge \min\limits_{i=1}^n(B_i)$

$\pi$ 是一个长度为 $n$ 的排列，定义价值函数 $f(\pi)$：

$f(\pi)=\prod_{i=1}^n\min(A_i,B_{\pi(i)})$

每种排列出现的概率相等，求 $f(\pi)$ 的期望对 $998244353$ 取模的结果。

即求:

$\left(\dfrac{1}{n!}\sum_\pi f(\pi)\right) \bmod 998244353$

$1\le n\le 5000$，$1\le A_i,B_i\le 10^9$。

首先不难发现顺序是没有任何影响的，所以先把 $a$ 和 $b$ 一起放到一个数组 $c$ 里从大到小排序，并把从 $a$ 来的元素染红，从 $b$ 来的元素染蓝。

不难发现，问题转化为让所有红元素和蓝元素两两配对，每一对后面那个数乘起来的和。看到这种 $\sum\prod$ 的题就能想到提取公因数，考虑 $c_i$ 的贡献，显然只有当它和前面的元素配对的时候才会有贡献，那么我们设 $dp_{i,j}$ 表示前 $i$ 个元素，有 $j$ 个蓝元素没有配对的 $\sum\prod$，那么考虑 $i$ 的配对情况转移即可。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int p=998244353;
const int S=5005;

struct node
{
	int x,tpe;
}c[S*2];

int n,a[S],b[S];
int dp[S*2][S];

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=(y&1)?1ll*res*x%p:res;
	return res;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)
	{
		c[i*2-1]=(node){a[i],1};
		c[i*2]=(node){b[i],2};
	}
	sort(c+1,c+n*2+1,[&](node x,node y){return x.x>y.x;});
//	for(int i=1;i<=n*2;i++) printf("%d %d\n",c[i].x,c[i].tpe);
//	puts("---------------------------------------------");
	dp[0][0]=1;
	for(int i=1,cnt1=0;i<=n*2;i++)
	{
		cnt1+=c[i].tpe==1;
		int cnt2=i-cnt1;
		for(int j=0;j<=cnt2;j++)
		{
			if(c[i].tpe==1)
			{
				int bse=j+1;
				dp[i][j]=(dp[i-1][j]+1ll*dp[i-1][j+1]*c[i].x%p*bse%p)%p;
			}
			else
			{
				int bse=max(0,cnt1-(cnt2-1-j));
				dp[i][j]=1ll*dp[i-1][j]*c[i].x%p*bse%p;
				if(j>0) dp[i][j]=(dp[i][j]+dp[i-1][j-1])%p;
			}
//			printf("%d ",dp[i][j]);
		}
//		printf("\n");
	}
	int fra=1;
	for(int i=1;i<=n;i++) fra=1ll*fra*i%p;
	printf("%d\n",1ll*dp[n*2][0]*qpow(fra,p-2)%p);
	return 0;
}