题目链接：https://jzoj.net/senior/#main/show/4786 有 n n n种珠子，要求把这些珠子放在一条直线上，且第 i i i种珠子的最后一个的位置 l a s t i last_i lasti满足 l a s t 1 < l a s t 2 < . . . < l a s t n last_1<last_2<...<last_n last1<last2<...<lastn。求满足要求的方案数。
假设我们求完了前 i i i种珠子按要求摆放的方案数，现在要求第 i + 1 i+1 i+1种珠子的方案数。 设 s u m [ i − 1 ] sum[i-1] sum[i−1]表示前 i − 1 i-1 i−1种珠子的总个数，那么第 i i i种珠子的最后一个就应该放在这 s u m [ i − 1 ] sum[i-1] sum[i−1]个珠子后面，剩余的第 i i i种珠子就应该全部放在这颗珠子的前面。
那么如果总共有 a [ i ] a[i] a[i]个第 i i i种珠子，那么剩余的 a [ i ] − 1 a[i]-1 a[i]−1个珠子都要放在上图蓝色珠子的前面。 而放置的空隙总共是有 s u m [ i − 1 ] + 1 sum[i-1]+1 sum[i−1]+1个的（如下图）
A : A: A: 所以放置方案数是 s u m [ i − 1 ] a [ i ] − 1 sum[i-1]^{a[i]-1} sum[i−1]a[i]−1吗？
不是！ 如果我们有 3 3 3个珠子要放，那么就有可能为以下6种情况（ x − y x-y x−y表示第 x x x颗珠子放第 y y y个位置）
1 − 2 , 2 − 5 , 3 − 6 1-2,2-5,3-6 1−2,2−5,3−6 1 − 2 , 2 − 6 , 3 − 5 1-2,2-6,3-5 1−2,2−6,3−5 1 − 5 , 2 − 2 , 3 − 6 1-5,2-2,3-6 1−5,2−2,3−6 . . . . . . ...... ......而这6种情况实质上是一模一样的，这样就会计算重复的。
A : A: A: 所以放置方案数是 s u m [ i − 1 ] a [ i ] − 1 s u m [ i − 1 ] ! \frac{sum[i-1]^{a[i]-1}}{sum[i-1]!} sum[i−1]!sum[i−1]a[i]−1吗？
依然不是。 虽然有一些排列方案会重复 s u m [ i − 1 ] ! sum[i-1]! sum[i−1]!次，但是也有一些方案重复的次数小于 s u m [ i − 1 ] ! sum[i-1]! sum[i−1]!，同时也有一些方案是不会重复的。 例如 1 − 3 , 2 − 3 , 3 − 3 1-3,2-3,3-3 1−3,2−3,3−3这种情况它就只会算一次。 很显然，这种计算是因为选择的位置本身的重复而导致的。例如上例选择的位置3就重复了，但是3,3,3的全排列只有3,3,3一种情况，所以就只会出现一次。 而 1 − 4 , 2 − 1 , 3 − 1 1-4,2-1,3-1 1−4,2−1,3−1就会出现3次，因为4,1,1的全排列有 ( 1 , 1 , 4 ) , ( 1 , 4 , 1 ) , ( 4 , 1 , 1 ) (1,1,4),(1,4,1),(4,1,1) (1,1,4),(1,4,1),(4,1,1)三种。
所以放置 a [ i ] − 1 a[i]-1 a[i]−1个珠子的方案数还需要分类讨论一下。
如果 a [ i ] − 1 a[i]-1 a[i]−1个珠子位置各不相同，那么就相当于从 s u m [ i − 1 ] sum[i-1] sum[i−1]个空位种选择 a [ i ] − 1 a[i]-1 a[i]−1个的方案数，所以就是 C s u m [ i − 1 ] a [ i ] − 1 C^{a[i]-1}_{sum[i-1]} Csum[i−1]a[i]−1如果 a [ i ] − 1 a[i]-1 a[i]−1个珠子位置有1个相同，那么就相当于从 s u m [ i − 1 ] sum[i-1] sum[i−1]个空位种选择 a [ i ] − 2 a[i]-2 a[i]−2个的方案数，但是这个相同的位置可能是选择的位置中的任意一个，所以就是 C s u m [ i − 1 ] a [ i ] − 2 × C a [ i ] − 2 1 C^{a[i]-2}_{sum[i-1]}\times C^{1}_{a[i]-2} Csum[i−1]a[i]−2×Ca[i]−21$**以此类推。所以第 i i i中珠子的方案数是 ∑ j = 2 a [ i ] − 1 C ( s u m [ i − 1 ] + 1 , j ) × C ( a [ i ] − 2 , j − 1 ) \sum^{a[i]-1}_{j=2} C(sum[i-1]+1,j)\times C(a[i]-2,j-1) j=2∑a[i]−1C(sum[i−1]+1,j)×C(a[i]−2,j−1)
最终答案就是 ∑ i = 2 n ∑ j = 2 a [ i ] − 1 C ( s u m [ i − 1 ] + 1 , j ) × C ( a [ i ] − 2 , j − 1 ) \sum^{n}_{i=2}\sum^{a[i]-1}_{j=2} C(sum[i-1]+1,j)\times C(a[i]-2,j-1) i=2∑nj=2∑a[i]−1C(sum[i−1]+1,j)×C(a[i]−2,j−1)
均摊思想得时间复杂度为 O ( ∑ i = 1 n a [ i ] ) O(\sum^{n}_{i=1} a[i]) O(∑i=1na[i])（即 O ( s u m [ n ] ) O(sum[n]) O(sum[n])）,由于题目中说了所有珠子数量和小于 5 × 1 0 5 5\times 10^5 5×105，所以是可以过去的。
吐槽：这道题卡了我1.5h woc \color{white}\texttt{吐槽：这道题卡了我1.5h woc} 吐槽：这道题卡了我1.5h woc
