P6672 [清华集训2016] 你的生命已如风中残烛（组合数学）
木xx木大
·
·
题解
P6672 [清华集训2016] 你的生命已如风中残烛
Raney 引理
若 A=\{A_i,i=1,2,...,m\} 是任意一个和为 1 的整数序列，则其所有循环位移中有且仅有一个满足所有前缀和都是正数。
证明：每次必须取最后一个最小值的后一位作为起点，使得其他最小值位置跨过序列结尾，前缀和为 1；否则如果有两个相等最小值而取前一个作为起点，第二个最小值位置前缀和是 0。
据此，假设 m 个数之和为 1，那么满足所有前缀和为正数的排列的数量即其圆排列的数量 (m-1)!，因为每个圆排列（环）都只有一个链满足条件。
问题转化
设 a_i 表示每张牌能提供的摸牌次数，那么普通牌 a_i=-1，特殊牌 a_i=w_i-1。则原题变为：给定 m 个数 a_1,a_2,\dots,a_m，求有多少种排列，使得 \forall i,\sum_{j=1}^i a_j\ge 0 且 \sum_{j=1}^m a_j=0
发现这个问题和 Raney 引理非常相似，类似推导卡特兰数时的方法，我们在序列末尾放一个 -1，问题转化为了求前 m 个前缀和大于等于 0 的排列数。这样合法的方案数即为 m!。直接套用 Raney 引理的证明，每个圆排列只有一种满足条件的情况，即每次必须取最后一个最小值的后一位作为起点。
还有一种解释：前缀大于等于0即后缀小于等于0，把原序列中的值全部取反再逆序，然后直接套推导卡特兰数的方法。
还要除去在末尾添加的 -1 的影响。所有方案中，被放在最后一个位置的 -1，可能是 m+1-n 个中的任意一个，且它们是等价的，所以最后答案还要除以 m+1-n。最终 ans=\dfrac{m!}{m+1-n}