题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2023
题意：
有n个家族，共m只蚂蚁(n <= 1000, m <= 100000)。
每个家族有cnt[i]只蚂蚁，并且同一家族中的蚂蚁无差别。
从窝里爬出来x只蚂蚁的方案数为f(x)。
给定a,b，让你求 ∑ f(a to b) MOD 1000000。
题解：
表示状态：
dp[i][j] = combinations
i：第i个家族已经考虑过了
j：目前出来了j只蚂蚁
找出答案：
ans = ∑ dp[n][a to b]
如何转移：
dp[i][j] = ∑ dp[i-1][j-k] (0 <= k <= cnt[i], j-k >= 0)
即：dp[i][j] = ∑ dp[i-1][max(0,j-cnt[i]) to j];
边界条件：
dp[0][0] = 1
others = 0
优化：
（1）裸dp时间复杂度为O(n * m^2) = 10^13，绝对炸了。。。
所以前缀和优化：求 ∑ dp[i-1][max(0,j-cnt[i]) to j]。
（2）裸dp空间复杂度为 n*m(Byte) = 95 MB > 64 MB，又炸了咋办。。。
滚动数组。因为dp[i][j]只会用到dp[i-1][...]。
AC Code:
// state expression:
// dp[i][j] = combinations
// i: considering ith group
// j: j ants have been outside
//
// find the answer:
// sigma dp[n][a to b]
//
// transferring:
// dp[i][j] = sigma dp[i-1][j-k] (0 <= k <= cnt[i], j-k >= 0)
//
// boundary:
// dp[0][0] = 1
// others = 0
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1005
#define MAX_M 100005
#define MOD 1000000 using namespace std; int n,m,a,b;
int ans=;
int cnt[MAX_N];
int dp[][MAX_M];
int sum[][MAX_M]; void read()
{
cin>>n>>m>>a>>b;
memset(cnt,,sizeof(cnt));
int temp;
for(int i=;i<m;i++)
{
cin>>temp;
cnt[temp]++;
}
} int cal_mod(int x)
{
return (x%MOD+MOD)%MOD;
} int cal_sum(int k,int x,int y)
{
if(x==) return cal_mod(sum[k&][y]);
return cal_mod(sum[k&][y]-sum[k&][x-]);
} void update_sum(int k,int x)
{
if(x==) sum[k&][x]=cal_mod(dp[k&][x]);
else sum[k&][x]=cal_mod(sum[k&][x-]+dp[k&][x]);
} void solve()
{
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<=m;i++)
{
sum[][i]=;
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
dp[i&][j]=cal_sum(i-,max(,j-cnt[i]),j);
update_sum(i,j);
}
}
for(int i=a;i<=b;i++)
{
ans=cal_mod(ans+dp[n&][i]);
}
} void print()
{
cout<<ans<<endl;
} int main()
{
read();
solve();
print();
}