P9084 [PA2018] Skwarki 题解

_•́へ•́╬_ · 2023-12-13 09:31:48 · 题解

思路

每次操作至多保留一半的数字，m>10 就无解了。

操作是删掉非局部峰顶，但是对着这个做肯定寄。

考虑笛卡尔树，每次删掉不是有两个儿子的。因为叶子肯定是局部谷底，有一个儿子的一定有个相邻的比他大。

但是边界比较特殊。如果说中间的点需要两个条件才能保留，那么边界就只需要一个，靠边的那侧免疫。

考虑到全局最大值一定是最后留下来的，我们枚举 n 的位置，两边分别算。我们并不在乎边界是在左边还是右边，设状态：f[i][j][0/1] 表示长度为 i 的排列 j 次删空有无边界的方案数。

转移直接枚举 i 的位置和左右两边的步数。总步数的计算详见代码。

code

#include<stdio.h>
#define N 1009
#define M 11
#define max(x,y) ((x)>(y)?(x):(y))
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,mod,c[N][N],ans;__int128 f[N][M][2];
main()
{
    read(n);read(m);read(mod);
    if(m>10)return putchar('0'),0;
    for(int i=0;i<N;++i)
    {
        c[i][0]=1;
        for(int j=1;j<=i;++j)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    }
    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,nxt;l<=m;++l)
        {
            nxt=k==l?k+1:max(k,l);
            f[i][nxt][0]+=f[j-1][k][0]*f[i-j][l][0]*c[i-1][j-1];
            nxt=max(k,l+1);
            f[i][nxt][1]+=f[j-1][k][1]*f[i-j][l][0]*c[i-1][j-1];
        }
        for(int j=0;j<=m;++j)f[i][j][0]%=mod,f[i][j][1]%=mod;
    }
    for(int j=1;j<=n;++j)for(int k=0;k<=m;++k)for(int l=0;l<=m;++l)
        if(max(k,l)==m)ans=(ans+(long long)(f[j-1][k][1])*f[n-j][l][1]%mod
            *c[n-1][j-1])%mod;
    printf("%d",ans);
}