CF 2066D2 Club of Young Aircraft Builders (hard version)

rizynvu · 2025-07-10 18:53:38 · 题解

cnblogs。

说一个看起来暴力得多的做法！

考虑对于 i 只有在 i\sim n 层飞出的纸飞机数量 < c 时才能飞一个纸飞机。
那么如果知道了当前每个楼层飞出的纸飞机数，考虑找到最小的 i 满足 i\sim n 层飞出的纸飞机数 < c，此时就相当于是只有 i\sim n 层可以飞出纸飞机。

发现这就天然的分出了阶段：1\sim n 层都可以飞纸飞机，2\sim n 层可以飞纸飞机，一直到最后第 n 层的纸飞机也飞完结束。

于是考虑记 f_{i, j, k} 表示考虑了前 i 个纸飞机，此时 j\sim n 层还可以飞纸飞机，且 j\sim n 层一共飞了 k 个纸飞机的方案数。
为了方便转移，考虑延后计算贡献，就是此时不去区分 j\sim n 层具体的分法，到阶段结束时再考虑计算贡献。
具体来说对于转移，考虑分为两种：

• 具体来说，记 $1\sim i$ 中 $a_{i'} > j$ 的数量为 $c_1$，$a_{i'} = j$ 的数量为 $c_2$，那么还有 $k - c_1 - c_2$ 个纸飞机没有确定，枚举 $x\in [c_2. k - c_1]$ 表示 $j$ 层的纸飞机数，转移为 $\binom{k - c_1 - c_2}{x - c_2}f_{i, j, k}\to f_{i + 1, j + 1, k - x}$。 需要注意可能 $j$ 这一层飞出去了 $0$ 个纸飞机，所以 $j + 1\sim n$ 的纸飞机数仍为 $k$，要继续删掉 $j + 1$ 层。

还需要考虑的是，如果遇到了 a_i > 0，说明此时 a_i 一定能够飞纸飞机，所以 j 的合法范围应为 [1, a_i]。