与昨天一道类似的多重集组合数问题
每个家族有n个蚂蚁,一共T个家族, 问从S到B能有多少组合可能
题目:
Description
Input
Output
Sample Input
3 5 2 3 1 2 2 1 3
Sample Output
10
Hint
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 5 using namespace std; 6 #define MOD 1000000 7 8 int T,A,S,B; 9 int num[1000+10]; 10 11 int dp[1000+10][100000+10]; 12 int main() 13 { 14 cin>>T>>A>>S>>B; 15 for(int i=0;i<A;i++) 16 { 17 int t; 18 cin>>t; 19 num[t] ++; 20 } 21 for(int i=0;i<=T;i++) 22 dp[i][0] =1; 23 24 for(int i=0;i<T;i++) 25 { 26 for(int j=1;j<=B;j++) 27 { 28 if( j-num[i+1]-1 >=0) 29 { 30 dp[ i+1 ][j] =(dp[i+1][j-1]+dp[i][j]- dp[i][j-1-num[i+1]] +MOD)%MOD; 31 } 32 else 33 { 34 dp[i+1][j] = (dp[i+1][j-1] +dp[i][j]+MOD)%MOD; 35 } 36 } 37 } 38 int ans =0 ; 39 for(int i = S;i<=B;i++) 40 { 41 //cout<<dp[T][i]<<endl; 42 ans+=dp[T][i]; 43 ans%=MOD; 44 } 45 cout<<(ans+MOD)%MOD<<endl; 46 return 0; 47 }
原文:http://www.cnblogs.com/doubleshik/p/3538391.html