[ARC212E] Drop Min 题解

我们需要对满足条件的

A

计数。这种“Drop Min 操作”形成的序列一眼看上去没什么很好的性质，于是先从操作入手：一个元素可以被操作（移除出

P

并加入

A

），当且仅当它的左边或者右边有元素比它大。

也就是说，如果一个元素

P_i

在

A

中出现，设左边第一个比它大的元素为

P_l

（如果有），右边第一个比它大的元素为

P_r

（如果有），则要么

P_{l+1\ldots i-1}

在

A

中均出现得比

P_i

靠前（如果

P_l

存在），要么

P_{i+1\ldots r-1}

在

A

中均出现得比

P_i

靠前（如果

P_r

存在）。

由于这个性质类似一个“区间二选一”，所以普通的 DP 肯定是行不通的。这个时候再次审查这个结构，发现它形如“

P_i

在中间，把

P_{l+1\ldots r-1}

划分成了左右两边，满足左右两边的元素都比它小”，这种划分成两边并具有特定大小关系的结构，启发我们考虑笛卡尔树上 DP。

重写一下条件：一个元素何时可以在

A

中出现，只取决于它两边的区间，即笛卡尔树上对应结点的两个儿子“管辖”的区间，是否有一边的所有元素在它之前出现——而这些元素确切的出现顺序并不重要。树的递归结构正好可以处理这样的问题：在进行 DP 时，不妨认为两棵子树各自内部元素的相对顺序已经排好了，即在当前结点处只需要做一个归并操作（左子树 / 右子树 / 自身），需要求的仅是合法的归并方案数。

建出

P

对应的大根笛卡尔树，此时 DP 的状态就很明确了：考虑一个结点

u

（这里的“结点

u

”指的是

P_u

对应的树上结点

(u,P_u)

），两个儿子为结点

v_l,v_r

，左右两边的区间大小为

L,R

；设

f_u

为

u

子树内元素的合法排列数，转移必然形如

f_u=k\cdot f_{v_l}\cdot f_{v_r}

，这个

k

就是在结点

u

处合法的归并方案数。由于前面提到了在

P

中可能有元素的左边 / 右边没有比它大的其他元素，故转移系数

k

的值需要分类讨论：

若左边和右边都没有比它大的元素，则代表它是 $P$ 中 $=N$ 的元素对应的结点；由于它最后留在了 $P$ 中（并没有进入 $A$ ），所以只用把两边以任意顺序归并起来而不用考虑自身，故 $k=C_{L+R}^{L}$ ；
若仅有左边有比它大的元素，则所有左边的元素都必须出现得比 $P_u$ 靠前：这个问题有个经典解法，从 $L+R+1$ 个位置中先选定 $R$ 个位置，把右边的 $R$ 个元素先固定在这些位置，于是左边的元素必然会在剩下位置中的前 $L$ 个（因为它们都要出现得比 $P_u$ 靠前），故 $k=C_{L+R+1}^{R}$ ；
若仅有右边有比它大的元素，与上一种情况对称，故 $k=C_{L+R+1}^{L}$ ；
若两边都有元素比它大，先尝试简单地把上面两种情况对应的系数相加，发现可能会算重，会被算两遍的即为子树内所有元素（自身除外）都在 $A$ 中比自身出现得靠前的方案数，为 $C_{L+R}^{L}$ ，扣掉就行了，故 $k=C_{L+R+1}^{R}+C_{L+R+1}^{L}-C_{L+R}^{L}$ 。

时间复杂度

O(N)

。

放代码：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=2e5,P=998244353;
static int fac[N+1],fi[N+1];
inline int add(int x,int y){
  int s=x+y; if(s>=P)s-=P; return s;
}
inline void self_add(int &x,int y){
  if((x+=y)>=P)x-=P;
}
inline int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=1ll*r*a%P;
    a=1ll*a*a%P,b>>=1;
  }
  return r;
}
inline int com(int n,int m){
  return n<m?0:1ll*fac[n]*fi[m]%P*fi[n-m]%P;
} // 计算组合数
vector<pii> cartesian_tree(vector<int> p){
  int n=p.size();
  vector<pii> a(n,make_pair(-1,-1));
  stack<pii> s;
  for(int i=0;i<n;i++){
    int l=-1;
    while(!s.empty()&&s.top().second<p[i])
      l=s.top().first,s.pop();
    a[i].first=l;
    if(!s.empty())a[s.top().first].second=i;
    s.emplace(i,p[i]);
  }
  return a;
} // 建出笛卡尔树
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  for(int i=fac[0]=1;i<=N;i++)
    fac[i]=1ll*fac[i-1]*i%P;
  fi[N]=qpow(fac[N],P-2);
  for(int i=N;i;i--)
    fi[i-1]=1ll*fi[i]*i%P;
  int n; cin>>n;
  vector<int> p(n);
  for(auto &i:p)cin>>i,i--;
  auto s=cartesian_tree(p);
  auto dfs=[&](auto &&self,int u,int l,int r,bool fl,bool fr)->int{
    if(u<0)return 1;
    int kl=self(self,s[u].first,l,u-1,fl,true),
      kr=self(self,s[u].second,u+1,r,true,fr);
    int c=0;
    if(!fl&&!fr)c=com(r-l,u-l); // 两边都没有
    if(fl)self_add(c,com(r-l+1,r-u)); // 左边有
    if(fr)self_add(c,com(r-l+1,u-l)); // 右边有
    if(fl&&fr)self_add(c,P-com(r-l,u-l)); // 两边都有，要扣掉算重的
    return 1ll*kl*kr%P*c%P;
  }; // 按照文中所述的方法进行 DP
  int u=find(p.begin(),p.end(),n-1)-p.begin();
  cout<<dfs(dfs,u,0,n-1,false,false)<<endl;
  return 0;
}

[ARC212E] Drop Min 题解

文章操作

相关推荐

评论

[ARC212E] Drop Min 题解