# 升级工具箱：题解

## 解法比较

出题人解法的两份实现都把第 $i$ 类的选择写成因子 $1+x+\cdots+x^{c_i}$ ，其中 $c_i$ 是该类可选数量上限，再逐类做朴素卷积，求各总数量的方案数。每一项对应一种合法数量选择，乘法展开恰好枚举全部组合，这是两种实现共同的正确性依据。

记 $S_i=\sum_{j\le i}c_j$ 、$S=S_n$ ，朴素卷积时间为 $O(\sum_i(S_{i-1}+1)(c_i+1))$ ，保留各阶段数组的出题人实现空间为 $O(n(S+1))$ .Codex（GPT-6）采用的实现利用每个新系数是旧系数一段连续区间的和，用滑动窗口转移，时间为 $O(n(S+1))$ ，滚动数组空间为 $O(S+1)$ .滚动存储也可单独用于朴素卷积；时间收益来自窗口和，计数模型不变。

## 按类型计数

第 $i$ 种可以选 $0$ 到 $C_i$ 个，因此答案是多项式

$$\prod_{i=1}^n(1+x+\cdots+x^{C_i})$$

的各项系数。令 $f_j$ 表示已处理类型中选出 $j$ 个工具箱的方案数，初始 $f_0=1$ .加入容量为 $C_i$ 的类型后：

$$g_j=\sum_{k=0}^{C_i} f_{j-k}$$

下标越界的 $f$ 视为 $0$ .每个方案唯一分解为“此前类型的方案”和“当前类型数量”，因此转移不重不漏。

## 滑动窗口

随着 $j$ 增加一，求和窗口加入 $f_j$ ，移除 $f_{j-C_i-1}$ .维护一个模 $100000007$ 的窗口和，每个系数只需常数时间。保存当前和下一层数组，处理完一类后交换。

容量为 $0$ 的类型仍占用自己的编号，计算后续容量时不能把编号前移。$n=0$ 时保留初始数组，输出 $1$ .

由于 $C_i\le\lfloor1000/i\rfloor$ ，总容量满足

$$S\le\sum_{i=1}^{1000}\left\lfloor\frac{1000}{i}\right\rfloor=7069$$

时间复杂度 $O(n(S+1))$ ，空间复杂度 $O(S+1)$ .窗口每次只加减一个已取模的系数，使用普通整数并及时归一化即可。