多重集组合数问题题目:有n种物品,第i种物品有a个.不同种类的物品可以互相区分,但相同种类的无法区分.从这些物品中取出m个,有多少种取法?求出数模M的余数.例如:有n=3种物品,每种a={1,

Question

多重集组合数问题
题目: 有n种物品, 第i种物品有a个. 不同种类的物品可以互相区分, 但相同种类的无法区分.
从这些物品中取出m个, 有多少种取法? 求出数模M的余数.
例如: 有n=3种物品, 每种a={1,2,3}个, 取出m=3个, 取法result=6(0+0+3, 0+1+2, 0+2+1, 1+0+2, 1+1+1, 1+2+0).
使用动态规划(DP).
前i+1种物品取出j个 = 前i+1种物品取出j-1个 + 前i种物品取出j个 - 前i种物品中取出j-1-a个.
因为取出j-1-a个, 最后需要j-1个, 则a需要全部取出, 前两个相重复, 则必然全部取出.
递推公式: dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-1-a]
时间复杂度O(nm).
------------
我看不明白递推式，谁能解释下

Answer 1

关键之处在于：公式C(k+n-1,k)是方程
x1+x2+x3+.+xn=k
的非负整数解,即诸xi>=0,注意,有等号
设 x1 为 a 出现的次数,x2 为 b 出现的次数,...,x4 为 d 出现的次数,得到方程
x1 + x2 + x3 + x4 = 10
4 种元素的每一种都至少出现一次的 ,xi>0
而公式里要求xi>=0,
有xi>0,得xi-1>=0,
所以令 :yi=xi-1
同样可以解释“ 引入新变量 y1 = x1 - 3,y2 = x2 - 1,y3 = x3,y4 = x4 - 5
y1 + y2 + y3 + y4 = 11 ”