SSL-OI夏日合宿 杂题 LOJ#6089小Y的背包计数问题 根号分治

摘要： 文章讨论了LOJ #6089小Y的背包计数问题，该问题要求计算将大小为$n$的背包装满的方案数，其中物品数量也为$n$，每个物品的重量和数量均为其编号。解法采用了根号分治策略：对于重量大于$\sqrt{N}$的物品，视为无数量限制，使用数的划分（可重方式）求解；对于重量小于$\sqrt{N}$的物品，使用多重背包求解，复杂度为$O(N\sqrt{N})$。前置知识包括多重背包的单调队列优化和数的划分DP。

LOJ #6089

这题是集训第一天晚上的杂题, 由于本人本性爱咕, 所以集训第二周才来补题解.

前置知识

多重背包: 用单调队列优化, 做到$O(NM)$的复杂度.

数的划分: $n$个整数由$k$个整数组成的方案数(可重/不可重), $O(NK)$复杂度DP.

题意

背包大小为$n$, 物品数量为$n$, 第$i$个物品的重量为$i$, 数量为$i$.

问: 将背包装满的方案数是多少?

正解

对于大于$\sqrt{N}$的物品, 相当于没有数量限制. 我们用数的划分(可重方式)求出答案就好.

对于小于$\sqrt{N}$的物品, 我们用多重背包求出答案. 由于物品数量是$\sqrt{N}$, 背包大小是$N$, 所以复杂度为$O(N\sqrt{N})$.