POJ 3046 Ant Counting（多重集组合数，归纳优化第三层循环）

http://poj.org/problem?id=3046
就是这种模型：
给 $N$N 种物品，每种有 $a_i$ai​ 个，从中选出 $m$m 个，求方案数？
参考博客：https://blog.csdn.net/ac_hell/article/details/51405598
还是直接来样例比较直接：
样例就是：有 两个 $1$1，两个 $2$2 ，一个 $3$3，问从中选 $2$2 个数 加上 从中选 $3$3 个数的方案数之和
$dp\left[i\right]\left[j\right]$dp[i][j] 表示从前 $i$i 种物品中，选出 $j$j 个的方案数
那就是求 $dp\left[3\right]\left[2\right]+dp\left[3\right]\left[3\right]$dp[3][2]+dp[3][3]

求 $dp\left[3\right]\left[2\right]$dp[3][2]：
就是当前在处理第三种物品
假如这次第三种物品一个都不拿，那么方案数就是 $dp\left[2\right][3-0]$dp[2][3−0]
假如这次第三种物品拿 $1$1 个，那么方案数就是 $dp\left[2\right][3-1]$dp[2][3−1]
假如这次第三种物品拿 $2$2 个，那么方案数就是 $dp\left[2\right][3-2]$dp[2][3−2]
依次类推。。。。
所以方程就出来了：

$dp\left[i\right]\left[j\right]=dp[i-1][j-0]+$dp[i][j]=dp[i−1][j−0]+ $d[i-1][j-1]+dp[i-1][j-2]+.....+dp[i-1][j-j]$d[i−1][j−1]+dp[i−1][j−2]+.....+dp[i−1][j−j]

#include"iostream"
#include"string.h"
using namespace std;
const int MOD=1e6;
const int maxn=1e3+5;
int dp[2][maxn*maxn];
int a[maxn];
int main()
{
    int N,ge,qL,qR;
    while(cin>>N>>ge>>qL>>qR)
    {
        memset(a,0,sizeof(a));
        for(int i=1;i<=ge;i++)
        {
            int t;
            cin>>t;
            a[t]++;
        }
        int pre=0,now=0;
        memset(dp,0,sizeof(dp));
        dp[0][0]=dp[1][0]=1;
        int M=0;
        for(int i=1;i<=N;i++)
        {
            now=pre^1;
            M+=a[i];
            for(int j=1;j<=M;j++)
            {
                if(j<=a[i])dp[now][j]=dp[pre][j]+dp[now][j-1];
                else dp[now][j]=dp[pre][j]+dp[now][j-1]-dp[pre][j-1-a[i]];
                dp[now][j]=(dp[now][j]%MOD+MOD)%MOD;
            }
            pre=now;
        }
        long long ans=0;
        for(int i=qL;i<=qR;i++)
        {
            ans+=dp[now][i];
            if(ans>MOD)ans%=MOD;
        }
        cout<<ans<<endl;
    }
}