升级工具箱：题解¶

解法比较¶

出题人解法的两份实现都把第 \(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)\) .窗口每次只加减一个已取模的系数，使用普通整数并及时归一化即可。