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

给定两个长度为 nn 的序列 A,BA,B,满足:

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

π\pi 是一个长度为 nn 的排列,定义价值函数 f(π)f(\pi)

f(π)=i=1nmin(Ai,Bπ(i))f(\pi)=\prod_{i=1}^n\min(A_i,B_{\pi(i)})

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

即求:

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

1n50001\le n\le 50001Ai,Bi1091\le A_i,B_i\le 10^9

首先不难发现顺序是没有任何影响的,所以先把 aabb 一起放到一个数组 cc 里从大到小排序,并把从 aa 来的元素染红,从 bb 来的元素染蓝。

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

代码如下:

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