题意分析

题目要求计算将$m$块相同的蛋糕分配到$n$个相同的盘子中的方法数。由于蛋糕和盘子都是不可区分的，因此这是一个典型的整数划分问题，即求将整数$m$划分为最多$n$个部分的方法数。

解题思路

1. 问题转化：将问题转化为求$m$的$n$部分划分数，其中每个部分可以为$0$。
2. 动态规划：使用动态规划来记录状态转移，设$dp[j]$表示将$j$块蛋糕分配到若干盘子中的方法数。
3. 状态转移：对于每个盘子$i$，考虑是否放入$i$块蛋糕，更新$dp[j]$的值。

实现步骤

1. 初始化：$dp[0] = 1$，表示$0$块蛋糕有一种分配方法。
2. 动态规划更新：
   • 遍历每个盘子$i$（从$1$到$n$）。
   • 对于每个$j$（从$i$到$m$），更新$dp[j] = (dp[j] + dp[j - i]) \mod 1000000007$。
3. 输出结果：$dp[m]$即为所求的方法数。

C++实现

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;
const int N = 4500;

int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<int> dp(N + 1, 0);
        dp[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= m; j++) {
                dp[j] = (dp[j] + dp[j - i]) % MOD;
            }
        }
        
        cout << dp[m] << endl;
    }
    return 0;
}

代码说明

1. 常量定义：

   • MOD = 1000000007：用于取模，防止数值过大。
   • N = 4500：题目中$n$和$m$的最大值。

2. 动态规划数组：

   • dp[j]：表示将$j$块蛋糕分配到若干盘子中的方法数。

3. 双重循环：

   • 外层循环遍历盘子数$i$（从$1$到$n$）。
   • 内层循环遍历蛋糕数$j$（从$i$到$m$），更新$dp[j]$的值。

4. 输出结果：

   • 直接输出$dp[m]$，即所求的方法数。