盒子与小球之三

描述

有N个相同的球,M个不同的盒子,每个盒子最多放K个球 
请计算将这N个球全部放入盒子中的方案数模1000007后的结果 

输入

三个正整数,依次为N,M,K

输出

输出方案数模1000007后的结果

样例输入4 2 3样例输出3提示

总共有3种方案,依次为

{ 3 , 1 }

{ 2 , 2 }

{ 1 , 3 }

对于100%的数据, N,M <= 5000 


这就是一道多集合组合数问题,具体讲解见https://stone906229046.blog.163.com/blog/static/267075001201610891627837/


代码:

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #define rep(q,p) for (int q=1;q<=p;q++) #define db double #define Mod 1000007 #define N 5005 using namespace std; int n,m,k; int f[2][N],s[2][N]; int main() { scanf("%d%d%d",&m,&n,&k); f[0][0]=1; for (int i=0; i<=5000; ++i) s[0][i]=1; for (int i=1; i<=n; i++) { memset(f[i&1],0,sizeof(f[i&1])); f[i&1][0]=1; memset(s[i&1],0,sizeof(s[i&1])); s[i&1][0]=1; for (int j=1; j<=m; j++) { f[i&1][j]=(f[i&1][j]+s[(i-1)&1][j])%Mod; if (j-min(j,k)-1>=0) f[i&1][j]=((f[i&1][j]-s[(i-1)&1][j-min(j,k)-1])%Mod+Mod)%Mod; s[i&1][j]=(s[i&1][j-1]+f[i&1][j])%Mod; } } printf("%d\n",f[n&1][m]); }
评论

© stonechina0616 | Powered by LOFTER