给定两个长度为 的序列 ,满足:
是一个长度为 的排列,定义价值函数 :
每种排列出现的概率相等,求 的期望对 取模的结果。
即求:
,。
首先不难发现顺序是没有任何影响的,所以先把 和 一起放到一个数组 里从大到小排序,并把从 来的元素染红,从 来的元素染蓝。
不难发现,问题转化为让所有红元素和蓝元素两两配对,每一对后面那个数乘起来的和。看到这种 的题就能想到提取公因数,考虑 的贡献,显然只有当它和前面的元素配对的时候才会有贡献,那么我们设 表示前 个元素,有 个蓝元素没有配对的 ,那么考虑 的配对情况转移即可。
代码如下:
#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;
}