无标号容器分配: 补充解法¶
五边形数递推与去除大部件¶
Codex（GPT-6）将经典 Euler 五边形数恒等式和生成函数截断应用于本题，程序见 alternative.cpp。分拆共轭及背包解法见主题解。以下多项式只保留次数不超过 \(n\) 的系数。
无限制整数分拆的生成函数为
\[
P(x)=\prod_{j\ge1}\frac1{1-x^j}
\]
Euler 五边形数恒等式给出其逆，公式可参见 NIST DLMF 27.14：
\[
\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\) 很小时，抵消部分接近二次，而背包更合适。这是具有不同适用区间的并列方案，完整范围均已测试。