A39809. 盒子与小球
填空题
较难
知识点
题目描述
盒子与小球
题目描述
有N个相同的球，M个不同的盒子，每个盒子最多放K个球
请计算将这N个球全部放入盒子中的方案数模1000007后的结果
输入
三个正整数，依次为N，M，K
输出
输出方案数模1000007后的结果
样例输入
4 2 3
样例输出
3
提示
总共有3种方案，依次为
{ 3 ， 1 }
{ 2 ， 2 }
{ 1 ， 3 }
对于100%的数据， N，M <= 5000
参考答案
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<cstring>
#define DEBUG(x) cout << #x << " = " << x << endl
typedef long long ll;
using namespace std;
const int MAXN=5e3+10;
const int MOD=1000007;
int N,M,K;
ll ways[MAXN][MAXN];
///前m个盒子放入n个球的放法
int main()
{
// freopen("in.txt","r",stdin);
scanf("%d %d %d",&N,&M,&K);
ways[0][0]=1;
for(int i=1;i<=M;i++){
ways[i][0]=1;
ways[0][i]=0;
}
for(int m=1;m<=M;m++){
int sum=m;
for(int n=1;n<=N;n++){
// int l=min(n,K);
// int r=0;
// for(int i=0;i<=l;i++){
// r=(r+ways[m-1][n-i])%MOD;
// }
ways[m][n]=sum;
sum=(sum+ways[m-1][n+1])%MOD;
if(n-K>=0)sum=(sum-ways[m-1][n-K]+MOD)%MOD;
}
}
printf("%lld\n",ways[M][N]);
return 0;
}
上一题
下一题