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

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})$.