简答题 偏难
#7099

小球放盒子 有N个相同的球,M个不同的盒子,每个盒子最多放K个球 请计算将这N个球全部放入盒子中的方案数模1000007后的结果 时间限制:10000 内存限制…

小球放盒子

有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 &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;map&gt; #include &lt;string&gt; #include &lt;vector&gt; #define DEBUG(x) cout &lt;&lt; #x &lt;&lt; " = " &lt;&lt; x &lt;&lt; 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", &amp;N, &amp;M, &amp;K);   ways[0][0] = 1;   for (int i = 1; i &lt;= M; i++) {     ways[i][0] = 1;     ways[0][i] = 0;   }   for (int m = 1; m &lt;= M; m++) {     int sum = m;     for (int n = 1; n &lt;= N; n++) {       //            int l=min(n,K);       //            int r=0;       //            for(int i=0;i&lt;=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 &gt;= 0)         sum = (sum - ways[m - 1][n - K] + MOD) % MOD;     }   }   printf("%lld\n", ways[M][N]);   return 0; }</pre>
这道题暂未补解析。