题目大意：一只牛想数蚂蚁，蚂蚁分成很多组，每个组里面有很多只蚂蚁，现在问你有多少种组合方式
（说白了就是问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
这题直接用滚动数组也是很快的
1 #include <stdio.h> 2 #include <stdlib.h> 3 #define MAX_N 1001 4 #define MAX_A 100 5 #define M 1000000 6 7 static int families[MAX_N]; 8 static int dp1[MAX_N *MAX_A]; 9 static int dp2[MAX_N *MAX_A]; 10 11 void Search(const int, const int, const int); 12 13 int main(void) 14 { 15 int families_sum, ants_sum, S, E, i, tmp; 16 while (~scanf("%d%d%d%d", &families_sum, &ants_sum, &S, &E)) 17 { 18 for (i = 1; i <= ants_sum; i++) 19 { 20 scanf("%d", &tmp); 21 families[tmp]++; 22 } 23 Search(families_sum, S, E); 24 } 25 return 0; 26 } 27 28 void Search(const int families_sum, const int S, const int E) 29 { 30 int i, j, L, now_amx, ans = 0; 31 int *exchange = NULL, *now = dp2, *prev = dp1; 32 33 now[0] = 1; 34 for (i = 0; i <= families[1]; i++)//基准情况 35 prev[i] = 1; 36 now_amx = families[1]; 37 for (i = 2; i <= families_sum; i++) 38 { 39 now_amx += families[i]; 40 for (j = 1, L = 1; j <= families[i]; j++)//先处理L<families[i]的情况 41 { 42 now[j] = (prev[j] + L) % M; 43 L += prev[j] % M; 44 } 45 for (;j <= now_amx; j++) 46 { 47 L -= prev[j - families[i] - 1]; 48 now[j] = (prev[j] + L) % M; 49 L += prev[j] % M; 50 } 51 exchange = prev; prev = now; now = exchange; 52 } 53 for (i = S; i <= E; i++) 54 ans = (ans + prev[i]) % M; 55 printf("%d ", ans); 56 }