P8321 『JROI-4』沈阳大街 2 题解
Inaba_Meguru
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)$ 常数比较小，完结撒花。
## 参考代码
```cpp
#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;
}
```