P8321 『JROI-4』沈阳大街 2 题解

· · 题解

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

题目简述

给定长度为 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;
}