题目描述

有一个大小为 $n$ 的背包和 $n$ 种物品，其中第 $i$ 种物品的体积为 $i$，数量为 $i$。求把背包恰好装满的方案数。

题解1

算法思路

阈值思想

这个问题直接去看是一个多重背包。但直接做多重背包，复杂度为$O(n^3)$，使用单调队列（这里是方案数，可以直接前缀和）优化多重背包复杂度则是 $O(n^2)$。

我们令 $S = \sqrt n$，则体积大于 $S$ 的物品肯定无法全部放入背包中（因为第 $i$ 种物品的数量为 $i$，当 $i > S$ 时，$i \times i > n$），可以看作有无限个。

因此，我们可以：

• 对体积 $\le S$ 的物品做多重背包；
• 对体积 $> S$ 的物品做完全背包。

最后合并答案时，只需要 $O(n)$ 扫一遍即可。

---

一、多重背包（体积 $\le S$）

众所周知，多重背包计数问题可以转化为完全背包。

具体做法：

1. 先跑一遍完全背包；
2. 然后倒序枚举 $j$，令 $f_{i,j}$ 减去不合法答案 $f_{i,j-(i+1)\times i}$。

由于只有 $\sqrt n$ 个物品体积 $\le S$，所以这一部分的复杂度为 $O(n\sqrt n)$。

当然，直接使用单调队列（前缀和）优化多重背包复杂度也是 $O(n \sqrt n)$

---

二、完全背包（体积 $> S$）

考虑体积 $> S$ 的物品，其种类数仍然是 $O(n)$ 的，如果暴力做完全背包，复杂度为 $O(n^2)$，无法接受。

这里有一个非常巧妙的优化：

我们假设当前选了 $i$ 个物品，体积总和为 $j$，接下来有两种操作：

1. 新增一个物品，体积为 $S+1$；
2. 给当前所有物品的体积都加 $1$。

不难发现，所有的方案都可以通过这两种操作方式唯一得到。

也就是说，每次枚举 $i,j$，令：

$$g_{i+1,\ j+S+1} \ += \ g_{i,j}$$ $$g_{i,\ j+i} \ += \ g_{i,j}$$

由于最多只能选 $S$ 个物品（否则体积超过 $n$），所以这一部分的复杂度也是 $O(n\sqrt n)$。

---

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define SN 320
#define X 23333333
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
using namespace std;

int n, s;

int f[SN + 5][N + 5];

I void DP1() // 体积小于等于 S，多重背包
{
    RI i, j;
    for (f[0][0] = i = 1; i <= s; ++i)
    {
        for (j = 0; j <= n; ++j)
            f[i][j] = (f[i - 1][j] + (j >= i ? f[i][j - i] : 0)) % X; // 完全背包
        for (j = n; j >= (i + 1) * i; --j)
            Inc(f[i][j], X - f[i][j - (i + 1) * i]); // 减去不合法答案
    }
}

int g[SN + 5][N + 5], tot[N + 5];

I void DP2() // 体积大于 S，完全背包
{
    RI i, j;
    for (g[0][0] = 1, i = 0; i <= s; ++i)
        for (j = 0; j <= n; ++j)
        {
            Inc(tot[j], g[i][j]); // tot 统计答案
            if (j + s + 1 <= n) Inc(g[i + 1][j + s + 1], g[i][j]);
            if (j + i <= n) Inc(g[i][j + i], g[i][j]); // 两种转移
        }
}

int main()
{
    RI i, t = 0;
    scanf("%d", &n);
    s = sqrt(n);
    DP1();
    DP2();
    for (i = 0; i <= n; ++i)
        t = (1LL * f[s][i] * tot[n - i] + t) % X; // 扫一遍求答案
    printf("%d\n", t);
    return 0;
}

时间复杂度 $O(n \sqrt n)$ 空间复杂度 $O(n \sqrt n)$

题解2

思路

第 $i$ 种物品（有 $i$ 个、每个体积 $i$）的生成函数为：

$$1 + x^i + x^{2i} + \dots + x^{i\cdot i} = \frac{1 - x^{i(i+1)}}{1 - x^i}$$

总方案数的生成函数为：

$$F(x) = \prod_{i\ge 1} \frac{1 - x^{i(i+1)}}{1 - x^i} = \left(\prod_{i\ge 1} (1 - x^{i(i+1)})\right)\left(\prod_{i\ge 1} \frac{1}{1-x^i}\right)$$

• 第二项 $\prod \frac{1}{1-x^i}$ 是经典的整数划分生成函数，其系数 $p(n)$ 可用五边形数定理递推：

$$p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - \dots$$

其中 $1,2,5,7,12,15,\dots$ 是广义五边形数 $k(3k\pm1)/2$。

• 第一项 $\prod(1-x^{i(i+1)})$ 的系数 $g(j)$ 表示"选若干 $i(i+1)$ 的和为 $j$、符号为 $(-1)^{个数}$"，可用 0-1 背包（带符号）递推。由于 $i(i+1)\le n$ 意味着 $i\le\sqrt n$，只有 $O(\sqrt n)$ 项。

最终答案：

$$\text{ans} = \sum_{j=0}^{n} g(j)\cdot p(n-j) \pmod{23333333}$$

复杂度

$O(n\sqrt n)$，其中五边形数定理和 0-1 背包各 $O(n\sqrt n)$。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 23333333;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vector<int> p(n+1, 0), g(n+1, 0);

    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; ; k++) {
            int g1 = k*(3*k-1)/2, g2 = k*(3*k+1)/2;
            if (g1 > i && g2 > i) break;
            int sign = (k & 1) ? 1 : -1;
            if (g1 <= i) p[i] = (p[i] + sign * p[i-g1]) % MOD;
            if (g2 <= i) p[i] = (p[i] + sign * p[i-g2]) % MOD;
        }
        p[i] = (p[i] % MOD + MOD) % MOD;
    }

    g[0] = 1;
    for (int i = 1; (ll)i*(i+1) <= n; i++) {
        int d = i*(i+1);
        for (int j = n; j >= d; j--) g[j] = (g[j] - g[j-d]) % MOD;
    }
    for (int j = 0; j <= n; j++) g[j] = (g[j] % MOD + MOD) % MOD;

    ll ans = 0;
    for (int j = 0; j <= n; j++) ans = (ans + (ll)g[j]*p[n-j]) % MOD;
    cout << (ans % MOD + MOD) % MOD << '\n';
}