题解：P12558 [UOI 2024] Heroes and Monsters

· · 题解

给定 n 个数 a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n，保证所有数均两两不同。

定义 ans_k 表示满足如下条件的 S\subseteq\{1,2,\cdots,n\},|S|=k 的集合 S 个数：

存在 1\sim n 的排列 p，满足：\begin{cases}a_i>b_{p_i}&(i\in S)\\[2pt]a_i<b_{p_i}& (i\not\in S)\end{cases}

求 ans_1,ans_2,\cdots,ans_n，对 998244353​ 取模。

首先将 a,b 按照从小到大排序。

依然先考虑判定性问题，如何判定 S​ 是否可行？

我们当然是直接贪心匹配，比如：最小的 S 内的 a 必须匹配最小的 b，最大的 T 内的 b 必须匹配最大的 a。

记 T = \{1, 2, \dots, n\} \setminus S，易知 S 合法的充要条件是：

此时我们可以枚举 |S|=m，然后 f_{i,j} 表示考虑前 i 个 a，有 j 个在集合 S 的方案数，时间复杂度 \mathcal{O}(n^3)​。

考虑优化，你发现每次 dp 的形式很类似，你每次重新做一遍很唐。

我们按照 b_{|S|} 把序列 a 划分成两个部分 a_1\sim a_k 和 a_{k+1}\sim a_n，其中 k 满足 a_k < b_{|S|} < a_{k+1}。

我们发现 a_1\sim a_k 天然能放进 T，a_{k+1}\sim a_n 天然能放进 S。

于是你只要考虑前缀是否放进 S，后缀是否放进 T。

我们只需要对前后缀分别做一个背包然后卷起来即可，这东西和 |S| 无关！就把前后缀独立开来了。

比如后缀记 g_{i,j} 表示 [i,n] 选了 j 个进 S 的方案数。如下转移：

时间复杂度 \mathcal{O}(n^2)​。这题还是一个拆条件独立的思想。代码很简单。

//洛谷 P12558
//https://www.luogu.com.cn/problem/P12558
#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=5005,mod=998244353;
int n,m,a[N],b[N],f[N][N],g[N][N],s[N];
inline void ad(int &x,int y){x+=y;(x>=mod)&&(x-=mod);}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
    for(auto A:{a,b})
    {
        for(int i=1;i<=n;i++) cin>>A[i];
        sort(A+1,A+1+n);
    }f[0][0]=g[n+1][0]=1;
    for(int i=1;i<=n;i++) for(int j=0;j<=i;j++)
        f[i][j]=f[i-1][j],(j&&a[i]>b[j])&&(ad(f[i][j],f[i-1][j-1]),1);
    for(int i=n;i;i--) for(int j=0;j<=n-i;j++) 
        g[i][j+1]=g[i+1][j],(a[i]<b[i+j])&&(ad(g[i][j],g[i+1][j]),1);
    for(int i=0,j=0;i<=n;i++)
    {
        while(j<n&&a[j+1]<b[i]) j++;
        for(int k=0;k<=i;k++) s[i]=(s[i]+1ll*f[j][k]*g[j+1][i-k])%mod;
    }
    for(int i=1;i<=n;i++) ad(s[i],s[i-1]);cin>>m;
    for(int l,r;m--;)
    {
        cin>>l>>r;int S=s[r];
        l&&(ad(S,mod-s[l-1]),1);cout<<S<<"\n";
    }
    return 0;
}