比赛在这 。

B.排列

前言：

笛卡尔树上 dp？这名字很妙啊，但其实不需要笛卡尔树，只不过利用了笛卡尔树的定义 。

一个性质：我们设一个区间 \([l,r]\) 中的最大值的位置为 \(pos\)，发现可以把该区间分为 \([l,pos]\) 和 \([pos,r]\) 两个子区间，并且这两部分互不影响，就是别管我左边怎么放数，不会对我的右边造成影响 。

注：如果你了解过笛卡尔树的话，那么下文所说区间都是指笛卡尔树上的区间； 如果你不知道笛卡尔树的话，我需要说：下文所说区间指一个数去向两边拓展，直到边上的数大于这个数 。

如下图整个区间分成了两个子区间 。

定义：

设 \(f_{i,j,0/1}\) 表示长度为 \(i\) 的区间用 \(j\) 次全部删完的方案数 。

1 表示该区间两边都挨着一个比该区间更大的数；0 表示一边挨着一个比区间内最大数更大的数，另一边是 \([1,n]\) 整个区间的边界 。

根据定义我们发现，显然我们没把 \([1,n]\) 整个区间囊括在 \(f\) 里，并且整个区间也不可能会有所有数全部删完的情况 。

所以最后整个区间的答案是要由它的两个子区间的的 dp 值单独计算的 。

考虑 dp 转移：

• 对于 \(f_{i,j,1}\) 的转移：我们枚举最大值在该区间第几个数的位置 \(k\)，对于每个 \(k\) 发现有 \(\tbinom{i-1}{k-1}\) 种方案（\(k-1\) 为最大值左侧区间数的个数） 。

  于是有转移:

  • 区间内最大值最后一个被删，那么左区间和右区间都是 \(j-1\) 次删完：
  \[f_{i,j,1} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (f_{k-1,j-1,1}\times f_{n-k,j-1,1}) \]
  • 右区间中的最大值最后一个被删，则大区间的最大值是被左区间一边的更大值在第 \(j\) 次之前删掉：
  \[f_{i,j,1} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (f_{n-k,j,1}\times \sum_{l=1}^{j-1} f_{k-1,l,1}) \]
  • 左区间中的最大值最后一个被删，同理：
  \[f_{i,j,1} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (f_{k-1,j,1}\times \sum_{l=1}^{j-1} f_{n-k,l,1}) \]

  后两种情况式子里的枚举求和可以直接前缀和优化，\(s\) 数组表示前缀合 。

  汇总一下转移就是:

  \[f_{i,j,1} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (f_{k-1,j-1,1}\times f_{n-k,j-1,1}+f_{n-k,j,1}\times s_{k-1,l,1}+f_{k-1,j,1}\times s_{n-k,l,1}) \]

• 对于 \(f_{i,j,0}\) 的转移：同样枚举最大值的位置，并且我们为避免重复，显然只应该计算一边为边界的情况，于是钦定左边为边界（ 。

  因为左区间的左边没有更大值，所以区间最大值只能被右区间的右边的更大值删掉，于是右区间里的数一定是在 \(j\) 次以内被删完的 。

  有转移:

  • 左区间在大区间最大值删掉之前被删：
  \[f_{i,j,0} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (\sum_{l=1}^{j-1} f_{k-1,l,0} \times f_{n-k,j-1,1}) \]
  • 左区间的最大值最后被删，于是中间最大值在 \(j\) 次以内被删，右区间所有数在 \(j-1\) 次以内被删完：
  \[f_{i,j,0} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (f_{k-1,j,0}\times \sum_{l=1}^{j-2} f_{n-k,l,1}) \]

  同样前缀和优化（ ，汇总一下:

  \[f_{i,j,0} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (s_{k-1,l,0}\times f_{n-k,j-1,1}+f_{k-1,j,0}\times s_{n-k,l,1}) \]

时间复杂度

发现每次操作至少删掉区间中一半的数量，所以一个长为 \(i\) 的区间最多 \(\log i\) 次被删完 。

dp 过程中枚举区间长度、删除次数、最大值位置，复杂度为 \(O(n^2 \log)\) 。

答案计算：

有两种情况

1. 两个子区间都是在 \(K\) 次被删完了 。

2. 一个子区间在 \(K\) 次被删完，而另一个在 \(K\) 次以内被删 。

code：

#include<bits/stdc++.h>
#define Aqrfre(x, y) freopen(#x ".in", "r", stdin),freopen(#y ".out", "w", stdout)
#define mp make_pair
#define Type ll
#define qr(x) x=read()
typedef __int128 INT;
typedef long long ll;
using namespace std;

inline ll read(){
    char c=getchar(); ll x=0, f=1;
    while(!isdigit(c)) (c=='-'?f=-1:f=1), c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48), c=getchar();
    return x*f;
}

const int N = 1005; 

int T, n, K, p, C[N][N];
int f[N][22][2], s[N][22][2];

inline void AqrPre(){
    C[0][0] = 1;
    for(int i=1; i<=n; i++){
        C[i][0] = 1;
        for(int j=1; j<=i; j++){
            C[i][j] = (ll)(C[i-1][j] + C[i-1][j-1]) % p;
        }
    }
}

inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return res;
}

signed main(){ // a
    // Aqrfre(a, a);

    qr(n); qr(K); qr(p);
    
    if(K > 10){
        puts("0"); return 0;
    }
    if(K == 1){
        cout<<qpow(2, n - 1); return 0;
    }
    AqrPre();

    f[0][0][0] = f[0][0][1] = 1;
    for(int i=0; i<=K; i++) s[0][i][0] = s[0][i][1] = 1;

    for(int i=1; i<n; i++){
        for(int j=1; j<=K; j++){
            for(int k=1; k<=i; k++){
                f[i][j][1] = (f[i][j][1] + 1ll * C[i-1][k-1] * \
                        ( 1ll * f[k-1][j-1][1] * f[i-k][j-1][1] % p
                        + 1ll * f[k-1][j][1] * s[i-k][j-1][1] % p
                        + 1ll * s[k-1][j-1][1] * f[i-k][j][1] % p) % p) % p;

                f[i][j][0] = (f[i][j][0] + 1ll * C[i-1][k-1] * \
                        ( 1ll * s[k-1][j][0] * f[i-k][j-1][1] % p
                        + (j >= 2 ? 1ll * f[k-1][j][0] * s[i-k][j-2][1] : 0) % p) % p) % p;
            }

            s[i][j][1] = (s[i][j-1][1] + f[i][j][1]) % p;
            s[i][j][0] = (s[i][j-1][0] + f[i][j][0]) % p;
        }
    }
    
    int ans = 0;
    for(int i=1; i<=n; i++){
        ans = (ll)(ans + 1ll * C[n-1][i-1] *
        (1ll * f[i-1][K][0] * f[n-i][K][0] % p
       + 1ll * f[i-1][K][0] * s[n-i][K-1][0] % p
	   + 1ll * s[i-1][K-1][0] * f[n-i][K][0] % p) % p) % p;
    }
    cout<<ans<<"\n";
    

    return 0;
}

最后此篇关于【排列】（笛卡尔树上dp？）的文章就讲到这里了,如果你想了解更多关于【排列】（笛卡尔树上dp？）的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。