Solution

应该这个做法不是很常见吧。

我们设 (f_{i,j}) 表示前面 (i) 个数，选出的数和为 (j) 的贡献之和。因为我们有以下式子：

[sum_{i=a}^{b} inom{i}{a}=inom{b+1}{a+1} ]

所以，我们可以得到转移式：

[f_{i,j}=sum_{k} f_{i-1,k} imes inom{j-k+1}{a_i+1} ]

然后，我们假设设：

[F_i(x)=sum_{j=1}^{infty} inom{j}{a_i+1}x^{j-1} ]

那么，我们就可以看出实际上 (prod_{i=1}^{n} F_i(x)) 就是 (f_{n,1},f_{n,2},...,f_{n,infty}) 的普通型生成函数。

于是，我们只需要求出 (F_i(x)) 的式子就好了。

我们可以得到如下推导：

设 (S=sum_{i=1}^{infty} inom{i}{a}x^{i})

则有：

[S=x^asum_{i=0}^{infty} inom{i+a}{i}x^i ]

[Rightarrow S=x^asum_{i=0}^{infty} inom{-a-1}{i}(-x)^i ]

[Rightarrow S=x^a(1-x)^{-a-1}=x^afrac{1}{(1-x)^{a+1}} ]

所以，我们可以得到：

[F_i(x)=x^{a_i}frac{1}{(1-x)^{a_i+1}} ]

那么，我们设 (s=sum_{i=1}^{n} a_i)，那么我们就可以得到：

[prod_{i=1}^{n} F_i(x)=x^{s}frac{1}{(1-x)^{s+n}} ]

那么这个多项式的第 (i) 项的系数就是 (inom{i+n-1}{n+s-1})。

那么，答案就是：

[sum_{i=0}^{m} inom{i+n-1}{n+s-1} ]

[=inom{n+m}{n+s} ]