题解：P9084 [PA 2018] Skwarki

· · 题解

尽量把其他题解含糊的点讲清楚一点。

容易发现删除的顺序是树状的，结合极值问题，可以考虑笛卡尔树。

建出一棵以下标为 k，以 A 为 w 的大根堆的笛卡尔树，验证发现确实如此。

有标记的元素在笛卡尔树上指的就是 son_u\le 1 的下标非边界的元素或者 son_u=0 的下标为边界的元素。

边界是动态变化的，但是可以由儿子转移到父亲。因为笛卡尔树的子树在区间上是连续的。

下标有 1 和 n 两种情况，似乎要四种状态，但是我们可以钦定为 1。因此状态为 f_{i,j,0/1} 表示 i 子树 j 次操作删到只剩 1 个，子树中是否存在边界，总方案数。

考虑转移：

f_{i,j,0}\leftarrow f_{i,j,0}+\sum\limits^{i-1}_k f_{k,j-1,0}\times f_{i-k-1,j-1,0}\times \binom{i-1}{k}

这个是显然的，枚举子树大小。

这是第一种情况，两个子树同时操作完，需要多耗费一次操作，所以是 j-1。

第二种情况是一个子树操作完之后节点直接被删除，所以是从 j 转移过来，此时另一个子树的操作数是不确定的。因此我们需要一个数组 g_{i,j,0/1}=\sum\limits^{j}_{k}f_{i,k,0/1}。

f_{i,j,0}\leftarrow f_{i,j,0}+\sum\limits^{i-1}_k f_{k,j,0}\times g_{i-k-1,j-1,0}\times\binom{i-1}{k}\times 2

对于存在边界的情况，前面已经提到了边界会转移，因此没有边界的那一边的子树是要先强制删完的，另一边则不确定。钦定左边为没有边界的就行。

f_{i,j,1}\leftarrow f_{i,j,1}+\sum\limits^{i-1}_k g_{k,j-1,1}\times f_{i-k-1,j-1,0}\times\binom{i-1}{k}

当然也同理地存在两种情况。

f_{i,j,1}\leftarrow f_{i,j,1}+\sum\limits^{i-1}_k f_{k,j,1}\times g_{i-k-1,j-1,0}\times\binom{i-1}{k}

答案是简单的，枚举根节点的两边子树大小即可，注意题目问的是恰好 k 次，所以要用 g_{i,k-1,1} 减去 g_{i,k-2,1}。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,mod,C[1005][1005],f[1005][1005][2],F[1005][1005][2],ans;
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m>>mod;
    if(m>10)
    {
        cout<<0;
        return 0;
    }
    C[0][0]=1,m++;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    f[0][0][0]=f[0][0][1]=f[1][1][0]=f[1][1][1]=F[0][0][0]=F[0][0][1]=1;
    for(int i=1;i<=m;i++)F[0][i][0]=F[0][i][1]=1,F[1][i][0]=F[1][i][1]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<i;k++)
            {
                f[i][j][0]=(f[i][j][0]+f[k][j-1][0]*f[i-k-1][j-1][0]%mod*C[i-1][k]%mod)%mod;
                f[i][j][0]=(f[i][j][0]+f[k][j][0]*F[i-k-1][j-1][0]%mod*C[i-1][k]%mod*2%mod)%mod;
                f[i][j][1]=(f[i][j][1]+F[k][j-1][1]*f[i-k-1][j-1][0]%mod*C[i-1][k]%mod)%mod;
                f[i][j][1]=(f[i][j][1]+f[k][j][1]*F[i-k-1][j-1][0]%mod*C[i-1][k]%mod)%mod;
            }
        }
        for(int j=1;j<=m;j++)F[i][j][0]=(F[i][j-1][0]+f[i][j][0])%mod,F[i][j][1]=(F[i][j-1][1]+f[i][j][1])%mod; 
    }
    for(int i=0;i<n;i++)
    {
        ans=(ans+F[i][m-1][1]*C[n-1][i]%mod*F[n-i-1][m-1][1]%mod)%mod;
        ans=(ans-F[i][m-2][1]*C[n-1][i]%mod*F[n-i-1][m-2][1]%mod+mod)%mod;
    }
    cout<<ans;
    return 0;
}