题解：P14636 [NOIP2025] 清仓甩卖 / sale

· · 题解

补一个组合意义手撕范德蒙德卷积。

设被卡住的 2 的位置是 i，卡住 i 的 1 的位置是 j，j 后面的第一个 1 是 k。

那么 i 之前的 2 和 1 必须都选。

所以 i 之前的每一个数至少有 1 的贡献。

所以而 $i,j$ 之间的的每一个数最多有 $1$ 的贡献。 我们分别记把一个 $i$ 之前的数赋值为 $2$ ，$i,j$ 之间把一个数赋值为 $1$ 作为一次选择。 那么从这些选出和为 $m-2$ 的值的方案数其实就是 $\tbinom{j-2}{m-i-1}$。 答案就是 $$ \sum 2^{n-k+1}\times \tbinom{j-2}{m-i-1} $$