题意也比较简单了。
大概是：
给出T种数字。每种各有N[i]个
然后用这些数字构成一些序列， 问x长度到y长度的序列有多少种
那么就是DP了
dp[i][j] 表示前i种数字构成长度为j的序列有多少种
然后
dp[i][j] = sigma(dp[i - 1][j - k]) k的范围是0~N[i]
注意到这里的sigma(dp[i - 1][j - k]) 可以用部分和算一下
然后因为总共的数字个数可能有10W个
有1000种数组。
所以需要开滚动数组来搞
复杂度的话 是 O(sigma(num[i] * (T + 1 - i)))
最坏是1亿
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define MAXN 111111
#define INF 1000000007
using namespace std;
int dp[2][MAXN], num[1111];
int sum[MAXN], up[1111];
int main()
{int T, S, A, B, x;scanf("%d%d%d%d", &T, &A, &S, &B);for(int i = 1; i <= A; i++){scanf("%d", &x);num[x]++;}for(int i = 1; i <= T; i++)up[i] = up[i - 1] + num[i];dp[0][0] = 1;int *pre = dp[0], *nxt = dp[1];for(int i = 1; i <= T; i++){sum[0] = pre[0];for(int j = 1; j <= up[i]; j++)sum[j] = (sum[j - 1] + pre[j]) % 1000000;for(int j = 0; j <= up[i]; j++){int tmp = max(0, j - num[i]);nxt[j] = (tmp == 0 ? sum[j] : (sum[j] - sum[tmp - 1] + 1000000));nxt[j] %= 1000000;}swap(nxt, pre);}int ans = 0;for(int i = S; i <= B; i++)ans = (ans + pre[i]) % 1000000;printf("%d\n", ans);return 0;
}