POJ.3046 Ant Counting

1.Problem
http://poj.org/problem?id=3046

2.Idea
dp[i][j]: The number of possible ways of making j by the first i families. The following relation is true.
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] +...+ dp[i-1][m], {m = minimum of i's number and j}, dp[i-1][j-f] expressing the set only includes f number of i.

3.Source

 #define MAX_N 1000  
 #define MAX_M 100000  
 #define MOD 1000000  
 int n, m, A, S;  
 int a[MAX_N];  
 int dp[MAX_N + 5][MAX_M + 5];  
 int main()  
 {  
      cin >> n >> A >> S >> m;  
      for (int i = 0; i < A; i++) {  
           int t;  
           cin >> t;  
           a[t]++;  
      }  
      dp[0][0] = 1;  
      int total = 0;  
      for (int i = 1; i <= n; i++) {  
           total += a[i];  
           for (int k = 0; k <= a[i]; k++) {  
                for (int j = total; j >= k; j--) {  
                     dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;  
                }  
           }  
      }  
      int ans = 0;  
      for (int i = S; i <= m; i++) {  
           ans = (ans + dp[n][i]) % MOD;  
      }  
      cout << ans << endl;  
      return 0;  
 }