# 无标号容器分配: 补充解法

## 五边形数递推与去除大部件

Codex（GPT-6）将经典 Euler 五边形数恒等式和生成函数截断应用于本题，程序见 [alternative.cpp](alternative.cpp)。分拆共轭及背包解法见[主题解](solution.zh.md)。以下多项式只保留次数不超过 $n$ 的系数。

无限制整数分拆的生成函数为

$$P(x)=\prod_{j\ge1}\frac1{1-x^j}$$

Euler 五边形数恒等式给出其逆，公式可参见 [NIST DLMF 27.14](https://dlmf.nist.gov/27.14#E4)：

$$\prod_{j\ge1}(1-x^j)=1+\sum_{k\ge1}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right)$$

由两者乘积为一，比较每个正次数 $s$ 的系数，得到

$$p_s=\sum_{k\ge1}(-1)^{k-1}\left(p_{s-k(3k-1)/2}+p_{s-k(3k+1)/2}\right)$$

其中 $p_0=1$ ，负下标项按零处理。每个 $s$ 只有 $O(\sqrt s)$ 个有效五边形数，因此可在 $O(n\sqrt n)$ 时间内计算全部无限制分拆数。

## 去掉超过容器上限的部件

由共轭对应，目标生成函数是

$$P_m(x)=\prod_{j=1}^{m}\frac1{1-x^j}=P(x)\prod_{j=m+1}^{n}(1-x^j)\pmod{x^{n+1}}$$

次数大于 $n$ 的因子不会影响所需答案。每次乘以 $1-x^j$ ，对 $s=n,n-1,\ldots,j$ 执行 $p_s\leftarrow p_s-p_{s-j}$ .这里必须倒序，使右侧使用乘法之前的系数；这样一次处理恰好抵消允许部件 $j$ 的几何级数因子。

五边形递推来自精确的生成函数恒等式，逐因子抵消后恰好只允许大小不超过 $m$ 的部件。再通过共轭对应，即得到原容器问题的全部答案。所有加减按题目模数规范化。

总时间 $O(n\sqrt n+\max(n-m,0)^2)$ ，空间 $O(n)$ .当 $m\ge n$ 时不需要抵消因子，只有 $O(n\sqrt n)$ ；当 $m$ 很小时，抵消部分接近二次，而背包更合适。这是具有不同适用区间的并列方案，完整范围均已测试。