POJ3046ANT_COUNTING

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <set>
#include <stack>
#include <map>

using namespace std;
const int MAX_A = 100002;
const int MAX_T = 1002;
int T, A, S, B;
int a[MAX_T];
int dp[2][MAX_A];
const int MOD = 1e6;

int main(void)
{
    cin>>T>>A>>S>>B;
    //输入组别的数量、蚂蚁的数量、起始的地方、终止的地方
    int x;
    for(int i = 0; i < A; i++){
        scanf("%d", &x);     //组的编号其实是 0 到 T - 1
        a[x-1]++;
    }
    //UNIT OPTION
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i <= a[0]; i++)  dp[0][i] = 1;
    // END OF INIT
    for(int i = 1; i < T; i++){
        if(i & 1){
            memset(dp[1], 0, sizeof(dp[1]));
            for(int j = 0; j <= B; j++){
                for(int k = 0; k <= a[i] && k <= j; k++){
                    dp[1][j] += dp[0][j-k], dp[1][j] %= MOD;
                }
            }
        }
        else{
            memset(dp[0], 0, sizeof(dp[0]));
            for(int j = 0; j <= B; j++){
                for(int k = 0; k <= a[i] && k <= j; k++){
                    dp[0][j] += dp[1][j-k], dp[0][j] %= MOD;
                }
            }
        }
    }
    int res = 0;
  //  printf("SHOW THE TMEP\n");
    if((T - 1) & 1){
     //   for(int i = 0; i < S; i++)  printf(" i  %d : %d\n", i, dp[1][i]);
        for(int i = S; i <= B; i++){
     //       printf(" i  %d : %d\n", i, dp[1][i]);
            res += dp[1][i];
            res %= MOD;
        }
    }
    else{
      //  for(int i = 0; i < S; i++)  printf(" i  %d : %d\n", i, dp[0][i]);
        for(int i = S; i <= B; i++){
     //       printf(" i  %d : %d\n", i, dp[0][i]);
            res += dp[0][i];
            res %= MOD;
        }
    }
 //   printf("THE RESULT :   ");
    printf("%d\n", res);
    return 0;
}