解题思路

这道题目要求我们计算从给定的蚂蚁家族中，可以组成多少组大小为S到B的蚂蚁集合。每个蚂蚁家族有不同数量的蚂蚁，且集合中的蚂蚁顺序不重要（即{1,2}和{2,1}视为同一个集合）。我们需要高效地计算这些组合的总数，并输出结果的最后六位数字。

1. 问题分析

• 输入：蚂蚁家族的数量T、总蚂蚁数A、最小集合大小S、最大集合大小B，以及每个蚂蚁的具体家族编号。
• 输出：大小为S到B的集合总数，结果取模1,000,000。

2. 动态规划方法

为了高效计算组合数，我们可以使用动态规划（DP）的方法。具体步骤如下：

1. 统计家族数量：

   • 首先统计每个蚂蚁家族的数量，即数组a[]，其中a[i]表示家族i的蚂蚁数量。

2. 初始化DP数组：

   • dp[i][j]表示从前i个家族中选取j只蚂蚁的组合数。
   • 初始化dp[i][0] = 1，表示从前i个家族中选取0只蚂蚁的组合数为1（即不选任何蚂蚁）。

3. 填充DP数组：

   • 对于每个家族i，从1到T：
     • 对于选取的蚂蚁数量j，从1到A：
       • 如果当前家族i的蚂蚁数量a[i]足够（即j ≤ a[i]），则组合数为dp[i-1][j] + dp[i][j-1]。
       • 如果当前家族i的蚂蚁数量不足（即j > a[i]），则组合数为dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1-a[i]]。
       • 每次计算后取模1,000,000，防止溢出。

4. 计算结果：

   • 遍历集合大小从S到B，累加dp[T][i]的值，得到最终的组合总数。

3. 关键点

• 组合数的递推：通过动态规划递推组合数，避免重复计算。
• 取模操作：由于结果可能非常大，需要在每次计算后取模，确保结果正确。
• 边界条件：正确处理家族数量为0或蚂蚁数量为0的情况。

4. 示例解释

对于输入样例：

3 5 2 3
1
2
2
1
3

• 家族1有2只蚂蚁，家族2有2只蚂蚁，家族3有1只蚂蚁。
• DP数组填充后，dp[3][2] = 5（大小为2的集合数），dp[3][3] = 5（大小为3的集合数）。
• 最终结果为5 + 5 = 10。

方法选择

• 动态规划：适用于组合计数问题，能够高效计算大规模数据。
• 模运算：确保结果在合理范围内，避免溢出。

标程

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1<<30;
const LL maxn = 1e5+10;
const int mod = 1e6;

int N, M, l, r, a[1010];
int dp[1010][maxn]; //前i种取j个的组合数
int main()
{
	int input;
	cin >> N >> M >> l >> r;
	for(int i = 1; i <= M; ++i){
		cin >> input;
		++a[input];
	}
	
	//初始化, 一个也不取总有一种
	for(int i = 0; i <= N; ++i)
		dp[i][0] = 1;
	
	for(int i = 1; i <= N; ++i){
		for(int j = 1; j <= M; ++j){
			if(j-a[i]-1 >= 0) //j>=a[i]时
				dp[i][j] = (dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-a[i]]+mod)%mod;
			else              //j<a[i]时
				dp[i][j] = (dp[i][j-1]+dp[i-1][j]+mod)%mod;
		}
	}
	int ans = 0;
	for(int i = l; i <= r; ++i)
		ans = (ans+dp[N][i]+mod)%mod;
	cout << ans << endl;
	
	return 0;
}