题解：P9084 [PA 2018] Skwarki

chen_yu_hang · 2026-04-24 21:58:18 · 题解

解题思路

显然因为每次操作至少删去一半的数，所以当 k>\log_2n （即 k>10）时答案一定为 0。

然后我们发现如果考虑删除所有非峰值的话很难考虑。注意到留下的数满足的条件等价于在笛卡尔树上有 2 个儿子，注意边界只需要 1 个儿子。

于是我们定义状态 f_{i,j,0/1} 表示长度为 i 的区间删完需要 j 次操作，无（有）边界的方案数。由于左边是边界与右边是边界是镜像的，所以只用考虑有无边界。

考虑转移，枚举最大值的位置，将区间划分为两个子区间转移。定义 i 为区间长度，j 为最大值位置，k,l 为左右两个区间删完的次数，则转移为：

假如左右区间需要次数相同，最后还要一次删掉最大值，否则最大值一定会在某个区间删完前删掉。

类似的有：

当左区间先删完时，右区间删完后最大值才会删。当右区间删完时，最大值会在左区间删完前被删掉。

最后枚举一下最大值的位置，答案就是

时间复杂度 O(n^2m^2)

代码实现

#pragma GCC optimize("Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
#define lll __int128
using namespace std;
const int N=1010,M=20;
lll f[N][M][2];
ll c[N][N];
ll n,m,p;
void C_init()
{
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i;j++)
            if(!i||!j) c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>p;
    if(m>10)
    {
        cout<<0;
        return 0;
    }
    C_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 k=0;k<=m;k++)
                for(int l=0;l<=m;l++)
                {
                    ll nxt=k==l?k+1:max(k,l);
                    f[i][nxt][0]=(f[i][nxt][0]+f[j-1][k][0]*f[i-j][l][0]*c[i-1][j-1])%p;
                    nxt=max(k,l+1);
                    f[i][nxt][1]=(f[i][nxt][1]+f[j-1][k][1]*f[i-j][l][0]*c[i-1][j-1])%p;
                }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<m;j++)
        {
            ans=(ans+f[i-1][j][1]*f[n-i][m][1]*c[n-1][i-1])%p;
            ans=(ans+f[i-1][m][1]*f[n-i][j][1]*c[n-1][i-1])%p;
        }
        ans=(ans+f[i-1][m][1]*f[n-i][m][1]*c[n-1][i-1])%p;
    }
    cout<<ans;
    return 0;
}