「Skwarki」题解

题目大意

给定一个长度为 $N$ 的排列，反复执行以下操作：

• 标记所有“非局部极大值”的元素（即比某个邻居小的元素），然后删除标记的元素。
• 重复直到只剩一个元素。

问有多少个排列至少需要 $K$ 次操作才能变成只剩一个元素。结果对 $P$ 取模。

数据范围：$1 \le K, N \le 1000$，$10^8 \le P \le 10^9$。

问题转化

一次操作会保留所有局部极大值。
这个过程等价于每次删除所有不是当前序列局部峰值的元素。

通过观察，这个问题与排列的笛卡尔树有密切关系：

• 每个排列对应一棵笛卡尔树，根是全局最大值。
• 左子树是最大值左边的子排列，右子树是右边的子排列。
• 在删除过程中，一个元素会在它所在的子树中成为全局最大值时被删除。

因此，问题转化为：

在排列的笛卡尔树中，根节点的深度至少为 $K$ 的排列有多少个？

这里“深度”定义为从根到该节点经过的边数（根深度为0），而题目中“操作次数”对应的是根节点被删除的时刻，也就是深度 $+1$。

动态规划设计

定义状态：

• f[i][d][t] 表示长度为 $i$ 的排列，其笛卡尔树根节点深度为 $d$，且：
  • t = 0：该子树的根节点比父节点先删除（即父节点更大）
  • t = 1：该子树的根节点比父节点后删除（即父节点更小）

状态转移

考虑长度为 $i$ 的排列，最大值在位置 $j$（$1 \le j \le i$）：

• 左子树长度为 $j-1$，右子树长度为 $i-j$
• 组合数系数为 $C_{i-1}^{j-1}$（选择左边哪些元素）

情况 1：f[i][max(k,l)+(k==l)][0]

• 来自 f[j-1][k][0] 和 f[i-j][l][0]
• 两个子树根都比当前根先删除，所以当前根的深度 = max(k,l) + (k==l)
  （如果两边深度相等，当前根深度+1）

情况 2：f[i][max(k,l+1)][1]

• 来自 f[j-1][k][1] 和 f[i-j][l][0]
• 左子树根比当前根后删除，右子树根比当前根先删除
• 当前根深度 = max(k, l+1)

最终答案

对于整个排列（没有父节点约束），我们枚举最大值位置 $i$：

• 左子树 f[i-1][j][1]（根比父节点后删除）
• 右子树 f[n-i][k][1]（根比父节点后删除）
• 如果 max(j,k) == m（这里 $m=K$），则根深度满足条件
• 乘以组合数 $C_{n-1}^{i-1}$

将所有满足条件的方案数相加即为答案。

复杂度分析

• 状态数：$O(N^2 \cdot K)$
• 转移：$O(N^3 \cdot K)$ 但实际有优化
• 由于 $N, K \le 1000$，且代码中当 $m > 10$ 时直接输出 0（因为深度不会太大），实际可运行

代码实现要点

#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 15;
int n, m, p, f[N][M][2], C[N][N], ans;

void add(int &x, int y) {
    if ((x += y) >= p) x -= p;
}

int main() {
    scanf("%d%d%d", &n, &m, &p);
    if (m > 10) return puts("0"), 0; // 深度不会超过 logN，这里保守取 10
    
    // 初始化
    f[0][0][0] = f[0][0][1] = 1;
    // 组合数预处理
    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] + C[i-1][j-1]) % p;
    }
    
    // DP 转移
    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; l <= m; l++) {
                    add(f[i][max(k,l) + (k==l)][0],
                        1LL * f[j-1][k][0] * f[i-j][l][0] % p * C[i-1][j-1] % p);
                    add(f[i][max(k,l+1)][1],
                        1LL * f[j-1][k][1] * f[i-j][l][0] % p * C[i-1][j-1] % p);
                }
            }
        }
    }
    
    // 统计答案
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= m; k++) {
                if (max(j,k) == m) {
                    add(ans, 1LL * f[i-1][j][1] * f[n-i][k][1] % p * C[n-1][i-1] % p);
                }
            }
        }
    }
    
    printf("%d", ans);
    return 0;
}

总结

本题的关键在于将删除过程转化为笛卡尔树上的深度问题，然后通过动态规划枚举最大值位置和子树深度来统计方案数。这种方法结合了组合数学（组合数、笛卡尔树）和动态规划的技巧，是典型的计数 DP 问题。