stonechina0616

Description

Bessie was poking around the ant hill one day watching the ants march to and fro while gathering food. She realized that many of the ants were siblings, indistinguishable from one another. She also realized the sometimes only one ant would go for food, sometimes a few, and sometimes all of them. This made for a large number of different sets of ants! 

Being a bit mathematical, Bessie started wondering. Bessie noted that the hive has T (1 <= T <= 1,000) families of ants which she labeled 1..T (A ants altogether). Each family had some number Ni (1 <= Ni <= 100) of ants. 

How many groups of sizes S, S+1, ..., B (1 <= S <= B <= A) can be formed? 

While observing one group, the set of three ant families was seen as {1, 1, 2, 2, 3}, though rarely in that order. The possible sets of marching ants were: 

3 sets with 1 ant: {1} {2} {3} 
5 sets with 2 ants: {1,1} {1,2} {1,3} {2,2} {2,3} 
5 sets with 3 ants: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3} 
3 sets with 4 ants: {1,2,2,3} {1,1,2,2} {1,1,2,3} 
1 set with 5 ants: {1,1,2,2,3} 

Your job is to count the number of possible sets of ants given the data above. 

Input

* Line 1: 4 space-separated integers: T, A, S, and B 

* Lines 2..A+1: Each line contains a single integer that is an ant type present in the hive

Output

* Line 1: The number of sets of size S..B (inclusive) that can be created. A set like {1,2} is the same as the set {2,1} and should not be double-counted. Print only the LAST SIX DIGITS of this number, with no leading zeroes or spaces.

Sample Input

3 5 2 3

1 

2 

2 

1 

3

Sample Output

10

Hint

INPUT DETAILS: 

Three types of ants (1..3); 5 ants altogether. How many sets of size 2 or size 3 can be made? 


OUTPUT DETAILS: 

5 sets of ants with two members; 5 more sets of ants with three members

题目大意：

一共n种蚂蚁，从其中选出s到b个不同的蚂蚁，不要求选到所以的种类。

即求多重集组合数

DP + 多重集组合数

显然这是一道数学题，计算组合数，这个组合数叫做多重集组合数，它的主要特征：无序，不要求取到全部集合

计算组合数都可以通过DP来计算， 

dp[i][j]表示在前i种物品中取出j个的方案数，可以从前i-1个集合中取出j-k个，再从i中取走k个，那么：

dp[i][j]=Σdp[i-1][j-k]  ( 0<=k<=min(a[i],j) ) 

这一枚举的时间复杂度为O(n*m^2)

优化：dp[i][j]在转移时需要枚举k，然而在前一次(dp[i][j-1])转移时k已经枚举到了k-1，那么可以利用前缀的思想，将方程优化为：

dp[i][j]=dp[i-1][j]+dp[i][j-1]

这一枚举的时间复杂度为O(n*m) 

讨论a[i]与j的关系(a[i]为到目前第i个集中元素的总个数):

1.a[i]<j即min(a[i],j)=a[i]

则有:Σdp[i-1][j-k](0<=k<=min(a[i],j))=Σdp[i-1][j-1-k](0<=k<=min(a[i],j-1))+dp[i-1][j]-dp[i][j-1-a[i]](重点).

即:dp[i][j]=dp[i-1][j]+dp[i][j-1]+dp[i-1][j-1-a[i]]

2.a[i]>=j即min(a[i],j)=j

则有:Σdp[i-1][j-k](0<=k<=min(a[i],j))=Σdp[i-1][(j-1)-k](0<=k<=min(a[i],j-1))+dp[i-1][j].

即:dp[i][j]=dp[i-1][j]+dp[i][j-1]

代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#define rep(q,p) for (int q=1;q<=p;q++)

using namespace std;

const int maxn=1005,md=1e6;

int dp[maxn][maxn*100],a[maxn];

int m,n,l,r,x,ans,tot;

int main()

{

    freopen("in.txt","r",stdin);

    scanf("%d%d%d%d",&m,&n,&l,&r);

    rep(i,n) scanf("%d",&x),a[x]++;

    rep(i,m)

    {

        dp[i][0]=1;

        tot+=a[i];

        rep(j,tot)

        {

            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%md;

            if (j>=a[i])

                dp[i][j]=(dp[i][j]-dp[i-1][j-a[i]-1]+md)%md;

        }

    }

    for (int i=l;i<=r;i++) ans+=dp[m][i],ans%=md;

    printf("%d\n",ans);

    return 0;

}