一道比较水的题目。 原型是多重集组合数的问题。。
大意就是n种物品，每种ai个， 问从中取出m个有多少种取法
dp[i+1][j] 是前i中物品取出j个的取法
dp[i+1][j] = dp[i][j] + dp[i+1][j-1] - dp[i][j-a[i]-1]] 后面的减号是因为在取j-1个的时候可能已经用掉了ai个。。这时候要去掉这种情况才能继续添加ai
注意用longlong 和避免 负数。
题目：
代码：
1 #include <iostream> 2 using namespace std; 3 #define MOD 1000007 4 #define MAX 101 5 #define LL long long 6 int n,m; 7 LL a[MAX]; 8 LL dp[MAX][MAX]; 9 int main() 10 { 11 cin>>n>>m; 12 13 for(int i=0;i<n;i++) 14 { 15 cin>>a[i]; 16 } 17 for(int i=0;i<=n;i++) 18 { 19 dp[i][0] =1; 20 } 21 22 for(int i=0;i<n;i++) 23 { 24 for(int j=1;j<=m;j++) 25 { 26 if(j-1-a[i]>=0) 27 dp[i+1][j] = dp[i+1][j-1] +dp[i][j] -dp[i][j-1-a[i]]; 28 else 29 dp[i+1][j] = dp[i+1][j-1]+dp[i][j]; 30 dp[i+1][j]=(dp[i+1][j]+MOD)%MOD; 31 } 32 } 33 cout<<(dp[n][m]+MOD)%MOD<<endl; 34 return 0; 35 }