POJ -- 3046、Ant Counting （多重集组合数，计数类dp）

题目vj链接

题面：

题意：
有 $T$T 种物品，第 $i$i 种物品有 $n_i$ni​ 个。

从中选出若干个物品组成一个集合，问集合大小位于区间 $[S,B]$[S,B] 的不同的集合有多少个。

两个集合相同当且仅当两个集合相同种类的物品个数一样。

题解：
我们设 $dp[i][j]$dp[i][j] 为选择了前 $i$i 种物品且集合大小为 $j$j 时不同的方案数。

转移方程显然： $dp[i][j]=\sum\limits_{k=0}^{min(j,n_i)}dp[i-1][j-k]$dp[i][j]=k=0∑min(j,ni​)​dp[i−1][j−k]。

那么此题的时间复杂度为 $O(T*\sum n_i*max(n_i))$O(T∗∑ni​∗max(ni​))

考虑化简 $dp$dp。

若 $j<=n_i$j<=ni​ ， $dp[i][j]=dp[i-1][j]+dp[i][j-1]$dp[i][j]=dp[i−1][j]+dp[i][j−1]

若 $j>n_i$j>ni​，$dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1-n_i]$dp[i][j]=dp[i−1][j]+dp[i][j−1]−dp[i−1][j−1−ni​]

时间复杂度 $O(T*\sum n_i)$O(T∗∑ni​)

代码：
感觉数据没有出满。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
//#include<unordered_map>
//#include<unordered_set>
#include<set>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x)  (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=1000000;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int maxp=100100;
const int up=1100;

int dp[2][maxn];
int pc[maxn];
int t,n,s,b;

int main(void)
{
    while(scanf("%d%d%d%d",&t,&n,&s,&b)!=EOF)
    {
        memset(pc,0,sizeof(pc));
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        int x;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            pc[x]++;
        }
        int sum=0;
        for(int i=1;i<=t;i++)
        {
            sum+=pc[i];
            int now=i&1;
            for(int j=0;j<=sum;j++)
            {
                if(j<=pc[i]) dp[now][j]=(dp[now^1][j]+dp[now][j-1])%mod;
                else dp[now][j]=(dp[now^1][j]+dp[now][j-1]-dp[now^1][j-1-pc[i]])%mod;
            }
        }
        int ans=0;
        for(int i=s;i<=b;i++)
            ans=(ans+dp[t&1][i])%mod;

        printf("%d\n",(ans+mod)%mod);
    }
    return 0;
}