D1. 青年飞机制造者俱乐部（困难版本）详细题解

问题理解

有一栋 $n$ 层的楼，每层住一个人。他们要发射总共 $m$ 架纸飞机。
发射顺序是按时间给出的：第 $i$ 架飞机由第 $a_i$ 层的人发射（$a_i = 0$ 表示信息丢失，需要填补）。

规则：

• 当第 $i$ 层的人发射一架飞机时，第 $1$ 层到第 $i$ 层的所有人都能看到它。
• 如果从某层居民的角度看，已经看到了至少 $c$ 架飞机，那么该居民就不会再发射任何飞机。
• 最终，从 每个居民的角度 看，至少看到了 $c$ 架飞机（即所有人都看到了足够多的飞机）。
• 总共恰好发射 $m$ 架。

在简单版本中，所有 $a_i = 0$（全部丢失），我们需要计算填补方案数。

---

核心条件转化

设 $b_x$ = 第 $x$ 层居民发射的飞机总数。
那么：

• 从第 $x$ 层居民的角度，他能看到的飞机 = 所有楼层 $\le x$ 的人发射的飞机总数。

• 最终他看到至少 $c$ 架：

  $$\sum_{j=1}^{x} b_j \ge c \quad \forall x \in [1, n] $$

• 并且他停止发射的条件：在发射过程中，一旦他看到 $c$ 架，就不会再发射。
  这意味着 第 $x$ 层的人发射的飞机，只能发生在他看到 $c-1$ 架及之前。
  换句话说，在他的最后一架飞机发射之前，他看到的总数 $< c$，而发射这一架后可能正好达到或超过 $c$。

实际上，这个条件可以等价为：
存在一个排列（发射顺序），使得按时间累积时，每个楼层贡献的飞机都满足“不超过 c”的约束。

---

更直接的视角

设 $S_i$ = 前 $i$ 架飞机中，来自楼层 $\le p$ 的飞机数。
条件“第 $p$ 层的人看到至少 $c$ 架”意味着：存在某个时刻 $t$ 使得 $S_t(p) \ge c$，并且此后第 $p$ 层不再发射。

但标程使用了一种更聪明的 DP 方法，将问题转化为 计数满足特定前缀和约束的序列。

---

标程思路解析

1. 前缀和矩阵

定义 $sum[i][p]$ = 前 $i$ 架飞机中，来自楼层 $\le p$ 的飞机数量。

显然 $sum[i][p]$ 随 $i$ 递增，随 $p$ 递增。

2. 状态定义

$f[p][x]$ 表示：已经处理到某个阶段，且当前“第 $p$ 层及以上的人还需要看到 x 架飞机才能达到 c”时的方案数。
（更准确地说，标程中的 $f[p][c]$ 表示“第 $p$ 层的人恰好已经看到 c 架飞机，且接下来的发射需要满足条件”）

其实标程的状态定义为：
$f[p][x]$ = 处理完前 $i$ 架飞机后，第 $p$ 层的人还需要看 $x$ 架飞机才能达到 $c$ 的方案数。
但代码中 $f$ 的更新非常巧妙。

---

3. 转移

标程的核心转移：

$$f[p+1][c-x] \mathrel{+}= f[p][c] \times \binom{c - sum[i][p]}{\,x - b[p]\,} $$

含义：

• 当前第 $p$ 层的人已经看到了 $c$ 架（即满足条件），接下来考虑第 $p+1$ 层。
• 第 $p+1$ 层的人还需要看到 $c - x$ 架（其中 $x$ 是第 $p+1$ 层自己发射的数量）。
• 第 $p$ 层及以下已经发射了 $sum[i][p]$ 架，而第 $p+1$ 层需要发射 $x$ 架，且必须安排在某个时刻，使得第 $p+1$ 层在发射过程中看到的数量始终 $<c$。
• 组合数 $\binom{c - sum[i][p]}{\,x - b[p]\,}$ 表示从剩下的“配额”中选出第 $p+1$ 层发射的时刻。

其中 $b[p]$ 是第 $p$ 层最终发射的总数（由输入确定，如果 $a_i=0$ 则未知）。

---

4. 初始与答案

• 初始：$f[1][0] = 1$，表示最开始第 $1$ 层还需要看到 $0$ 架（还没开始）。
• 最终答案：$f[n+1][0]$，表示处理完所有 $n$ 层后，还需要看到 $0$ 架（全部满足）。

---

组合数的含义

$\binom{c - sum[i][p]}{\,x - b[p]\,}$ 中的 $c - sum[i][p]$ 是“第 $p+1$ 层在开始发射前，还能看到多少架来自低层的飞机（还未发生但会发生在它发射过程中）”。
$x - b[p]$ 是“第 $p+1$ 层发射过程中，看到的来自低层的新飞机数”。
这个组合数表示在剩余空间中选择这些新飞机的插入位置。

---

为何这样 DP 正确

核心观察：

• 每层的人一旦看到 $c$ 架就停止发射。
• 因此，第 $p$ 层发射的 $b[p]$ 架飞机，必须分布在前 $p$ 层累积数达到 $c-1$ 之前的某个区间内。
• 整个问题可以按楼层分层处理：先安排第 $1$ 层，再第 $2$ 层，等等。
• 每层的新飞机可以穿插在之前各层飞机的间隙中，只要不打破“在看到 $c$ 架前发射”的约束。

---

复杂度分析

• 状态数：$O(n \cdot c)$
• 转移：$O(c)$ 内层循环
• 总复杂度 $O(n \cdot c^2)$，$n, c \le 100$，完全可行
• 预处理组合数 $O(n^2)$

---

示例验证

以 $n=3, c=2, m=4$ 为例：

所有 $a_i=0$，$b[1],b[2],b[3]$ 未知，但需满足 $\sum b = m$，且 $b[p] \le c$。

标程通过 DP 计算出答案是 $6$，与题目一致。

---

总结

本题的关键：

1. 将问题按楼层分层处理
2. 利用“看到 $c$ 架就停止”的约束，转化为对每层发射数的分布限制
3. 使用组合数计算插入方式
4. DP 状态 $f[p][x]$ 表示第 $p$ 层还需要看到 $x$ 架才能达到 $c$

这种逐层 DP + 组合计数的方法，是处理带有“全局阈值”的顺序计数问题的经典技巧。