【20联赛集训day10】排列

一个长度为 \(n\) 的排列，每次操作删除所有存在相邻的数字比它更大的数字，问执行 \(k\) 次操作后剩下恰好一个数的排列方案数。

首先因为每次删除至少删一半的数字，所以最多删 \(\log\) 次。

对于一个排列，我们可以发现把序列按最大值劈开，左右两边互不干扰，成为子问题。因此考虑 DP。

可以用笛卡尔树帮助理解，可以想象成在笛卡尔树上 DP。（这里的笛卡尔树是下标满足二叉搜索树性质，权值满足大跟堆，一棵子树一定是一个连续的区间）

\(dp_{i,j,0/1}\) 表示长度为 \(i\) 的序列，删除 \(j\) 次刚好删完，这个序列有没有一边碰到边界，的排列数量。

转移方程详见代码。

可以前缀和优化，时间复杂度 \(O(n^2\log n)\)。

Code

#include<bits/stdc++.h>
// #define DEBUG
#define int ll
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
using namespace std;
typedef long long ll;
const int N=1005,M=20;
int n;
int p,m;
int ans;
int c[N][N];
int dp[N][M][2],s[N][M][2];
void init(){
    c[0][0]=1;
    rep(i,1,n){
        rep(j,0,i){
            c[i][j]=(j-1>=0?c[i-1][j-1]:0)+c[i-1][j];
            c[i][j]%=p;
        }
    }
}
signed main(){
    #ifdef DEBUG
    freopen("ex_a1.in","r",stdin);
    // freopen("in.txt","r",stdin);
    freopen("my.out","w",stdout);
    #endif
    sf("%lld%lld%lld",&n,&m,&p);
    if(m>18) {
        pf("0\n");
        return 0;
    }
    init();
    dp[0][0][1]=dp[0][0][0]=1;
    rep(i,0,m){
        s[0][i][0]=s[0][i][1]=1;
    }
    rep(i,1,n-1){
        rep(j,1,m){
            rep(k,0,i-1){
                int x=2ll*(1ll*dp[k][j][0]*s[i-k-1][j-1][0]%p)%p+1ll*dp[k][j-1][0]*dp[i-k-1][j-1][0]%p;
                dp[i][j][0]+=1ll*x%p*c[i-1][k]%p;
                dp[i][j][0]%=p;
                int y=1ll*dp[k][j][1]*s[i-k-1][j-1][0]%p+1ll*dp[k][j-1][0]*s[i-k-1][j-1][1]%p;
                dp[i][j][1]+=1ll*y%p*c[i-1][k]%p;
                dp[i][j][1]%=p;
            }
            s[i][j][0]=(s[i][j-1][0]+dp[i][j][0])%p;
            s[i][j][1]=(s[i][j-1][1]+dp[i][j][1])%p;
        }
    }
    rep(k,0,n-1){
        int x=2ll*dp[k][m][1]*s[n-k-1][m-1][1]%p+1ll*dp[k][m][1]*dp[n-k-1][m][1]%p;
        ans+=1ll*x%p*c[n-1][k]%p;
        ans%=p;
    }
    pf("%lld\n",ans);
}