# 圣辇船直营菓子工房的补货：题解

出题人解法：整数拆分的五边形数递推及非递减采购搜索。Codex（GPT-6）将递推整理为稀疏枚举，补齐模运算、证明与实现，并补充完全背包方案。

## 按花费归类

令 $P_s$ 为整数 $s$ 的无序正整数拆分数，$P_0=1$ .花费为 $s\le X$ 的采购方案与这样的拆分一一对应：价格就是拆分中的部件。任何部件都不超过 $X$ ，每种商品购买数也不超过 $X$ ，因此库存限制不会排除拆分。

$$A=\sum_{s=0}^{X}(X-s)P_s\pmod{998244353}$$

## 五边形数递推

[Euler 五边形数定理](https://dlmf.nist.gov/27.14#E4)与拆分生成函数给出

$$P_0=1,\qquad P_s=\sum_{k\ge1}(-1)^{k+1}\left(P_{s-k(3k-1)/2}+P_{s-k(3k+1)/2}\right)$$

负下标的值定义为零。简要推导：拆分生成函数乘以 $\prod_{i\ge1}(1-z^i)$ 等于一；将乘积按五边形数定理展开，比较正次数的系数并移项，就得到上述递推。因此按花费递增计算可以得到全部计数，再按余款加权求和。

只枚举不超过当前花费的广义五边形数，每项是已知的较小下标。减法后加模数再取模，保持余数非负。

## 复杂度与方案选择

每个花费仅有 $O(\sqrt X)$ 个有效偏移，总时间 $O(X\sqrt X)$ ，空间 $O(X)$ ；零预算单独看作常数工作。使用 64 位整数保存加权乘积，模后计数乘以预算不会超过 $80(998244353-1)$ .

[std.cpp](std.cpp) 使用稀疏的五边形数递推。逐个扫描所有小于当前花费的下标、跳过零系数，得到相同递推但需 $O(X^2)$ 时间；稀疏枚举保留算法而减少无效项。

另外提供两种完整说明与程序：

- [完全背包](solution-alternative-knapsack.zh.md)：时间 $O(X^2)$ 、空间 $O(X)$ ，证明直接，不依赖五边形数定理；当前范围内可通过。
- [非递减搜索](solution-alternative-search.zh.md)：直接枚举采购方案，空间 $O(X)$ ，时间随拆分数量增长。作为枚举方案的备用实现保留，适用性能见其说明；不据此收紧或改变题目范围。

这是对经典拆分恒等式的应用，五边形数定理不属于本题实现者的原创贡献。