Luogu5824 十二重计数法（子问题）

题意：求将 拆分成不超过 个无序整数的和方案数。

答案对 取模，。

---

法一：组合转化

在一个整数拆分中，将各个数写成“柱状统计图”的形式，即得到 Ferrers 图。

拆分 的 Ferrers 图如下所示 ：

要拆成不超过 个无序整数，即 Ferrers 图的“行数”不超过 。

接下来，将 Ferrers 图翻转，得到另一个 Ferrers 图，其对应另一个整数拆分 ：

我们观察翻转后产生的图有什么约束，答案是 ： 每一列的长度不超过 。

这等价于要求用 的数来拆分，于是答案是 类似 MSET 变换，可以 求解。

法二：二元生成函数

用 记录数字的和，用 记录数字的个数，列出整数拆分的 OGF 答案是 到 系数之和，可以先乘 （在 上前缀和），再提取 系数。

记 ，答案是 。

难以直接写出 的封闭形式，用扰动法观察其性质 两侧提取 系数得

其中 ，边界是 。

根据该递推，，得到相同的结果。