自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:45:12，当前版本为作者最后更新于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);
}