LOJ6089 小Y的背包计数问题(根号分治,计数dp)

题目链接

LOJ

题意简述

你有体积为 $i$ ($1\le i\le n$) 的物品 $i$ 个,同体积物品在计数时没有区别,求装满大小为 $n$ 的背包的方案数。

$1\le n\le 10^5$。

简要作法

体积大于等于 $\sqrt n$ 的物品可以无限选,所以考虑分开处理小于根号的和大于等于根号的。

小于根号的

令 $f_{i, j}$ 表示从前 $i$ 种物品中选体积为 $j$ 的方案数。
$$
f_{i, j} = \sum\limits_{k = 0}^{\min(i, \left\lfloor\frac j i\right\rfloor)}f_{i-1, j - ik}
$$
可以使用模 $i$ 同余的前缀和优化。

这部分的时间复杂度为 $O(n\sqrt n)$,空间复杂度可以优化至 $O(n)$。

大于等于根号的

令 $g_{i, j}$ 表示选择 $i$ 个物品体积为 $j$ 的方案数。

转移有两种方式:

  1. 向背包中放入一个体积为 $\left\lceil\sqrt n\right\rceil$ 的物品。
  2. 将背包中所有物品体积加一。

$$
g_{i, j} = g_{i - 1, j - \left\lceil\sqrt n\right\rceil} + g_{i, j - i}
$$

由于最多选 $\left\lfloor\sqrt n\right\rfloor$ 个物品,第一维大小为 $O(\sqrt n)$,这部分复杂度也是 $O(n\sqrt n)$。

合并

相当于求卷积的一位。

两部分加起来体积为 $n$ 就计入答案。

需要注意的是,第二部分中体积为 $k$ 的方案数是 $\sum\limits_{i=0}^{\left\lfloor\sqrt n\right\rfloor}g_{i, k}$,而不是某个单独的 dp 值。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cmath>
#include <cstdio>
#include <cstring>

const int mod = 23333333;
const int N = 100010;

int n, b, f[N], pre[N], g[2][N], cur, ans;

int main()
{
scanf("%d", &n);

b = int(sqrt(n) + 1);

f[0] = 1;

for (int i = 1; i < b; ++i)
{
for (int j = 0; j <= n; ++j) pre[j] = (f[j] + (j >= i ? pre[j - i] : 0)) % mod;
for (int j = 0; j <= n; ++j)
{
if (j < i * (i + 1)) f[j] = pre[j];
else f[j] = (pre[j] - pre[j - i * (i + 1)] + mod) % mod;
}
}

ans = f[n];

g[cur][0] = 1;

for (int i = 1; i < b; ++i)
{
memset(g[cur ^= 1], 0, sizeof(int) * (i * b));
for (int j = i * b; j <= n; ++j)
{
g[cur][j] = (g[cur ^ 1][j - b] + g[cur][j - i]) % mod;
ans = (ans + 1ll * f[n - j] * g[cur][j]) % mod;
}
}

printf("%d", ans);

return 0;
}