有n种物品, 第i种物品有a个. 不同种类的物品可以互相区分, 但相同种类的无法区分

从这些物品中取出m个, 有多少种取法

求多重集组合数，并没有让枚举多重集组合

可是枚举应该怎么枚举呢？哈希判重？

dp[i][j] 表示前i种物品,一共拿了j个物品的方法数

为了得到dp[i][j]，那么可以从前i-1种物品取j-k个,再从第i种物品取k个即可

这个公式是O（n（m^2））的

优化一下效率

决策：第i种不选或者至少选一个

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-ant[i]-1]

然后给出实现，这里的答案把m的值从S到B都累加了

1 #include
     
       2 using namespace std; 3 const int maxn=100005; 4 const int MOD=1000000; 5 int T,A,S,B,ans; 6 int a[1005];  //一共这么多种，存每种几个  7 int f[2][maxn]; 8 int main() 9 {10     int x;11     scanf("%d%d%d%d",&T,&A,&S,&B);12     for(int i=1;i<=A;i++)13     {14         scanf("%d",&x);15         a[x]++;16     } 17     f[0][0]=f[1][0]=1;18     for(int i=1;i<=T;i++)  //一共几种数19     for(int j=1;j<=B;j++)  //Cn取m的那个m20         if(j-a[i]-1>=0)21             f[i%2][j]=(f[(i-1)%2][j]+f[i%2][j-1]-f[(i-1)%2][j-a[i]-1]+MOD)%MOD;22         else f[i%2][j]=(f[(i-1)%2][j]+f[i%2][j-1])%MOD;23     for(int i=S;i<=B;i++)24         ans=(ans+f[T%2][i])%MOD;25     printf("%d",ans);26     return 0;27 }
     

其实这个题给我印象最深的地方是%2，让我立刻想起了NOIP2014day1T3激扬的小鸟的满分做法