放苹果

GitHub跳转原题关系图返回列表

盘子相同就按非增序列去重,答案即 M 拆成不超过 N 个部分的拆分数;按「是否有空盘」分类递推打表,每组询问 O(1)。

OJ: roj

题目 ID: 1222

难度:普及-

标签:递推整数划分动态规划递归python

创建: 2026-10-07 15:23

更新: 2026-10-07 15:23

形式化题目

给定 MM 个相同的苹果与 NN 个相同的盘子,允许有些盘子空着, 问把苹果全部放进盘子里的分法数 KK。

由于盘子相同,{5,1,1}\{5,1,1\} 与 {1,5,1}\{1,5,1\} 是同一种分法, 因此一种分法只能由一个非增序列刻画:

a1⩾a2⩾⋯⩾aN⩾0,∑i=1Nai=M.a_1 \geqslant a_2 \geqslant \cdots \geqslant a_N \geqslant 0, \qquad \sum_{i=1}^{N} a_i = M .

其中 aia_i 是"某个盘子里的苹果数",第 ii 项与第 ii 个盘子无关——排序只是为了让表示唯一。 于是要求的就是整数的分拆数:

K=p(M; 部分数⩽N),K = p(M;\ \text{部分数} \leqslant N),

即把 MM 拆成不超过 NN 个正整数之和的方案数。两种表示可以互相还原:非增序列去掉末尾的一串 00 就得到拆分的加数列表(按从大到小排列),反过来把加数按非增顺序填进序列、后面补 00 就回到原序列。

输入为 tt 组询问,每组给出 M,NM, N,逐组输出 KK;0⩽t⩽200 \leqslant t \leqslant 20,1⩽M,N⩽101 \leqslant M, N \leqslant 10。

正解

思路

朴素做法。 逐盘决定苹果数,并强制"后面的盘不多于前面的盘": dfs(当前盘下标, 上一盘苹果数, 剩余苹果数),走到最后一盘时若剩余苹果数不超过上一盘就记一种方案。 这条强制去重正是题目里"盘子相同"的那句话——它一次性排除了所有重排: 比如 77 分给 33 个盘时只会产出 (4,3,0)(4,3,0),不会再出现 (3,4,0)(3,4,0)。

这个搜法对本题规模(M,N⩽10M, N \leqslant 10,答案最大 K=p(10;⩽10)=42K = p(10;\leqslant 10) = 42)本身跑得飞快, 真正的问题是同一个状态被反复重算:子问题的规模完全由「还剩多少苹果」+「还剩几个盘」 这两个量决定,而不同的搜索分支会反复走到同一对值。 实测这个朴素 DFS 算 f(10,10)f(10,10) 要展开 853 次调用, 而不同的「剩余苹果数 + 剩余盘数」组合只有 100 个: 以退化状态(剩 00 个苹果、11 个盘)为例,它在这棵递归树里被算到了 41 次。 瓶颈不是规模,而是"重复"——把每个状态只算一次就够了。

关键观察:按"有没有空盘"给分法分类。 记 f(m,n)f(m, n) 为"mm 个苹果进 nn 个盘"的分法数, 则任何一种分法都恰好落进下面两类之一:

类别 特征 与哪个子问题一一对应
至少一个空盘 至少有一个 ai=0a_i = 0 把 MM 个苹果放进 N−1N-1 个盘(多出来的空盘直接删掉),方案数 f(M,N−1)f(M, N-1)
每个盘都非空 所有 ai⩾1a_i \geqslant 1 每盘先各放 11 个,再把剩下的 M−NM-N 个放进 NN 个盘(仍可空),方案数 f(M−N,N)f(M-N, N)

两类互不相交又覆盖全部方案,两边的对应关系都是双射(删掉一个空盘 / 每盘各减 11 后可逆), 所以直接相加:

f(m,n)=f(m,n−1)+f(m−n,n)(1⩽n⩽m).f(m, n) = f(m, n-1) + f(m-n, n) \qquad (1 \leqslant n \leqslant m).

这就是整数分拆的经典递推。它每算一个 f(m,n)f(m, n) 只用两个已经更小的参数, 所以把 mm 从小到大、nn 从小到大扫一遍,整张表就能无循环依赖地填完—— 这也正是 C++ 版不写递归、直接递推打表的原因。

边界。 几个退化情况必须单独定死,否则递推没有终点:

  • f(0,n)=1f(0, n) = 1:苹果已经放完,剩下的盘子只能全空着,这算一种分法(0 个苹果时 aia_i 全为 0);
  • f(m,0)=0f(m, 0) = 0(m>0m > 0):一个盘子都没有,苹果无处可放;
  • 当 n>mn > m 时不必让递推下降到 n=0n = 0:已经"每盘非空"的支路会算出 f(m−n,n)f(m-n, n) 这种负数下标, 而事实上盘子多于苹果时,多出来的 n−mn - m 个盘子必然空着, 这些格子在非增序列里就是末尾的一串 00,所以
f(m,n)=f(m,m)(n>m).f(m, n) = f(m, m) \qquad (n > m).

加上这一条,n>mn > m 的支路被一次性砍掉,递归范围只剩正方形 m,n⩽10m, n \leqslant 10。

状态数决定写法。 状态只有 (m,n)(m, n) 两个参数、各自不超过 1010, 所以不需要任何优化技巧,直接把全部 11×1111 \times 11 个状态打出来即可:

  • Python 版用 functools.cache 记忆化递归,天然只算到用得到的那些状态;
  • C++ 版直接从小到大递推填 dp[m][n] 二维表,之后每组询问是一次数组取值。

下面用样例 M=7,N=3M = 7, N = 3 走一遍:f(7,3)=f(7,2)+f(4,3)=4+4=8f(7, 3) = f(7, 2) + f(4, 3) = 4 + 4 = 8。

flowchart TD
  R["f(7,3) = 8"] --> A["至少一个空盘:f(7,2) = 4"]
  R --> B["每盘都非空:f(4,3) = 4"]
  A --> A1["(7) (6,1) (5,2) (4,3)"]
  B --> B1["(5,1,1) (4,2,1) (3,3,1) (3,2,2)"]

读这张图要抓住两点。第一,左支的 4 种里都至少有一个 00,右支的 4 种每一项都 ⩾1\geqslant 1, 两列拼起来刚好是不重不漏的 8 种,这正是"分类相加"的直接体现。 第二,右支的 4 种把每项都减 11 后得到 (4,0,0)(4,0,0)、(3,1,0)(3,1,0)、(2,2,0)(2,2,0)、(2,1,1)(2,1,1), 恰好是 f(4,3)f(4,3) 的全部方案——这就是"每盘各减 11"是可逆双射的具体样貌。

下表是 m⩽7m \leqslant 7、n⩽3n \leqslant 3 时的局部递推结果,行是苹果数 mm、列是盘子数 nn, 单元格即 f(m,n)f(m, n);表格可以直接按公式逐格验算。

m\nm \backslash n 0 1 2 3
0 1 1 1 1
1 0 1 1 1
2 0 1 2 2
3 0 1 2 3
4 0 1 3 4
5 0 1 3 5
6 0 1 4 7
7 0 1 4 8

三点观察:n=0n = 0 那一列除了 m=0m = 0 全是 00;n=1n = 1 那一列全是 11(只能全放在这一个盘里); n⩾mn \geqslant m 之后每行数值不再增长,正是 f(m,n)=f(m,m)f(m,n) = f(m,m) 的表现—— 表中 m=2m = 2 那一行往右看,n=2n = 2 与 n=3n = 3 都是 22(nn 再大也还是 22)。 样例要的 f(7,3)=8f(7, 3) = 8 就落在表右下角。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:14
# update_at: 2026-10-07 15:14

import sys
from functools import cache


@cache
def ways(m: int, n: int) -> int:
    """把 m 个相同苹果放进 n 个相同盘子(允许空盘)的分法数。"""
    if m == 0:
        return 1                              # 苹果已放完,剩下的盘子只能空着
    if n == 0:
        return 0                              # 没有盘子,剩下的苹果无处可放
    if n > m:
        return ways(m, m)                     # 盘子多于苹果,多出来的盘子必然空着
    return ways(m, n - 1) + ways(m - n, n)    # 至少一个空盘 + 每盘先放一个再分剩下的


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    t = next(data, 0)                         # 测试数据组数;空输入按 0 组处理

    out: list[str] = []
    for _ in range(t):
        m, n = next(data), next(data)         # 本组询问的两个量
        out.append(str(ways(m, n)))

    if out:                                   # t = 0 时题目要求输出为空,不能多一个换行
        print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 15:14
 * update_at: 2026-10-07 15:14
 */
// main.cpp:放苹果。把 M 个相同苹果放进 N 个相同盘子(允许空盘)的分法数,
// 就是「M 拆成不超过 N 个正整数之和」的拆分数,用整数分拆的递推式一次打表,每组询问 O(1)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 10; // 题面 M 的上限
const int MAXN = 10; // 题面 N 的上限

// dp[m][n]:把 m 个相同苹果放进 n 个相同盘子、允许空盘的分法数,
// 即 m 的不超过 n 个部分的拆分数。答案最大是 dp[10][10] = 42。
ll dp[MAXM + 1][MAXN + 1];

// 按 m 从小到大、m 相同时按 n 从小到大打表
void build_table() {
    for (int n = 0; n <= MAXN; n++) dp[0][n] = 1; // 0 个苹果:全是空盘,唯一分法
    for (int m = 1; m <= MAXM; m++) {
        dp[m][0] = 0; // 一个盘子都没有,非零个苹果放不下
        for (int n = 1; n <= MAXN; n++) {
            if (n > m) {
                dp[m][n] = dp[m][m]; // 盘子比苹果多,多出来的盘子必然空着,可以砍掉
            } else {
                // 至少一个空盘:dp[m][n-1];每盘都非空:先各放 1 个,剩下 m-n 个任意放
                dp[m][n] = dp[m][n - 1] + dp[m - n][n];
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    build_table();

    ll t;
    if (!(cin >> t)) return 0; // 无输入时直接结束
    while (t-- > 0) {
        ll m, n;
        cin >> m >> n;
        cout << dp[m][n] << "\n";
    }
    return 0;
}

复杂度

  • 时间:预处理填满 11×1111 \times 11 的表,每个状态 O(1)O(1),所以是 O(Mmax⁡Nmax⁡)O(M_{\max} N_{\max})(本题 100100 次加法); 之后每组询问 O(1)O(1)。总计 O(Mmax⁡Nmax⁡+t)O(M_{\max} N_{\max} + t)。Python 版用 cache 记忆化, 只会展开实际被询问的状态,上界同样是 O(Mmax⁡Nmax⁡)O(M_{\max} N_{\max})。
  • 空间:O(Mmax⁡Nmax⁡)O(M_{\max} N_{\max}) 的状态表(本题 121121 个整数),无递归以外的额外开销; Python 记忆化递归深度上界 O(M+N)O(M + N)。
  • 实测:C++ 编译后 10 个测试点单点 ⩽0.010\leqslant 0.010 s / 峰值 8.4 MB, Python 单点 ⩽0.019\leqslant 0.019 s / 峰值 14.6 MB(限时 1000 ms / 64 MB), 两种实现在 10 个测试点上逐字节输出一致。

总结

  • "盘子相同"就是去重约定:它把分法与"非增序列"一一对应,于是题目从"放球"变成了整数分拆; 如果盘子是不同的,答案会变成隔板法组合数 (M+N−1N−1)\binom{M+N-1}{N-1},7,37,3 就该是 3636 而不是 88。
  • 分类的依据要能反向还原:按"至少一个空盘 / 每盘非空"分,两类都能由子问题可逆地构造出来 (删空盘、每盘减 11),所以既能相加也不会重复计数,这是本题唯一的推导步骤。
  • 边界定死两头:f(0,n)=1f(0, n) = 1、f(m,0)=0f(m, 0) = 0,再加上 n>m⇒f(m,n)=f(m,m)n > m \Rightarrow f(m, n) = f(m, m) 的剪枝,递推就能稳稳落地;少了任何一条都会出现负数下标或漏算空盘方案。
  • 范围小就别硬套技巧:状态只有 O(MN)O(MN) 个且都很小,直接打表 + 每组 O(1)O(1) 查询是最清楚的写法; Python 侧用 cache 记忆化就能达到同样的复杂度。
  • 读入细节:t=0t = 0 是题面允许的合法输入,此时不能输出任何字符(连换行都不能多), 代码里用 if out: 守住这一条。