【ZRC-524】全排列 / 题解

Description

有一个 $1$ 到 $n$ 的排列 $p_1,p_2,p_3,…,p_n$,你会对它进行若干轮操作,每一轮操作,你会保留序列中极大的数,也就是说对于每个数字,如果它比相邻的数字都大,那么会被保留下来。比如一个排列 $(3,2,5,1,4,6)$,经过一轮操作之后序列变成 $(3,5,6)$,第二轮操作之后序列变成 $(6)$,经过恰好 $2$ 轮之后序列里只有一个元素。

请问有多少个长度为 $n$ 的序列,经过恰好 $k$ 次操作之后,序列里只有一个元素,由于答案很大,对一个素数 $P$ 取模。

Idea

⾸先考虑给定⼀个排列,我们计算它⼏次会被消掉。

考虑这个排列的笛卡尔树,那么当⼀个数它的左⼦树或者右⼦树都被消掉的时候,它就会和它的祖先直接相邻,也就是⼀个⽐它⼤的数。

所以记 $dp[u]$ 表示笛卡尔树中 $u$ 这个点的⼦树什么时候被全部消完。那么有 $dp[u]=\max (dp[l],dp[r],\min (dp[l],dp[r])+1)$。

我们得到了⼀个 $\Theta(n)$ 的判断⼀个序列多少轮被消完的⽅法。

可以把这个 $dp$ 的过程直接改成计数。

令 $dp[u][k]$ 表示⼤⼩为 $u$ 的⼦树,能存活 $k$ 轮。$dp$ 的时候枚举最⼤值在哪⾥,分成左右两边计算。

因为最多存活 $\log n$ 轮,时间复杂度为 $\Theta(n^2\log ^2 n)$。

Code

#include <bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define maxn 1010
#define maxm 11
int f[maxn][maxm],g[maxn][maxm];
int c[maxn][maxn],n,m,p,ans;
void inc(int &x,int y){x+y>=p?x=x+y-p:x=x+y;}
int read(){
	int x=0,flag=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if (ch=='-') ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
	return x*flag;
}
int main(){
	n=read(),m=read(),p=read();
	for (int i=0;i<n;++i){
		c[i][0]=1;
		for (int j=1;j<=i;++j)
			inc(c[i][j],c[i-1][j]+c[i-1][j-1]);
	}
	f[0][0]=g[0][0]=f[1][1]=g[1][1]=1;
	for (int i=2;i<n;++i)
		for (int k,r,j,l=0;l<i;++l){
			r=i-l-1;k=c[i-1][l];
			for (int x=0;x<=m;++x) if (f[l][x]){
				for (int y=0;y<=m;++y) if (f[r][y]||g[r][y]){
					j=(x==y?x+1:max(x,y));
					inc(f[i][j],1ll*f[l][x]*f[r][y]%p*k%p);
					j=max(x+1,y);
					inc(g[i][j],1ll*f[l][x]*g[r][y]%p*k%p);
				}
			}
		}
	for (int k,r,l=0;l<n;++l){
		r=n-l-1;k=c[n-1][l];
		for (int x=0;x<m;++x) inc(ans,1ll*g[l][x]*g[r][m]%p*k%p);
		for (int x=0;x<m;++x) inc(ans,1ll*g[l][m]*g[r][x]%p*k%p);
		inc(ans,1ll*g[l][m]*g[r][m]%p*k%p);
	}
	printf("%d\n",ans);
	return 0;
}
Show Comments