题目大意：一只牛想数蚂蚁，蚂蚁分成很多组，每个组里面有很多只蚂蚁，现在问你有多少种组合方式
（说白了就是问1,1,1,...,2...,3...,4...）这些东西有多少种排列组合方式
这一道题我一开始想着去用矩阵乘法去做了，结果怎么想怎么不对，后来想着，如果对1,2,3,这些看成背包会怎么样呢？最后结果就压在最后一个背包就可以了
这么一想就懂了，其实就是要你找到递推关系，直接画一个矩阵拉几个箭头就很容易地看出来，对于一个矩阵，dp[i][j]等于dp[i-1][k] j-f[i]<=k<j的所有之和
因为我们是一个格子一个格子地数的，所以会有重复的计算，那么就弄一个队列区间维护长度就可以了，每一次循环减掉一开始的值，增加j的值
状态转移方程
dp[1][k] = 1 0<=k<=f[1]
dp[i][j]= ∑dp[i-1][k] j-f[i]<=k<j&& i<=f_sum
这题直接用滚动数组也是很快的
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1001
#define MAX_A 100
#define M 1000000 static int families[MAX_N];
static int dp1[MAX_N *MAX_A];
static int dp2[MAX_N *MAX_A]; void Search(const int, const int, const int); int main(void)
{
int families_sum, ants_sum, S, E, i, tmp;
while (~scanf("%d%d%d%d", &families_sum, &ants_sum, &S, &E))
{
for (i = ; i <= ants_sum; i++)
{
scanf("%d", &tmp);
families[tmp]++;
}
Search(families_sum, S, E);
}
return ;
} void Search(const int families_sum, const int S, const int E)
{
int i, j, L, now_amx, ans = ;
int *exchange = NULL, *now = dp2, *prev = dp1; now[] = ;
for (i = ; i <= families[]; i++)//基准情况
prev[i] = ;
now_amx = families[];
for (i = ; i <= families_sum; i++)
{
now_amx += families[i];
for (j = , L = ; j <= families[i]; j++)//先处理L<families[i]的情况
{
now[j] = (prev[j] + L) % M;
L += prev[j] % M;
}
for (;j <= now_amx; j++)
{
L -= prev[j - families[i] - ];
now[j] = (prev[j] + L) % M;
L += prev[j] % M;
}
exchange = prev; prev = now; now = exchange;
}
for (i = S; i <= E; i++)
ans = (ans + prev[i]) % M;
printf("%d\n", ans);
}