#include <iostream>
using namespace std;
 
#define MOD 1000
int family[1000 + 16];               // 每个家庭有多少只蚂蚁
int dp[1000 + 16][10000 + 16];     // 使用前i个家族可以配出来“元素个数为j”的集合的个数
 
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int T, A, S, B;
    cin >> T >> A >> S >> B;
    for (int i = 0; i < A; ++i)
    {
        int index;
        cin >> index;
        ++family[index];
    }
    dp[0][0] = 1;
    int total = family[0];                   // 前i个家族一共有多少只蚂蚁
    for (int i = 1; i <= T; ++i)
    {
        total += family[i];
        for (int k = 0; k <= family[i]; ++k)
        {
            for (int j = total; j >= k; --j)
            {
                dp[i][j] = (dp[i][j] 
                            + dp[i - 1][j - k] // 前i-1个家族配成j-k的集合们每一个集合都放入k只
                                                // 家族i的蚂蚁构成新集合，它们必然各不相同
                            ) % MOD;
            }
        }
    }
    int result = 0;
    for (int i = S; i <= B; ++i)
    {
        result = (result + dp[T][i]) % MOD;
    }
    cout << result << endl;
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////
由于dp数组每次都是i和i-1，所以可以滚动重复利用：

#include <iostream>
using namespace std;
 
#define MOD 1000000
int family[1000 + 16];               // 第i个家庭有多少只蚂蚁
int dp[2][100000 + 16];              // 使用前i个家族可以配出来“元素个数为j”的集合的个数
 
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int T, A, S, B;
    cin >> T >> A >> S >> B;
    for (int i = 0; i < A; ++i)
    {
        int index;
        cin >> index;
        ++family[index];
    }
    dp[0][0] = 1;
    int total = 0;                              
    for (int i = 1; i <= T; ++i)
    {
        total += family[i];                       // 前i个家族一共有多少只蚂蚁
        int cur = i & 0x1;
        int pre = (i - 1) & 0x1;
        memset(dp[cur], 0, sizeof(dp[cur]));
        for (int k = 0; k <= family[i]; ++k)
        {
            for (int j = total; j >= k; --j)
            {
                dp[cur][j] = (dp[cur][j] 
                            + dp[pre][j - k] // 前i-1个家族配成j-k的集合们每一个集合都放入k只
                                                // 家族i的蚂蚁构成新集合，它们必然各不相同
                            ) % MOD;
            }
        }
    }
    int result = 0;
    int cur = T & 0x1;
    for (int i = S; i <= B; ++i)
    {
        result = (result + dp[cur][i]) % MOD;
    }
    cout << result << endl;
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////