题解：P6672 [清华集训2016] 你的生命已如风中残烛

· · 题解

题目链接：[清华集训2016] 你的生命已如风中残烛

考虑满足条件的序列长什么样：

若我们摸到了大小为 x 的牌，则之后我们可以摸 x-1 次大小为 0 的牌。

不难发现，对于一个形如 \forall i\in\left[1,m\right],\sum\limits_{j=1}^i w_j \ge i 的序列 w，其满足条件。

将 w 中的每一个元素 -1，则 \forall i\in\left[1,m\right],\sum\limits_{j=1}^i w_j \ge 0 满足条件。

考虑 \text{Raney} 引理：

如果序列 x_1,x_2,\cdots,x_n 满足 \sum\limits_{i=1}^n x_i=1，则其所有循环位移中有且仅有一个满足前缀和均为正数。

发现这个引理和我们需要的东西很像。

在我们所需要的序列前添上一个 1，就和 \text{Raney} 引理中的序列一样了。

但不难发现，加上一个 1 后计算出来的圆排列数量并不是答案，因为原本的序列经过圆排列的打乱，那个 1 最后不一定出现在序列的最前端。

接下来就是本题最妙的地方。

既然加 1 不行，那我们在最后加上 -1 后对整个序列取反，序列的和还是 1。问题就转化为了求 \forall i\in\left[1,m+1\right],\sum\limits_{j=i}^{m+1} w_j >0 的序列数量。依旧可以用 \text{Raney} 引理解决。这个时候依旧会重复计算，但计算出来的每个序列的最后一个元素都一定是 1（只有 1 一个正数，又要满足后缀和为正数）。一共有 \left(m-n+1\right) 个 1，故答案为 \frac{m!}{m-n+1}。