简答题
偏难
#7330
小球放盒子(2023.3) 有N个相同的球,M个不同的盒子,每个盒子最多放K个球 请计算将这N个球全部放入盒子中的方案数模1000007后的结果 时间限制:10…
小球放盒子(2023.3)
有N个相同的球,M个不同的盒子,每个盒子最多放K个球
请计算将这N个球全部放入盒子中的方案数模1000007后的结果
时间限制:10000
内存限制:131072
输入
三个正整数,依次为N,M,K
输出
输出方案数模1000007后的结果
样例输入
4 2 3
样例输出
3
提示
总共有3种方案,依次为 { 3 , 1 },{ 2 , 2 },{ 1 , 3 }。 对于100%的数据, N,M ≤ 5000
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#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;
}</pre><p><br/></p>
这道题暂未补解析。