Ant Counting

前言

不知道为什么有这么多英文题。。。

题目

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

大意

有T只蚂蚁，分别属于A个家族。要你把它们分成元素个数为S~B的集合，问有多少种分法。

分析

想用容斥原理，看了一下规模，决定算了。
那么就用我们的 好伙伴 DP吧
明显的，这是一道多重背包问题
所以就来想一想思路吧

很容易想到的思路是定义dp[i][j]，表示第i家的蚂蚁出j只能得到的方案数

还好，这世上终归是有大佬的
大佬是这么想的：

dp[i-1][j]不就是不选这个家族嘛
dp[i][j-1]不就是再选一个嘛
dp[i-1][j-N[i-1]-1]不就是重复的个数嘛

然后就开始码吧

代码

#include<cstdio>
#define MAXN 1000
#define MAXM 100
#define MOD 1000000
int Num[MAXN+5],dp[MAXN+5][MAXN*MAXM+5];
int main(){
    int T,A,S,B,Ans=0;
    scanf("%d %d %d %d",&T,&A,&S,&B);
    for(int i=1;i<=A;i++){
        int x;
        scanf("%d",&x);
        Num[x-1]++;
    }
    for(int i=0;i<=T;i++)
        dp[i][0]=1;
    for(int i=1;i<=T;i++)
        for(int j=1;j<=B;j++)
            if(j-Num[i-1]-1>=0)
                dp[i][j]=(dp[i-1][j]+dp[i][j-1]-dp[i-1][j-Num[i-1]-1]+MOD)%MOD;
            else
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;
    for(int i=S;i<=B;i++){
        Ans+=dp[T][i];
        Ans%=MOD;
    }
    printf("%d\n",Ans);
    return 0;
}