P9804_Skwarki题解

可能更洛谷的阅读体验

好题，写一篇题解记录一下。

首先考虑计数 DP，但是直接做发现不太好做，我们思考能否对删除操作进行进一步转化成好的条件取做。

对于原题目的限制，即只要一个数左右两侧一旦有一个大的就会被删，既有位置限制和数值限制。一步很妙的转化的就是将这个思想转成笛卡尔树，那么删除操作就是在笛卡尔树上删有儿子的点。

我们不妨设$g_{u}$ 表示删空$u$ 子树（包括$u$ 号点）的所需次数，因为题意表明删除操作是同时进行的，不难有如下转移：

$$g_{u}=\max\left\{ g_{\text{ls}},g_{\text{rs}},\min(g_{\text{ls}},g_{\text{rs}})+1 \right\}$$

其中 ls 表示左儿子，rs 表示右儿子，注意在没有左儿子和右儿子的时候要特判。

方程表明如下情况：

• $g_{\text{ls}},g_{\text{rs}}$：因为操作是并行的，我们可以直接对左右儿子删除操作取$\max$ 即可。
• 某一子树删除完毕后，花一次操作删根节点$u$ 让后把剩下子树接上去。

注意到删除最多删除树的一半节点，也就是当删除操作数量$k\le \log(n)$ 时才可能有解。

验证考虑分类讨论，讨论左右子树操作次数相同和不同的情况即可简明验证。不难发现的一点是答案一定是全局的最大值，并且一定作为叶子节点出现。

接下来我们考虑如何把它搬到计数 DP 上，真的在笛卡尔树上 DP 显然是不现实的，因为树的结构会改变。

我们利用笛卡尔树的性质：我们设一个区间$[l,r]$ 最大值的位置为$pos$，发现可以把区间分成$[l,pos]$和$[pos,r]$ 两个区间，并且两个区间互不影响，也就是说我左边怎么乱搞放数也不会影响右边的区间。这个时候全局最大值作为区间的端点出现。

我们利用笛卡尔树结构的特点，设$f(i,j,0/1)$ 表示$i$ 个元素的排列，恰好$j$ 次删空，全局最大值是否在区间的端点。

对于$f(i,j,0)$ 的转移，根据我们上面所述的笛卡尔树的节点，我们需要枚举区间的最大值的位置来进行转移，对于每个位置$k$ 在分配左儿子的方案有$\binom{i-1}{k-1}$ 种方案给乘起来，左儿子$f(k-1,l,0)$ 右儿子$f(i-k,r,0)$，其中$l,r$ 是枚举儿子区间最大值的位置，转移即可。

考虑$f(i,j,1)$ 的转移，我们不考虑区间端点到底在哪里，因为排列的对称性可以完全统计答案，那么转移只需统计左儿子或者右儿子任一出现最大值的方案数即可，再乘上$\binom{i-1}{k-1}$ 即可。

转移的$j$ 需要通过上面的$g$ 单独计算，答案统计仍枚举最大值转移即可，见代码，时间复杂度$O(n^{2}k^{2})$。

注意到$k$ 最大为$\log(n)$，那么时间复杂度就是$O(n^2 \log^{2} n)$，这个复杂度下会被卡常，需要减少取模操作。注意到转移方程可以前缀和优化，那么时间复杂度即为$O(n^{2} \log n)$，这里就不用关心了。

不同于一些连续段 DP，这种转移的技巧叫做枚举最大值转移，实质就是上面所提到的在笛卡尔树上排列的 DP 结构，这种题类型很少见，但是我可以推荐一道题供大家练习：CF1580B。

#include<bits/stdc++.h>
#define int __int128
using namespace std;
constexpr int MN=1520;
int f[MN][MN][2],pw[MN],inv[MN],n,K,nj,MOD;

template<typename type>
inline type read(type &x)
{
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return flag?x=-x:x;
}

template<typename type>
inline void write(type x)
{
    x<0?x=-x,putchar('-'):0;
    static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10;while(x);
    while(top) putchar(Stack[top--]|48);
}

int ksm(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=ret*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ret;
}

void init(){
    pw[0]=1;
    for(int i=1;i<MN;i++) pw[i]=pw[i-1]*i%MOD;
    inv[MN-1]=ksm(pw[MN-1],MOD-2);
    for(int i=MN-2;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%MOD;
    }
}

int getC(int a,int b){
    if(a<b) return 0;
    return pw[a]*inv[b]%MOD*inv[a-b]%MOD;
}

signed main(){
    read(n),read(K),read(MOD);
    if(K>__lg(n)+1){
        cout<<0;
        return 0;
    }
    init();
    f[0][0][0]=f[0][0][1]=1;
    for(int i=1;i<n;i++){
        for(int j=1;j<=i;j++){
            for(int l=0;l<=K;l++){
                for(int r=0;r<=K;r++){
                    // l和r枚举两个孩子区间最大值位置
                    nj=(l==r)?l+1:max(l,r);// 小 g 的凭借
                    f[i][nj][0]=(f[i][nj][0]+f[j-1][l][0]*f[i-j][r][0]*getC(i-1,j-1)%MOD)%MOD;
                    nj=max(l,r+1);
                    f[i][nj][1]=(f[i][nj][1]+f[j-1][l][1]*f[i-j][r][0]%MOD*getC(i-1,j-1)%MOD)%MOD;
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int l=0;l<=K;l++){
            for(int r=0;r<=K;r++){
                if(max(l,r)==K){
                    // 根据方程枚举区间拼接，可以看上面图理解
                    ans=(ans+(f[i-1][l][1]*f[n-i][r][1]%MOD*getC(n-1,i-1)%MOD))%MOD;
                }
            }
        }
    }
    write(ans);
    return 0;
}