Devu有N个盒子,第i个盒子中有AiAi枝花。
同一个盒子内的花颜色相同,不同盒子内的花颜色不同。
Devu要从这些盒子中选出M枝花组成一束,求共有多少种方案。
若两束花每种颜色的花的数量都相同,则认为这两束花是相同的方案。
结果需对109+7109+7取模之后方可输出。
输入格式
第一行包含两个整数N和M。
第二行包含N个空格隔开的整数,表示A1,A2,…,ANA1,A2,…,AN。
输出格式
输出一个整数,表示方案数量对109+7109+7取模后的结果。
数据范围
1≤N≤201≤N≤20,
0≤M≤10140≤M≤1014,
0≤Ai≤10120≤Ai≤1012
输入样例:
3 5
1 3 2
输出样例:
3
题意:让你在n朵花里面选择m朵,其中有些花朵相同,然后求方案数有多少种,不用顺序排列
思路:这里其实就是一个多重集的组合数问题
多重集的排列问题
有k个物品,总共有n个种类,第ni个种类有a[i]个物品,问全排列数是多少
就是 n!/(n1!*n2!*....ni!),道理很简单,全部不相同的全排列数是n!,但是这个其中有重复,所以我们需要去重,所有我们对每个种类求个全排列
然后除就行,其中每个种类的重复又可以和其他种类的重复产生联系,所以是乘法原理,把所有的种类全排列相乘即可
多重集的组合问题
有k个物品,总共有n个种类,第ni个种类有a[i]个物品,然后从中选择m个,问有多少个选择方法
多重集的组合数的弱化版(m=<a[i])
如果是基于这个条件的话,那么我们就可以直接采用隔板法来计算,首先我们选择m个商品,我们条件那么就只有在每个种类选择的个数加起来等于m即可
又因为我们的m不会大于每个种类个数,那么我们就把他分为n组即可,使用n-1个隔板,那么这个的答案就是
C(n+m-1,n-1) 我们把我们的m个商品分个类,分成n份,所有我们还加入了n-1个隔板,所以就是这个答案
多重集的组合数的强化版(m<=n)