题解：CF2066D2 Club of Young Aircraft Builders (hard version)

weitianyi · 2025-10-11 22:44:13 · 题解

一道比较神奇的计数题。

我们经过适当转化后的题意可以变为：

在一个序列 a 中填数，有些位置已经填好了，填完数后的 a 要满足以下条件：

1. 对于任意 i \in [1, n]，满足 a_j \geq i 的 j 数量要不少于 c。

2. 对于任意 i \in [1, m]，满足 a_j \geq a_i, j < i 的 j 的数量要小于 c。

不难发现，条件 1 可以写成满足 a_j = n 的 j 的数量恰好为 c（同时结合了条件 2）。

对于这一类问题，我们考虑直方图 DP 的类似处理方式，对于每一个 i \in [1, n] 考虑 a 序列最终填完之后 a_j \geq i 的位置和 a_j = i 的位置来进行 DP。

Solution for easy version（a_i = 0）

直接考虑上面的过程，定义 f_{i, j} 表示考虑到第 i 层，a_p \geq i 的位置 p 有 j 个。考虑在 j 个位置中选出若干位置 p 满足 a_p = i，稍微分析一下性质就可以知道，在这 j 个位置中，只有前 c 个位置才可以放 =i 的元素，因此有以下显然的 DP：

• 枚举 k 表示满足 a_p = i 的 p 的数量，有：f_{i, j} \times \binom{c}{k} \rightarrow a_{i + 1,j - k}。
• 答案是 f_{n, c}。

时间复杂度为 O(nmc)，代码 1。

Solution for hard version

考虑上面的 DP 思路能否继续使用，我们发现如果依旧使用上面的记录方式 f_{i,j}，在前 c 个位置中我们不知道存在多少个位置满足不能填 i，于是这个 DP 就假了。

我们能否记录一些本质相同但是和位置相关的信息呢？显然这是可以的，我们魔改一下 DP 数组，记录 f_{i, j} 表示考虑 a_p \leq i 的所有位置以后第 c 个 >i 的位置是 j，这样我们得到的信息量就很大了！首先，所有 a_p = i + 1 的位置 p 只能在 j 之前填；其次，j 之前的空位数量恰好为 c；同时，在填完 i + 1 后 j 的新位置就是 j + t，t 表示填 i + 1 的数量。因此，我们可以进行 DP：

• 定义 x 为所有已经强制填的 a_p = i + 1 的数量，z 为所有 p \leq j 并且已经强制填的 a_p > i + 1 的数量，要求不存在强制填的 a_p = i + 1, p > j，有转移：f_{i, j} \times \binom{c - x - z}{y} \to f_{i+1, j + x + y}, y \in [0, c - x - z]。
• 答案为 f_{n-1, m}。

这个东西有点抽象，我大概想了 40min 才会，可以画图理解一下，时间复杂度为 O(nmk)，代码 2。