题意也比较简单了。
大概是：
给出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
#include
#include
#include
#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;
}