圣辇船直营菓子工房的补货：题解¶
出题人解法：整数拆分的五边形数递推及非递减采购搜索。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 五边形数定理与拆分生成函数给出
\[
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 使用稀疏的五边形数递推。逐个扫描所有小于当前花费的下标、跳过零系数，得到相同递推但需 \(O(X^2)\) 时间；稀疏枚举保留算法而减少无效项。
另外提供两种完整说明与程序：
- 完全背包：时间 \(O(X^2)\) 、空间 \(O(X)\) ，证明直接，不依赖五边形数定理；当前范围内可通过。
- 非递减搜索：直接枚举采购方案，空间 \(O(X)\) ，时间随拆分数量增长。作为枚举方案的备用实现保留，适用性能见其说明；不据此收紧或改变题目范围。
这是对经典拆分恒等式的应用，五边形数定理不属于本题实现者的原创贡献。