1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<cstdio>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 1e6;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 1e5+111;
int dp[1050][N];
int num[1050];
int main(){
int t,n,l,r;
scanf("%d %d %d %d",&t,&n,&l,&r);
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
num[x]++;
}
for(int i=0;i<=t;i++)dp[i][0]=1;
ll ans = 0;
for(int i=1;i<=t;i++){
for(int j=1;j<=n;j++){
if(j-1-num[i]>=0)
dp[i][j]=(dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1-num[i]]+mod)%mod;
else dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
}
}
for(int i=l;i<=r;i++)ans=(ans+dp[t][i])%mod;
printf("%lld\n",ans);
}
|