多重集是指可以包含重复元素的广义集合。
现在你有一个形如 { a 1 × b 1 , a 2 × b 2 , . . . , a k × b k } \{a_1\times b_1,a_2 \times b_2 , ...,a_k \times b_k\} {a1×b1,a2×b2,...,ak×bk} 的多重集，其中 x × y x\times y x×y 表示这个集合中有 x x x 个 y y y，现在问这个集合有多少种不同的排列方式。
这是一道很基础的组合数学问题。
我们先考虑这些元素有多少种排列方式，显然为： ( ∑ i = 1 k a i ) ! (\sum_{i=1}^k a_i)! (∑i=1kai)!。
但是我们还要去除相同的排列，我们注意到，这里面有 a 1 a_1 a1 个 b 1 b_1 b1，而这些 b 1 b_1 b1 之间交换位置是不会形成新的排列方式的，所以我们要除以 a 1 ! a_1! a1!，也就是这些 b 1 b_1 b1 之间的全排列方案数。
那么最后的答案就是： ( ∑ i = 1 k a i ) a 1 ! a 2 ! . . . a k ! \frac {(\sum_{i=1}^k a_i)} {a_1!a_2!...a_k!} a1!a2!...ak!(∑i=1kai)
现在你有一个形如 S = { a 1 × b 1 , a 2 × b 2 , . . . , a k × b k } S=\{a_1\times b_1,a_2 \times b_2 , ...,a_k \times b_k\} S={a1×b1,a2×b2,...,ak×bk} 的多重集，现在要从中选出 m m m 个数，问有多少种方案。
先考虑 m m m 满足 m ≤ a i ( i ∈ [ 1 , n ] ) m\leq a_i~(i \in [1,n]) m≤ai (i∈[1,n]) 时的情况。
那么此时相当于没有了 a i a_i ai 的限制，我们设 c i c_i ci 表示 b i b_i bi 这个数选 c i c_i ci 个，那么需要满足 ( ∑ i = 1 n c i ) = m (\sum_{i=1}^n c_i)=m (∑i=1nci)=m 且对于任意 i i i，有 c i ≥ 0 c_i\geq 0 ci≥0。
那么现在问题等价于：有 k k k 个不同的盘子，你要将 m m m 个相同的苹果放到这 k k k 个盘子里，问方案数。
那么这就是一个经典的组合数插板法问题了（不会请戳这里），方案数为 C m + k − 1 k − 1 = C m + k − 1 m C_{m+k-1}^{k-1}=C_{m+k-1}^m Cm+k−1k−1=Cm+k−1m。
在此基础上，我们再考虑 m m m 没有特殊性质时的情况。
不妨先忽略 a i a_i ai 的影响，那么根据 Part 1 可以知道，此时的方案数为： C m + k − 1 m C_{m+k-1}^{m} Cm+k−1m
但是我们还要减去不合法的方案，设 f [ i ] f[i] f[i] 表示 b i b_i bi 这个数拿了至少 a i + 1 a_i+1 ai+1 个的方案数。
考虑求 f [ i ] f[i] f[i]： b i b_i bi 至少拿 a i + 1 a_i+1 ai+1 个的方案数，也就是先拿 a i + 1 a_i+1 ai+1 个 b i b_i bi，然后再从剩下的里面拿 m − ( a i + 1 ) m-(a_i+1) m−(ai+1) 个的方案数，也就是 f [ i ] = C m + k − 1 − ( a i + 1 ) m − ( a i + 1 ) = C m + k − 1 − ( a i + 1 ) k − 1 f[i]=C_{m+k-1-(a_i+1)}^{m-(a_i+1)}=C_{m+k-1-(a_i+1)}^{k-1} f[i]=Cm+k−1−(ai+1)m−(ai+1)=Cm+k−1−(ai+1)k−1
那么答案就是： C m + k − 1 m − ∑ i = 1 k f [ i ] C_{m+k-1}^{m}-\sum_{i=1}^k f[i] Cm+k−1m−i=1∑kf[i]
还没完！ f [ i ] f[i] f[i] 之间计算的方案数是有重复的，比如说：对于 b 1 b_1 b1 拿了 a 1 + 1 a_1+1 a1+1 个，同时 b 2 b_2 b2 拿了 a 2 + 1 a_2+1 a2+1 个，这样的不合法方案会被 f [ 1 ] f[1] f[1] 和 f [ 2 ] f[2] f[2] 各计算一次，所以我们还需要加上 f [ i ] ∩ f [ j ] ( i ∈ [ 1 , n ] , j ∈ [ 1 , n ] , i ≠ j ) f[i] \cap f[j]~(i\in[1,n],j\in[1,n],i \neq j) f[i]∩f[j] (i∈[1,n],j∈[1,n],i=j)。
f [ i ] ∩ f [ j ] f[i] \cap f[j] f[i]∩f[j] 的计算方法类似上面，即 C m + k − 1 − ( a i + 1 ) − ( a j + 1 ) k + 1 C_{m+k-1-(a_i+1)-(a_j+1)}^{k+1} Cm+k−1−(ai+1)−(aj+1)k+1。
那么这样反复容斥下去，就能得到最终的答案： a n s = C m + k − 1 m − ∑ i = 1 k C m + k − 1 − ( a i + 1 ) k − 1 + ∑ i ∈ [ 1 , n ] , j ∈ [ 1 , n ] , i ≠ j C m + k − 1 − ( a i + 1 ) − ( a j + 1 ) k − 1 + . . . + ( − 1 ) k ∑ p 1 ∈ [ 1 , n ] , p 2 ∈ [ 1 , n ] , ⋯ , p 1 ≠ p 2 , p 1 ≠ p 3 , ⋯ C m + k − 1 − ∑ j = 1 k ( p j + 1 ) k − 1 \begin{aligned} ans=&C_{m+k-1}^m-\sum_{i=1}^k C_{m+k-1-(a_i+1)}^{k-1} + \sum_{i\in[1,n],j\in[1,n],i \neq j} C_{m+k-1-(a_i+1)-(a_j+1)}^{k-1}\\ &+...+(-1)^k \sum_{p_1\in[1,n],p_2\in[1,n],\cdots,p1\neq p_2,p_1 \neq p_3 , \cdots} C_{m+k-1-\sum_{j=1}^k (p_j+1)}^{k-1} \end{aligned} ans=Cm+k−1m−i=1∑kCm+k−1−(ai+1)k−1+i∈[1,n],j∈[1,n],i=j∑Cm+k−1−(ai+1)−(aj+1)k−1+...+(−1)kp1∈[1,n],p2∈[1,n],⋯,p1=p2,p1=p3,⋯∑Cm+k−1−∑j=1k(pj+1)k−1
Devu and Flowers 题解
