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

Coffee_zzz · 2025-11-06 20:42:54 · 题解

考虑把 a_i 看作 1 类数，b_i 看作 2 类数，将所有 a_i 和所有 b_i 扔进一个长度为 2n 的数列 c 中并从大到小排序，每次选出一个 1 类数和 2 类数进行匹配，贡献乘上较小的数的值，将问题转化为求所有匹配方案的贡献之和。

设 f_{i,j} 表示考虑到数列 c 的第 i 项，此时一共匹配了 j 对数的方案的贡献的和。转移时，首先根据 i,j 和前缀和数组，计算出未匹配的 1 类数数量 x 和未匹配的 2 类数数量 y，再根据 c_{i+1} 的类型分别处理：

• 若 c_{i+1} 为 1 类数：
  • 若 y>0：对 c_{i+1} 进行匹配，f_{i+1,j+1} \leftarrow f_{i+1,j+1}+y\times c_{i+1} \times f_{i,j}；
  • 不对 c_{i+1} 进行匹配，f_{i+1,j} \leftarrow f_{i+1,j}+f_{i,j}。
• 若 c_{i+1} 为 2 类数：
  • 若 x>0：对 c_{i+1} 进行匹配，f_{i+1,j+1} \leftarrow f_{i+1,j+1}+x\times c_{i+1} \times f_{i,j}；
  • 不对 c_{i+1} 进行匹配，f_{i+1,j} \leftarrow f_{i+1,j}+f_{i,j}。

初始化 f_{0,0}=0，答案即为 f_{2n,n}。

时间复杂度 \mathcal O(n^2)。

const int N=5005,mod=998244353;
int n,f[N<<1][N],s[N<<1][3];
pii p[N<<1];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1,a=1ll*a*a%mod;
    }
    return res;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i].fi,p[i].se=1;
    for(int i=1;i<=n;i++) cin>>p[n+i].fi,p[n+i].se=2;
    sort(p+1,p+n+n+1),reverse(p+1,p+n+n+1);
    for(int i=1;i<=n+n;i++) for(int k=1;k<=2;k++) s[i][k]=s[i-1][k]+(p[i].se==k);
    f[0][0]=1;
    for(int i=0;i<n+n;i++){
        for(int j=0;j<=min(s[i][1],s[i][2]);j++){
            int x=s[i][1]-j,y=s[i][2]-j;
            if(p[i+1].se==1){
                if(y>0) add(f[i+1][j+1],1ll*y*p[i+1].fi%mod*f[i][j]%mod);
                add(f[i+1][j],f[i][j]);
            }
            else{
                if(x>0) add(f[i+1][j+1],1ll*x*p[i+1].fi%mod*f[i][j]%mod);
                add(f[i+1][j],f[i][j]);
            }
        }
    }
    int fac=1;
    for(int i=1;i<=n;i++) fac=1ll*fac*i%mod;
    cout<<1ll*ksm(fac,mod-2)*f[n+n][n]%mod<<endl;
}