ARC184D Erase Balls 2D 题解

Coffee_zzz · 2025-10-27 19:28:14 · 题解

将所有球按照 X_i 排序，那么第 i 个球满足 X_i=i。显然选择的球的顺序并不重要，我们只需要明确哪些球被选了。为了方便，我们在 (0,n+1) 和 (n+1,0) 处各添加一个球，并强制选择这两个球。

设选择的球所组成的集合为 S=\{a_1,a_2,\dots,a_m\}\ (0=a_1 \lt a_2 \lt \dots \lt a_m=n+1)，那么显然有 Y_{a_1}\gt Y_{a_2}\gt \dots \gt Y_{a_m}。

设剩余的球所组成的集合为 f(S)：

• 对于 u \in f(S) 且 x \not\in f(S)，设 a_j \lt u \lt a_{j+1}，则显然有 Y_{a_j}\gt Y_u \gt Y_{a_{j+1}}；
• 对于 v \not\in f(S)，设 a_j \lt v \lt a_{j+1}，则显然有 Y_{a_j} \lt Y_v 或 Y_v \lt Y_{a_{j+1}}。

直接对本质不同的 f(S) 进行计数比较困难，因此可以转化计数对象，对选择的球所组成的集合 S 进行计数。

显然不漏容易做到，于是问题变成了如何做到不重。考虑把 f(S) 的贡献转化到满足下列条件的集合 T 上：

• 对于任意 u \not\in T，f\big(\{u\} \cup T\big) \ne f(S)；换句话说，即再选择任意一个球都会导致 f(T) 变化。

显然满足条件的集合 T 是唯一的，因为了第二个条件相当于要求了集合 T 是极大的。

于是现在只需要统计有多少个集合 T 满足上面的条件即可。设 f_i 表示考虑完前 i 个球且选择了第 i 个球的满足条件的集合 T 的数量。转移时枚举 0 \le j \lt i 且 Y_j \gt Y_i 的整数 j，表示上一个选择的球为 j，判断是否能从 j 转移到 i：

• 若存在 j \lt k \lt i，使得对于任意 j \lt u \lt k 都不满足 Y_i \lt Y_u \lt Y_k 且对于任意 k \lt v \lt i 都不满足 Y_k \lt Y_v \lt Y_j（即选择 k 不会导致 f(T) 变化），则不能从 j 转移到 i，否则可以从 j 转移到 i。

于是做一个二维前缀和即可 \mathcal O(n) 检验是否能从 j 转移到 i。总时间复杂度 \mathcal O(n^3)。

const int N=305,mod=998244353;
int n,v[N],s[N][N],f[N];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
bool check(int ax,int ay,int bx,int by){
    return s[ax][ay]-s[ax][by-1]-s[bx-1][ay]+s[bx-1][by-1]==1;
}
void solve(){
    cin>>n,s[1][n+2]++,s[n+2][1]++,v[1]=n+2,v[n+2]=1;
    for(int i=1,x,y;i<=n;i++) cin>>x>>y,x++,y++,v[x]=y,s[x][y]++;
    for(int x=1;x<=n+2;x++) for(int y=1;y<=n+2;y++) s[x][y]=s[x][y]+s[x-1][y]+s[x][y-1]-s[x-1][y-1];
    f[1]=1;
    for(int i=2;i<=n+2;i++){
        for(int j=i-1;j>=1;j--){
            if(v[j]<v[i]) continue; 
            bool flag=1;
            for(int k=j+1;k<i;k++){
                if(check(k,v[k],j,v[i])&&check(i,v[j],k,v[k])){
                    flag=0;
                    break;
                }
            }
            if(flag) add(f[i],f[j]);
        }
    }
    cout<<f[n+2]<<endl;
}