题意简化

容量为 $n$ 的背包，有 $n$ 种物品：

• 第 $i$ 种物品体积为 $i$
• 第 $i$ 种物品最多可以用 $i$ 个

求装满背包的方案数，模 $23333333$。

$n \le 10^5$。

核心思想：根号分治

1. 问题分析

这是多重背包问题，但 $n$ 很大，直接 DP $O(n^2)$ 会超时。

观察：物品体积从 $1$ 到 $n$，但大体积物品数量少。

2. 根号分治

设 $m = \lfloor \sqrt{n} \rfloor$（约 316）。

将物品分为两类：

1. 小物品：体积 $\le m$（约316种）
2. 大物品：体积 $> m$（约 $n-m$ 种）

3. 分别处理

第一部分：大物品（体积 > m）

大物品最多用 $\lfloor \frac{n}{m+1} \rfloor$ 个，数量少。

设 $dp_1[i][j]$：用了 $i$ 个大物品，体积和为 $j$ 的方案数。

转移：

• 加一个体积最小的（$m+1$）：$dp_1[i][j] = dp_1[i-1][j-(m+1)]$
• 所有大物品体积+1（巧妙转化）：$dp_1[i][j] = dp_1[i][j-i]$

最终 $g[j] = \sum_{i} dp_1[i][j]$ 表示用大物品凑出体积 $j$ 的方案数。

第二部分：小物品（体积 ≤ m）

小物品体积小但数量多，用前缀和优化的多重背包。

设 $dp_2[i][j]$：只考虑前 $i$ 种小物品（体积1..i），凑出体积 $j$ 的方案数。

转移（完全背包但有限制）：

$$dp_2[i][j] = \sum_{k=0}^{\min(i, \lfloor j/i \rfloor)} dp_2[i-1][j-k\cdot i] $$

用前缀和优化到 $O(1)$：

• 维护前缀和数组 $sum[j]$
• 注意每个物品最多用 $i$ 个，所以减去 $j \ge i(i+1)$ 的部分

最终 $f[j] = dp_2[m][j]$ 表示用小物品凑出体积 $j$ 的方案数。

4. 合并答案

背包总容量 $n$，可以：

• 用大物品凑 $i$ 体积
• 用小物品凑 $n-i$ 体积

方案数：

$$ans = \sum_{i=0}^n f[i] \times g[n-i]$$

代码解析

变量说明

• m = sqrt(n)：分界点
• dp_1[][]：大物品 DP
• dp_2[][]：小物品 DP
• f[], g[]：最终方案数
• sum[]：前缀和优化

函数功能

1. solve_1()：处理大物品
2. solve_2()：处理小物品（前缀和优化多重背包）

复杂度分析

• 大物品 DP：$O(\sqrt{n} \times n)$
• 小物品 DP：$O(\sqrt{n} \times n)$
• 总复杂度：$O(n\sqrt{n}) \approx 3\times 10^7$，可过 $n=10^5$

关键优化

1. 根号分治

• 大物品：体积大，数量少，用特殊 DP
• 小物品：体积小，用优化的多重背包

2. 大物品的巧妙转化

将所有大物品体积同时+1的转移，减少状态数。

3. 前缀和优化

小物品多重背包用前缀和降到 $O(1)$ 转移。

样例解释

$n=3$，物品：

• 体积1：最多1个
• 体积2：最多2个
• 体积3：最多3个

方案：

1. 1+1+1
2. 3

输出：2

代码特点

• 根号分治经典应用
• 大物品的特殊 DP 设计
• 小物品前缀和优化
• 模运算处理