计数
P6672 [清华集训2016] 你的生命已如风中残烛
题意
给你一个长度为 \(m\) 的序列 \(W\) ，其中 \(n\) 个 \(w_i\geq 1\) ，\(\Sigma w_i[w_i\geq 1] =m\) ，拿到一个 \(w_i\) 可以往后拿 \(w_i\) 个数，求在 \(m!\) 中有多少种排列可以拿到第 \(m+1\) 的数。
简化
我们将每个数减一，原问题便转化为给定序列 \(W\) ，其中 \(n\) 个数非负，其余 \(m-n\) 个数均为 \(-1\) ，\(\Sigma w_i=0\) 要求有多少序列满足该序列所有前缀和均非负。
思路
有一个东西，叫作 Raney 引理。
Raney 引理是这么说的：
若存在一个序列 \(A\) ，其中 \(\sum a_i = 1\) ，则其循环移位有且只有一个满足所有的前缀和均为正数。
关于证明：《具体数学》7.5章（机房这本是P301-P302）有关于此的几何方法证明，读者自证不难因此在此口胡一下。
考虑一个序列 \(a_1,a_2,a_3,...,a_m\) ，设 \(sum_i\) 表示前 \(i\) 位的前缀和。由于要求所有 \(sum_i>0\) ，则对于一个合法的
考虑在 \(m+1\) 的位置放一个 \(-1\) ，则原问题又变成求前 \(m\) 的前缀和为非负的排列数，\(\sum _{i=1}^{m+1} w_i=0\) 。
AGC024E Sequence Growing Hard
求有多少个序列组 \(A_0,A_1,⋯ ,A_n\) 满足：
- \(A_i\) 的长度为 \(i\)，且其中元素均为属于 \([1,K]\) 的整数。
- \(A_{i−1}\) 为 \(A_i\) 的子序列。
- \(A_i\) 的字典序大于 \(A_{i-1}\).
思考一下，不难发现
ARC125F Tree Degree Subset Sum
给定一棵 \(N\) 个点的树，第 \(i\) 条边连接了 \(A_i\) 和 \(B_i\) 两个节点。求出满足以下条件的数对 \((x,y)\) 的个数：
- \(0≤x≤N\) ；
- 存在一种从树上选出恰好 \(x\) 个节点的方案，使得节点的度数和为 \(y\)。
首先，比较显然的，树的具体形态并不重要。
那么这道题的限制形式化来讲，就是求有多少个点对，\((x,y)\) ，设取出的点度数为 \(du\) ，满足 \(\sum _{i=1}^x du_i =y\) ，且 \(\sum _{i=1}^n d_i =2n-2\) 。
特别鸣谢：
-
Diwanul 听我口胡 Raney 定理且帮助我思考，
-
某前数学组学长yzl听我口胡 P6672 ，
-
gyq 借我 cy 的《具体数学》，
-
ZJK 的课件（虽然有点难懂），
-
以及特别感谢各位在我分享过程中没有一怒之下D死我这个菜鸡stOOOOOOOO。