题解：CF2066D1 Club of Young Aircraft Builders (easy version)

· · 题解

组合意义

首先，顶层必须扔 c 只飞机。

对于下面的每一层，需要决定它们看到的前 c 只飞机分别是自己丢出去的还是楼上丢下来的。

而楼下总共丢出 m-c 只飞机。

故答案为 \large \binom{(n-1) c}{m-c}。

dp

记 dp_{i,j} 为 n=i,m=j 时原问题的答案，有：

dp_{i,j}=\sum_{0 \leq k \leq c} \binom{c}{k} dp_{i-1,j-k}

时间复杂度为 \mathcal{O}(n \cdot c \cdot m)。