题解 | #放苹果#

#include <iostream>
using namespace std;

//统计m个相同的苹果放入n个相同的盘子中有多少种放法，其中o为每个盘子可放的最多苹果个数
int counts(const int m, const int n, const int o) {
    //若苹果数为0，则只有一种放法
    if (m == 0)
        return 1;
    //若盘子数为0，但苹果数不为0，则没有放法或前几个盘子的放法不成立
    if (n == 0)
        return 0;
    //若只有一个苹果，则无论放到哪个盘子都是一样的，只有一种放法
    if (m == 1)
        return 1;
    //若只有一个盘子，则苹果都只能放到这个盘子里，只有一种放法
    if (n == 1)
        return 1;
    //假设往第一个盘子里放i个苹果，为方便计算，令i从大到小开始统计
    //第一个盘子里的苹果个数不能超过苹果总数，也不能超过单个盘子里的最大苹果数，所以取i的最大值为m和o的较小者
    int i = m < o ? m : o;
    //如果盘子的个数超过苹果的个数，由于单个苹果不能拆分，有n-m个盘子一直是空的，统计前m个盘子的放法即可
    if (m < n)
        return counts(m, m, i);
    //用于记录放法的个数，便于累加
    int count = 0;
    do {
        //递归求出第一个盘子放了i个苹果的放法
        count += counts(m - i, n - 1, i);
        i--;
        //将苹果平均分给每个盘子时每个盘子有m/n个苹果，若第一个盘子里所放苹果少于平均值，则必有盘子里的苹果多于平均值，会与之前统计过的放法重复
        //由于m/n不总是整数，将运算数转化为浮点类型确保结果准确
    } while (i >= (float)m / n);
    return count;
}

int main() {
    int m, n;
    while (cin >> m >> n) { // 注意 while 处理多个 case
        cout << counts(m, n, m) << endl;
    }
}
// 64 位输出请用 printf("%lld")