背包动态规划
flywen
·
·
算法·理论
Part0.前言
动态规划和背包问题是否也是你的噩梦呢？
鉴于我从学 oi 开始就不擅长喜欢动态规划，如今都以 NOIP 为目标，却连最基础的橙色动态规划题都没有思路，所以我决定从零开始学习动态规划。
当然是从最经典的背包动态规划开始啦！——2026.4
$\mathrm{upd}\hspace{0.25em}\mathrm{2026.5.17}$：修改格式。
$\mathrm{upd}\hspace{0.25em}\mathrm{2026.5.18}$：将较长代码块放到另一篇[专栏](https://www.luogu.com.cn/article/lozjxzeq)。
$\mathrm{upd}\hspace{0.25em}\mathrm{2026.5.28}$：勘误，感谢 [@Feynman5210](https://www.luogu.com.cn/user/1085788) 和 [@Deepsick](https://www.luogu.com.cn/user/2004018) 指出错误。按 [@xht_T](https://www.luogu.com.cn/user/1064974) 的推荐，将一道退背包加入拓展题推荐（这道题的题解是 TA 写的）。由于有很多人认为 [P15649 [省选联考 2026] 找寻者 / recollector](https://www.luogu.com.cn/problem/P15649) 不应该放在拓展题推荐中，故从中移除并加入题解。增加相关链接。
麻烦善良的管理员请通过一下。
---
### 什么是背包问题
我认为背包问题的格式如下：
* 有 $n$ 个物品，每个物品有价值 $v_i$ 和体积 $w_i$（或重量），甚至更多的属性，但主要围绕价值和代价计算。
* 选出一些物品最大化价值，即决策每个物品的选择系数 $x_i$。
* 使得总体积和不超过或恰好为 $W$，也可能存在别的约束条件。
比如 01 背包可以这样表示：选定 $x_i$ 为 $0$ 或 $1$，满足 $\sum\limits_{i=1}^nx_iw_i\leq W$，最大化 $\sum\limits_{i=1}^nx_iv_i$。
---
### 背包动态规划原理
关于背包动态规划其他的原理，如最优子结构、决策顺序等，在第一道例题 01 背包中有所提到。
通常默认背包动态规划的体积是整数，因为我们往往需要枚举体积。关于实数背包，不在主要考虑范围内，我只知道随机数据大概 $O(n2^{n/2})$ 的做法。
---
### 背包可加性
由于经常运用，就先说了。
背包动态规划带有天然的可加性。
每个物品都不依赖于过去选择什么，所以为每种物品都单独写一个处理函数即可，再依次调用。01 背包和完全背包新增一个物品是 $O(W)$ 的。
背包数组自身也带有可加性，如果有两个背包数组，那么可以 $O(W)$ 计算一种体积的最大价值。故可以 $O(W^2)$ 计算两背包数组合并后的新数组。
---
### 记号约定
我通常默认 $f_{i,j}$ 为决策完前 $i$ 个物品，占用代价为 $j$ 时的最大价值，$dp_{i,j}$ 表示方案。
通常不区分时间复杂度渐进上界和渐进紧确界。时间复杂度中为显示代码流程有时不省略低阶项。
通常不严格要求各类求和等记号格式。
通常所有记号都是整数，如果没有取整符号，默认取下整。
---
### 代码
本人代码风格一坨，就看个乐吧。
尽量保持和正文一样的变量名。
不重要的宏定义和快读都删了。我大多数不会给完整的主函数，会将部分不重要的输入和`int main()`删掉。
比较好写或是代码和之前的题差不多的代码就不给了。还有没有原题的题目或实现难度较高可能由于本人时间问题没有写代码。
---
### 参考文献
* luogu 题解
* GX 《信息学基础算法：追本溯源》中的背包动态规划部分
---
### 相关链接
* [题单链接](https://www.luogu.com.cn/training/1020292)
* [参考代码](https://www.luogu.com.cn/article/lozjxzeq)
# Part1.模板
*本板块主要介绍背包动态规划的各类模板，熟练掌握模板和各类变式能在解题过程中带来好处。*
## 01 背包
*本章节主要介绍 01 背包的模板及各类变式，提到区间 01 背包。*
---
### [P1048 [NOIP 2005 普及组] 采药](https://www.luogu.com.cn/problem/P1048)
$n$ 个物品，每个物品的价值为 $v_i$，体积为 $w_i$，数量为 $1$。背包体积为 $W$，最大化价值和。
$n,W\leq10^4$。
---
首先，存在**最优子结构**。
>全局最优方案中，如果任意局部方案不是最优的，替换为更优的后全局方案的价值会更高，与全局最优矛盾，故最优子结构成立。
决策顺序没有要求，故将输入顺序当做决策顺序。
朴素地，定义 $f_{i,j}$ 表示决策前 $i$ 件物品，所选物品体积**不超过** $j$ 的最大价值。
>注意这里写的是“不超过”，有的题目需要恰好体积为 $j$，此时将 $f$ 数组全部赋值为 $-\inf$ 并进行初始化即可。
考虑转移，分为选和不选，即：
$$f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-w_i}+v_i|j\geq w_i\}$$
边界 $f_{0,j}=f_{i,0}=0$。
答案为 $f_{n,W}$。
此时时间复杂度和空间复杂度都为 $O(nW)$，空间有点紧。
注意到每次决策 $i$ 转移只依赖于 $f_{i-1}$，故可以用滚动数组。更进一步，$f_{i,j}$ 依赖于 $f_{i-1,j-w_i}$，其中 $j-w_i\leq j$，故只依赖数组“左上方”的值，可以通过倒序枚举 $j$ 来利用上一行信息从而将数组压得只剩一维，空间复杂度 $O(W)$。
```cpp
for(int i = 1;i <= n;++i){
for(int j = W;j >= w[i];--j)f[j] = max(f[j],f[j - w[i]] + v[i]);
}
printf("%lld",f[W]);
```
---
### 低价 01 背包
$n\leq10^4,W\leq10^9,v\leq10^2$。
---
体积大，价值小，转化状态。
定义 $f_{i,j}$ 为决策前 $i$ 个物品，恰好获得 $j$ 收益，**至少**要占用的体积。
仍然决策第 $i$ 个物品是否选，得到转移方程：
$$f_{i,j}=\min\{f_{i-1,j},f_{i-1,j-v_i}+w_i|j\geq v_i\}$$
答案为 $\max\limits_{f_{n,j}\leq W}j$。
注意需要初始化为 $-\inf$。
时间复杂度 $O(nv)$。
---
### 少物品 01 背包
$n\leq40,W,v\leq10^{18}$。
---
值域和价值都已经无法枚举了，背包已经完全失效了。
不过......$40$ 这个数据范围让你想到什么了吗？
没错，**折半搜索**，这道题压根就不是背包。加这样一道题想表达的是，千万不要有思维定式（下一题也是）。
让 $n$ 是偶数，奇数加一个虚拟物品。假设前一半方案为 $a^{(v)}$ 和 $a^{(w)}$，后一半是 $b^{(v)}$ 和 $b^{(w)}$。
给一个循环写法：
```cpp
struct item{ long long w,v; }a[1<<21],b[1<<21];
bool cmp(item x,item y){ return x.w < y.w; }
int m = 1<<(n/2); //奇数就加一个虚拟物品
for(int i = 1;i <= n/2;++i){ //加入物品i和i+n/2
for(int j = 0;j < (1<<(i-1));++j){
a[j + (1<<(i-1))].w = a[j].w + w[i];
a[j + (1<<(i-1))].v = a[j].v + v[i];
b[j + (1<<(i-1))].w = b[j].w + w[i + n / 2];
b[j + (1<<(i-1))].v = b[j].v + v[i + n / 2];
}
}
```
那么答案为：
$$\max_{i=1}^{2^{n/2}}\{a^{(v)}_i+\max_{b^{(w)}_j\leq W-a^{(w)}_j}b^{(v)}_j\}$$
将 $j$ 按 $b^{(w)}_j$ 排序，然后前缀 $\max$ 优化内层 $\max$。时间复杂度 $O(n2^{n/2})$。
---
### 性价比 01 背包
$n$ 个物品，每个物品的价值为 $v_i$，体积为 $w_i$，数量为 $1$。背包至少要装 $W$ 体积物品，最大化性价比。
$n,w,W\leq2\times10^3,v\leq10^9$。
---
可能会想到二分答案（分数规划），因为性价比不具有最优子结构。
**性价比没有，但在体积固定时，价值有啊**。我们可以枚举体积，最大化价值。
定义状态 $f_{j}$ 为选体积和**恰好**为 $j$ 的物品的最大价值。根据之前所述，这就是01背包，我们知道如何转移和初始化。
然而我们还需要确定一下体积枚举的上限。如果选择体积大于 $W+w_i$，那么删去一个性价比最低的物品，肯定更优。所以最终体积枚举到 $2W$ 即可。
答案为 $\max\limits_{j=W}^{2W}{\frac{f_j}{j}}$。
时间复杂度 $O(nW)$，优于分数规划。
---
### 小物品 01 背包
$n\leq10^4,W\leq10^5,v\leq10^9,w\leq50$。
---
结论：最优解和贪心解至多相差 $2w$ 个物品。
证明：
>设贪心解 $S_1$ 总体积为 $W_1$，最优解 $S_2$ 总体积为 $W_2$，呢么 $W_2-w\leq W_1\leq W_2$。
>
>通过下列操作，总能使贪心解变为最优解。当使用体积小于等于 $W_2$ 时，增加一个在最优解中而不在贪心解中的物品；否则删除一个在贪心解中而不在最优解中的物品。
>
>该过程中体积始终在 $(W_2-w,W_2+w)$ 范围内，该范围只有 $2w-1$ 个值。根据**抽屉原理**，操作数大于等于 $2w$ 时，中途一定有两次体积相同，可以证明有一种操作方案次数更少的方案能使得总价值不变。
>
>证明：
>
>>设这两次方案先后是 $S_3,S_4$，体积 $W_3=W_4$。
>>
>>$S_3$ 到 $S_4$ 过程中性价比不可能变高，因为 $S_1$ 是总性价比最高的情况，而 $W_3=W_4$，则 $V_3\geq V_4$，即价值变小。
>>
>>不如直接使 $S_3$ 操作到 $S_2$，总价值不会变低。故操作数变少，而总价值不变。
>
>则操作至多 $2w$ 次。
具体地，先对体积 $2w^2$ 做含所有物品的背包，记录体积为 $0$ 到 $2w^2$ 的所有情况。枚举着 $2w^2$ 种情况，剩下的体积直接贪心。
>注意背包动态规划和贪心的顺序不能调换，因为不知道最优解与贪心解差的具体是哪 $2w^2$ 个物品。
时间复杂度 $O(nw^2+n\log n)$。
---
### [P6240 好吃的题目](https://www.luogu.com.cn/problem/P6240)
区间 01 背包，求一种体积的答案。
$n\leq4\times10^4,q\leq2\times10^5,W\leq2\times10^2$。
---
如果使用线段树维护背包数组，那么合并要 $O(W^2)$，会超时。
如果能把询问分成两个区间，左右两个区间背包数组分别为 $L$ 和 $R$，那么求 $\max\limits_{j=0}^W L_j+R_{W-j}$。现在合并复杂度是 $O(W)$ 了，不过要求要能找到这样两个区间。
所以使用可爱的猫树分治。
时间复杂度 $O(nW\log{n}+qW)$，空间复杂度 $O(nW)$。如果在线的话要把猫树存下来，空间再乘 $\log n$，这题有点紧。
## 完全背包
*本章节主要介绍完全背包的模板及各类变式，提到区间完全背包，广义矩阵快速幂优化完全背包和拆分数。*
---
### [P1616 疯狂的采药](https://www.luogu.com.cn/problem/P1616)/[P2722 [USACO3.1] 总分 Score Inflation](https://www.luogu.com.cn/problem/P2722)/[B2174 完全背包](https://www.luogu.com.cn/problem/B2174)
$n$ 个物品，每个物品的价值为 $v_i$，体积为 $w_i$，数量为 $\inf$。背包体积为 $W$，最大化价值和。
$n,W\leq10^4$。
---
和 01 背包无本质区别，先最暴力地去枚举每种物体装多少个。由于 $W$ 有限制，时间复杂度为 $O(nW^2)$。
对于每个 $f_{i,j}$ 想要去选 $k$ 个 $i$ 物品需要从 $f_{i-1,j - kw_i}$ 转移。然而如果我们按顺序遍历，先决策 $f_{i,j-(k-1)w_i}$，即选 $k-1$ 个该物品。此时如果再加上一个物品，也可以代替 $f_{i-1,j - kw_i}$ 对 $f_{i,j}$ 贡献。反复利用此结论，就不用枚举每种物体个数 $k$，得到转移方程：
$$f_{i,j}=\max\{f_{i-1,j},f_{i,j-w_i}+v_i|j\geq w_i\}$$
时间复杂度 $O(nW)$。
```cpp
for(int i = 1;i <= n;++i){
for(int j = w[i];j <=W;++j)f[j] = max(f[j],f[j - w[i]] + v[i]);
}
printf("%lld",f[W]);
```
---
### 小物品完全背包
$n,w\leq2\times10^3,W,v\leq10^{9}$。
---
#### 算法一：分治
因为对于两半体积，都需要是最优的，并且物品状态相同。
无脑必定会有问题，不能直接半切原问题。设当前体积为 $j$，考虑切割成体积 $\frac{j}{2}+k$ 和 $\frac{j}{2}-k$ 两部分，$0\leq k\leq \lceil\frac{w}{2}\rceil$，这样总能有一个分割情况能放下这个物品。
当 $j$ 远远大于 $w$ 时分治，再对每种情况求最值，即 $f_j=\max\limits_{k=0}^{\lceil w/2\rceil}\{f_{j/2+k},f_{j/2-k}\}$，否则直接dp。
时间复杂度 $O(nw+w^2\log W)$。
```cpp
long long f[N];
map<long long,long long>F;
long long solve(long long j){
if(j <= 2000)return f[j];
if(F.count(j))return F[j];
long long ans = 0;
for(int k = 0;k <= 1000;++k)ans = max(ans,solve(j / 2 - k) + solve(j / 2 + k));
F[j] = ans;
return ans;
}
for(int i = 1;i <= n;++i){
int w = in(),v = in();
for(int j = w;j <= 2000;++j)f[j] = max(f[j],f[j - w] + v);
}
printf("%lld",solve(W));
```
#### 算法二：矩阵快速幂
完全背包广义矩阵快速幂优化是算法一的原理，时间复杂度也是 $O(w^2\log W)$。
本人数学太差，但这个原理还挺简单的。网上资料似乎很少，只找到[这篇](https://www.cnblogs.com/JY-Chen/p/11378862.html)，有兴趣可以了解一下。
---
### [P5455 [THUPC 2018] 弗雷兹的玩具商店](https://www.luogu.com.cn/problem/P5455)
区间完全背包，求所有体积的答案。
$n\leq2\times10^5,q\leq3\times10^4,W\leq60$。
---
小容量的完全背包经常出现，容易发现实际上只有 $W$ 种物品会选，因为**同样体积的物品只用保留价值最大的**。所以只要快速找出这 $W$ 个物品就能够在 $O(W^2)$ 时间内完成一次完全背包。
直接使用可爱的线段树，让她维护每个体积的最高价值即可。
时间复杂度 $O(nW\log n+qW\log n+qW^2)$。
---
### [P6189 [NOI Online #1 入门组] 跑步](https://www.luogu.com.cn/problem/P6189)/[P1025 [NOIP 2001 提高组] 数的划分](https://www.luogu.com.cn/problem/P1025)/[P10955 正整数拆分](https://www.luogu.com.cn/problem/P10955)
给出正整数 $n$，询问将其分为若干正整数之和的方案数。
$n\leq10^5$。
---
#### 算法一：完全背包
把正整数 $i$ 当成 $i$ 代价物品，就变成完全背包计数。
定义状态 $f_{i,j}$ 为使用小于等于 $i$ 的数和**恰好**为 $j$ 的方案数。
$$f_{i,j}=f_{i-1,j}+f_{i,j-i}[j\geq i]$$
时间复杂度 $O(n^2)$。
考虑**根号分治**，令大于 $D$ 的数为大物品，小于等于的数为小物品。假设小物品和大物品选出和为 $x$ 的方案数分别是 $S_j=f_{D,j}$ 和 $B_j$，答案为 $\sum\limits_{j=0}^n S_jB_{n-j}$。
对于小物品直接完全背包，时间复杂度 $O(nD)$。
对于大物品至多只有 $\frac{n}{D}$ 个物品和为 $n$，故定义状态 $g_{i,j}$ 为 $i$ **个**大物品和为 $j$ 的方案数，则 $B_j=\sum\limits_{i=0}^{n/D}g_{i,j}$。
由于不知道现在选的大物品代价，考虑将所有大物品代价平移使得现在的大物品代价为 $D+1$，那么转移如下：
$$g_{i,j}=g_{i-1,j-D-1}+g_{i,j-i}$$
故大物品复杂度为 $O(\frac{n^2}{D})$。
综上，$D$ 取 $n^{1/2}$ 时最优，总复杂度为 $O(n^{3/2})$。
#### 算法二：五边形数定理
此外还一种复杂度相同的方法，只不过和背包没有关系。我太菜了，想了解的去看StudyingFather的[文章](https://www.luogu.com.cn/article/rejrmdfv)。
## 多重背包
*本章节主要介绍多重背包的两种写法，二进制拆分和单调队列。*
---
### [B2173 多重背包](https://www.luogu.com.cn/problem/B2173)/[P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776)
$n$ 个物品，每个物品的价值为 $v_i$，体积为 $w_i$，数量为 $c_i$。背包体积为 $W$，最大化价值和。
$n,W\leq10^4$。
---
如果直接枚举选择几个物品的话，是和完全背包的暴力相差不大的。有两种优化方法，二进制拆分和单调队列。
#### 算法一：二进制拆分
考虑将 $c_i$ 分解成 $m$ 个只能取一次的物品，其中第 $k$ 个新物品视作选择了 $p_k$ 个 $i$ 物品，并且通过选这些物品能凑出 $0$ 到 $c_i$ 中所有的数量。为时间复杂度更优，$m$ 还要尽量小。
>即对于新的每个物品 $k$ 给一个选不选的系数 $x_k$ 为 $0$ 或 $1$，要求 $\sum\limits_{k=1}^mx_kp_k$ 对于所有可能的 $x$ 能够取到 $0$ 到 $c_i$ 中所有的数。
能够想到二进制拆分，设 $l=\log c_i$ 并向下取整。具体地将 $c_i$ 拆分成 $l+1$ 个新物品，其中前 $l$ 个中第 $k$ 个 $p_k=2^k$，第 $l+1$ 个为剩余的，即 $c_i-2^l$。
正确性显然。时间复杂度 $O(nW\log c)$。
```cpp
for(int i = 1;i <= n;++i){
int rw = in(),rv = in(),rc = in();
for(int j = 1;j <= rc;j<<=1){
w[++cnt] = j * rw;
v[cnt] = j * rv;
rc -= j;
}
if(rc){
w[++cnt] = rc * rw;
v[cnt] = rc * rv;
}
}
```
#### 算法二：单调队列
NOIP 范围内似乎不考察单调队列优化动态规划，但是仍然有先例存在，比如 [P5665 [CSP-S 2019] 划分](https://www.luogu.com.cn/problem/P5665)。反正这个也不难，看看也没有坏处，但是写起来更复杂，我不会。
注意到暴力的话，每个 $f_j$ 从 $f_{j-kw_i}+kv_i$ 转移过来，故其依赖的所有 $f$ 的下标都与 $j$ 是模 $w_i$ 的同余类，证明显然。做题的时候要注意一下 $w_i$ 为 $0$ 的情况。
那么对于每个同余类，我们可以使用单调队列快速地去进行决策。具体地，将转移方程变形，使得我们能从当前体积 $j$ 查询向前 $c_i$ 个中最大的：
$$f_j=\max\limits_{k= \lfloor j/w_i \rfloor-c_i}^{\lfloor j/w_i \rfloor}\{f_{(j\mod w_i) + kw_i}-kv_i\}+\lfloor\frac{j}{w_i} \rfloor v_i$$
然而实现上一般不会枚举 $j$，而是枚举 $j\mod w_i$，即余数。这样能避免同时使用多个单调队列，节约空间。
由于每个 $f_j$ 至多出入队一次，所以时间复杂度是 $O(nW)$。
```cpp
int v = in(),w = in(),c = in();
c = min(c,W / w);
for(int d = 0;d < w;++d){ //d = j mod w
int l = 1,r = 0;
for(int k = 0;k <= (W - d) / w;++k){
while(l <= r && f[d + k * w] - k * v >= val[r])--r;
q[++r] = k;
val[r] = f[d + k * w] - k * v;
while(l < r && q[l] < k - c)++l;
f[d + k * w] = max(f[d + k * w],val[l] + k * v);
}
}
```
## 多维背包
*本章节主要介绍多维背包，即广义资源。*
---
### [P1507 NASA的食物计划](https://www.luogu.com.cn/problem/P1507)/[P1794 装备运输](https://www.luogu.com.cn/problem/P1794)
$n$ 个物品，每个物品的价值为 $v_i$，体积为 $w_i$，质量为 $m_i$，数量为 $1$。背包体积为 $W$，质量上限为 $M$，最大化价值和。
$n,W,M\leq10^2$。
---
多枚举一维就行。
时间复杂度 $O(nWM)$。如果有 $k$ 维的话，每维上限为 $W_i$ 就是 $O(n\prod\limits_{i=1}^k W_i)$。
```cpp
for(int i = 1;i <= n;++i){
int w = in(),m = in(),v = in();
for(int j = W;j >= w;--j){
for(int k = M;k >= m;--k)f[j][k] = max(f[j][k],f[j - w][k - m] + v);
}
}
printf("%d",f[W][M]);
```
---
### [P2732 [USACO3.3] 商店购物 Shopping Offer](https://www.luogu.com.cn/problem/P2732)
$n$ 个物品，第 $i$ 个需要买 $t_i$ 个，单价为 $w_i$。有 $m$ 个促销方案，第 $j$ 种需要买 $c_{j,i}$ 种 $i$ 物品，只需要花费 $p_j$ 元。保证促销方案优于直接买，即 $\sum\limits_{i=1}^{n}c_{j,i}w_i\geq p_j$。
$n,t\leq5,m\leq100$。
---
将每个物体单买和促销方案处理成同一种物体，$c$ 为其收益，$w$ 和 $p$ 为代价。即当收益确定时求最小代价。
由于 $n\leq5$，写一个五维dp做完全背包即可。时间复杂度 $O(nmt^n)$。
## 分组背包
*本章节主要介绍分组背包，并引出依赖性背包。*
---
### [P1757 通天之分组背包](https://www.luogu.com.cn/problem/P1757)
$n$ 个物品，每个物品的价值为 $v_i$，体积为 $w_i$，数量为 $1$，组别为 $c_i$，**每组的物品至多只能选一个**。背包体积为 $W$，最大化价值和。
$n,W\leq10^3,c\leq10^2$。
---
直接**在枚举完体积后**去暴力枚举每组中选哪个物品。
>注意必须先枚举体积，再枚举组中物品。顺序不能调换，不然会出现同时选同组物品的情况。
时间复杂度 $O(nWc)$。
```cpp
for(int i = 1;i <= n;i++){
w[i] = in(),v[i] = in(),x = in();
k = max(k,x);
s[x]++;
g[x][s[x]] = i;
}
for(int i = 1;i <= k;i++){
for(int j = W;j >= 0;j--){
for(int k = 1;k <= s[i];k++){
if(j >= w[g[i][k]])f[j] = max(f[j],f[j - w[g[i][k]]] + v[g[i][k]]);
}
}
}
printf("%lld",f[W]);
```
---
### [P3961 [TJOI2013] 黄金矿工](https://www.luogu.com.cn/problem/P3961)
$n$ 个点，第 $i$ 个点价值为 $v_i$，体积为 $w_i$。如果几个点分别与 $(0,0)$ 连接的直线相同，选与原点更远的点必须选所有在该直线上比它里原点更近的点。背包体积为 $W$，最大化价值和。
$n\leq10^2,W\leq4\times10^4$。
---
如果依赖关系是一条链或者可以分较少情况（[P1064 [NOIP 2006 提高组] 金明的预算方案](https://www.luogu.com.cn/problem/P1064)）可以转化为分组背包，至于其他依赖情况详见下一张。
对于一条直线上的点，转化为决策离原点最远点，价值为比它里原点近的所有点的价值和，体积也是体积和。相当于排序之后前缀和。
时间复杂度 $O(nW+n\log n)$。
## 依赖性背包
*本章节主要介绍依赖性背包，上一个章节讲解依赖关系是链的情况，本章侧重于依赖关系是更复杂的图的情况。*
---
### [P2967 [USACO09DEC] Video Game Troubles G](https://www.luogu.com.cn/problem/P2967)/[P1064 [NOIP 2006 提高组] 金明的预算方案](https://www.luogu.com.cn/problem/P1064)
$n$ 台游戏机，每台需要 $p_i$ 价格解锁。每台游戏机有 $g_i$ 款游戏，每台游戏机解锁后可以再用 $v_j$ 价格去买这台游戏机中的 $j$ 号游戏，价值为 $w_j$。
$n\leq50,g_i\leq10,W\leq10^3$。
---
只有两层的树形背包。
对于每台游戏机来说，简单的 01 背包。
对于总的来说，代价 $w$ 只能在游戏机 $i$ 中买到该游戏机背包中 $w-p_i$ 价格的价值。
故dp套dp，处理每个游戏机。时间复杂度 $O(ngW)$。
```cpp
for(int i = 1;i <= n;++i){
for(int j = 0;j <= W;++j)f[j] = dp[j];
int p = in(),g = in();
for(int j = 1;j <= g;++j){
int w = in(),v = in();
for(int k = W;k >= w;--k)f[k] = max(f[k],f[k - w] + v);
}
for(int j = p;j <= W;++j)dp[j] = max(dp[j],f[j - p]);
}
printf("%d",dp[W]);
```
---
### [P2014 [CTSC1997] 选课](https://www.luogu.com.cn/problem/P2014)
$n$ 个物品，每个物品的价值为 $v_i$，体积为 $1$，数量为 $1$，选该物品的前提条件是选物品 $p_i$。背包体积为 $W$，最大化价值和。
**保证前提条件无冲突**。
$n,W\leq3\times10^2$。
---
如果新加一个虚拟点，题目给出的约束条件是一颗树。
定义 $f_{u,i,j}$ 为节点 $u$ 前 $i$ 个子节点总重不超过 $j$ 的最大价值。$i$ 这维依然可以压掉。
对于节点 $u$，依次遍历每个子节点，进行背包。时间复杂度 $O(nW^2)$。但实际上，上述代码经过优化复杂度为 $O(nW)$，详见这篇[题解](https://www.luogu.com.cn/article/3z2tovfz)。
```
int f[N][N]; //f[u][v] = 节点u代价为v,不选自己的最大价值
void dfs(int u,int fa){
for(int i = 0;i < e[u].size();++i){
int v = e[u][i];
if(v != fa){
dfs(v,u);
for(int j = W;j;--j){
for(int k = 0;k < j;++k)f[u][j] = max(f[u][j],f[u][k] + f[v][j - k - 1] + val[v]);
}
}
}
}
dfs(0,0);
printf("%d",f[0][W]);
```
参考上一题的思路，我们还能做到更直观的 $O(nW)$。
```cpp
void dfs(int u,int fa){
for(int i = 0;i < e[u].size();++i){
int v = e[u][i];
if(v != fa){
for(int j = W;j >= 0;--j)f[v][j] = f[u][j] + val[v];
dfs(v,u);
for(int j = W;j;--j)f[u][j] = max(f[u][j],f[v][j - 1]);
}
}
}
```
---
### [P2515 [HAOI2010] 软件安装](https://www.luogu.com.cn/problem/P2515)
$n$ 个物品，每个物品，体积为 $w_i$，数量为 $1$，选该物品提供价值 $v_i$ 的前提条件是选物品 $p_i$。背包体积为 $W$，最大化价值和。
$n\leq10^2,W\leq5\times10^2$。
---
相较于上题，本题不保证约束条件是一棵树。不过这无伤大雅，对于一个环，要么全选，要么全都不选。所以缩点后就变成上一道题。
## 动态背包
*本章节主要介绍动态背包，提到几种常用的优化思路。线段树分治是平凡的动态背包的最优解。*
---
### [P5391 [Cnoi2019] 青染之心](https://www.luogu.com.cn/problem/P5391)
$q$ 次操作，要么加入一个价值为 $v_i$，体积为 $w_i$，数量为 $\inf$ 的物品，要么删除上一次加入的物品，即后进先出（栈）。背包体积为 $W$，最大化价值和。
$q,W\leq2\times10^4$。
---
#### 算法一：乱搞
如果是撤销操作，暴力重新做一遍背包，时间复杂度 $O(q^2W)$，喜提 TLE。但是数据很水，优化之后能过，参考这篇[题解](https://www.luogu.com.cn/article/a46uzp4s)。
#### 算法二：树剖
动态背包最朴素地，直接存下来每次的背包数组。时间复杂度 $O(qW)$，空间复杂度 $O(qW)$，喜提 MLE，考虑优化空间。
离线下来整个过程是一棵树，求每个点到根节点上所有物品的背包。
考虑只给**当前节点往上的路径**每个点开背包数组，但如果是链还是 MLE，所以再上一个重链剖分。综上，给当前节点往上的路径每条**重链**开一个背包数组。
注意之前使用过的应当回收，参考这篇[题解](https://www.luogu.com.cn/article/2jc7twiv)。因为每个点到根节点至多过 $\log q$ 条重链，所以同时至多使用 $\log q$ 个背包数组。应该先遍历轻儿子，后遍历重儿子，因为重儿子和父节点用的一个背包数组。
时间复杂度 $O(qW)$，空间复杂度 $O(W\log q)$。
---
### 过期动态 01 背包
$q$ 次操作，要么加入一个价值为 $v_i$，体积为 $w_i$，数量为 $1$ 的物品，要么删除还没被删除最先加入的物品，即先进先出（队列）。背包体积为 $W$，最大化价值和。
$q,W\leq8\times10^3$。
---
假设有一个分割点 $mid$，向左延伸的数组为 $L$，向右延伸的数组为 $R$。
当加入物品时增加 $R$：
```cpp
rgt++;
w[rgt] = in(),v[rgt] = in();
for(int j = W;j >= 0;++j)R[rgt][j] = R[rgt - 1][j];
for(int j = W;j >= w[rgt];++j)R[rgt][j] = max(R[rgt][j],R[rgt][j - w[rgt]] + v[rgt]);
```
删除时缩短 $L$，当 $L$ 为空时，从目前最新的物品 $rgt$ 开始倒退重新计算 $L$，将 $mid$ 改为 $rgt$：
```cpp
if(++lft > mid){
for(int i = rgt - 1;i >= lft;--i){
for(int j = 0;j <= W;++j)L[i][j] = L[i + 1][j];
for(int j = W;j >= w[i];--j)L[i][j] = max(L[i][j],L[i][j - w[i]] + v[i]);
}
mid = rgt;
for(int j = 0;j <= W;++j)R[rgt][j] = 0; //清空R
}
```
答案：
```cpp
int ans = 0;
for(int j = 0;j <= W;++j)ans = max(ans,L[lft][j] +R[rgt][W - j]);
printf("%d\n",ans);
```
时间复杂度 $O(qW)$。
---
### [P4141 消失之物](https://www.luogu.com.cn/problem/P4141)
$n$ 个物品，每个物品体积为 $w_i$，数量为 $1$。背包体积为 $W$。对于每个物品求不使用该物品凑出每种小于等于 $W$ 体积的方案数，对 $10$ 取模。
$n,W\leq2\times10^3$。
---
这题并不是动态背包，只是为下一题做铺垫。
背包没有可减性是因为取最大值，但计数器是求和，所以可以直接减。
显然需要使用 $n$ 个物品的背包数组去计算 $n-1$ 个物品背包数组。考虑去掉一种物品,会对结果有什么影响。
如果少物品 $i$，对 $dp_j$ 来说，少一个从 $dp_{j-w_i}$ 的贡献，注意这里的 $dp_{j-w_i}$ 是不使用物品 $i$ 的。故从小到大将背包数组 $dp_j$ 更新为 $dp_j - dp_{j-w_i}$。
时间复杂度 $O(nW)$。
```cpp
t[0] = dp[0] = 1;
for(int i = 1;i <= n;++i){
for(int j = m;j >= w[i];--j)dp[j] += dp[j - w[i]],dp[j] %= 10;
}
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
t[j] = dp[j];
if(j >= w[i]){
t[j] -= t[j - w[i]];
t[j] = (t[j] + 10) % 10;
printf("%lld",t[j]);
}
else printf("%lld",dp[j]);
}
printf("\n");
}
```
---
### 随机增删动态背包
$q$ 次操作，要么加入一个价值为 $v_i$，体积为 $w_i$，数量为 $1$ 的物品，要么删除任意一个加入的物品。
**Q1**：求能否恰好装满背包体积 $W$。
**Q2**：求背包体积为 $W$ 时最大价值。
$q,W\leq2\times10^3$。
---
#### Q1
可行性没有可减性，不过可以**升格**，维护方案数。
参考上一题的方法，我们可以在 $O(W)$ 的复杂度内增删一个物品。
还有一个小问题就是方案数可能爆 long long，所以需要取模，可能会有微小误判，但可以忽略。
时间复杂度 $O(qW)$。
#### Q2
回顾本章节的所有题，都是在增删物品上有些特殊性质，**避免合并背包，利用物品可加性**，然而现在删除的物品是任意的，我们已经没有任何性质可以利用。那现在该怎么办？
**线段树分治！**
线段树分治不是数据结构，而是一种思想。将每一个时间视作线段树的一个叶节点，那么每个物品有加入和删除时间，它的存在就会变成一个区间，拆到线段树上为 $2\log q$ 个节点上。
进行从左到右的遍历，维护当前节点到根节点路径上这 $\log q$ 个节点的背包数组。来到新节点时加上该节点的物品，到叶节点输出，回退时释放节点内存。
>教练曾说过：“线段树分治看似是离线做法，实际上是半在线的，因为遍历顺序是按时间顺序的，可以边回答问询边往打标记。”~~不过代码实现难度很高。~~
时间复杂度是 $O(qW\log q)$，空间复杂度 $O(q\log q+ W\log q)$，可以解决几乎所有的动态背包问题。
## 同余最短路
*本章节主要介绍同余最短路，不太确定这玩意适不适合放在背包板块，但背包也属于线性代数嘛。同余最短路是一种将动态规划转换为图论问题的优化。*
---
### [P2371 [国家集训队] 墨墨的等式](https://www.luogu.com.cn/problem/P2371)
$n$ 个物品，每个物品的体积为 $w_i$，数量为 $\inf$。求区间 $[l,r]$ 中有多少体积能**恰好**被这 $n$ 个物品凑出来。
$n\leq12,0\leq w\leq5\times10^5,1\leq l\leq r\leq10^{12}$。
---
无脑完全背包，$f_j=f_j|f_{j-a_i}[j\geq a_i]$，$l,r$ 太大了，挂。
通常对于这种题目考虑计算 $[0,l-1]$ 和 $[0,r]$ 的答案，然后做减法。考虑现在求 $[0,v]$ 的答案。
假设 $m$ 是 $a_i$ 中的一个数，那么当 $\sum\limits_{i=1}^{n}{a_ix_i} = s$ 时，则 $s+km$ 都能取到，其中 $k$ 是自然数。
注意到当 $s$ 最小时，该情况对答案的贡献最大，即最完全，就可以用对 $m$ 取模的一个 $s$ 计算它的同余类。定义 $f_{s \mod m}$ 为 $s$ 的最小答案。
考虑连边 $u\rightarrow(u+a_i)\mod m$，边权为 $a_i$，那么 $0$ 到 $u$ 的最短路就是 $f_u$。对于每个 $u$，$k$ 的个数为 $\lfloor\frac{v-f_u}{m}\rfloor+1$。这被称为**同余最短路**。
$m$ 可以取 $\min\limits_{i=1}^na_i$，因为总点数为 $m+1$，取最小的可以让点数最少。
记 SPFA 复杂度为 $\mathrm {SPFA}(点数,边数)$，则使用 SPFA 时间复杂度 $O(\mathrm {SPFA}(a,na))$，因为图比较特殊能过。
---
### [P9140 [THUPC 2023 初赛] 背包](https://www.luogu.com.cn/problem/P9140)
$n$ 个物品，每个物品的价值为 $v_i$，体积为 $w_i$，数量为 $\inf$。求所求物品体积**恰好**为 $W$ 时最大化价值和，多组问询 $W$。
$n\leq50,10^{11}\leq W\leq10^{12}$。
---
大体积背包依然先贪心。令 $k$ 为性价比最高的物品，即 $\frac{v_i}{w_i}$ 最大，那么对于体积等于 $w_k$ 倍数的物品组合，都应该替换成物品 $k$。
假设物品可以分割，那么理想答案为 $\frac{W}{w_k}\times v_k$。考虑最小化实际情况和理想情况的差值：
$$\Delta=\frac{W}{w_k} \times v_k - V=\frac{v_k}{w_k} \sum_{i=1}^n x_i w_i - \sum_{i=1}^n x_i v_i\\=\frac{1}{w_k}\sum_{i=1}^n x_i \left(v_k w_i - v_i w_k \right)$$
令 $wgt_i = w_k v_i - w_i v_k$。由于物品 $1$ 性价比最大，故 $wgt_i \ge 0$。
现在就变成物品 $i$ 代价为 $wgt_i$，求最小代价。
发现 $wgt_k=0$，故定义 $f_j$ 为达到体积 $W'\equiv j\mod w_k$，转移：
$$f_{(j+w_i)\mod w_k}=\min\{f_{(j+w_i)\mod w_k},f_j+wgt_i\}$$
同余最短路解决，使用 Dijkstra 时间复杂度 $O(nv\log v)$。
答案为 $\frac{W\times v_k-f_{W\mod w_k}}{w_k}$，条件是 $W'\leq W$，这恒成立。
证明：
>同余最短路不会重复经过任何一点，因为中间这段路径可以换成 $k$ 物品，代价为 $0$，更优。故 $W'\leq\sum\limits_{i=1}^nv_i\leq W$。
# Part2.背包建模
*本板块主要讲解背包动态规划题目，按题目编号排序，难度主要提高及以上。*
---
### [P1285 [NEERC 2001] 队员分组](https://www.luogu.com.cn/problem/P1285)/[P2175 小Z的游戏分队](https://www.luogu.com.cn/problem/P2175)
每个同学信任另一些同学。如果两个同学在一组，他们必须互相信任。判断能否分成两组，最小化两组人数差。
$n\leq2\times10^3$。
---
按不信任关系建图，用`dfs`二分图染色求出每个连通块两种颜色计数 $sz_{i,0/1}$。
定义 $f_{i,j}$ 为可否在前 $i$ 的连通块中染色使得两组差恰好为 $j$。
>由于这里染色的连通块大小差有正负性，染色过程又有顺序，所以这里的 $j$ 应该是从 $-n$ 到 $n$。不然就像我一样 P1285 只有 $99$ 分。
时间复杂度 $O(n^2)$。
P1285 要求输出实际上的分组，所以我们需要记录转移时该连通块被分到哪组，通过倒推的方式得到分组结果。
---
### [P1858 多人背包](https://www.luogu.com.cn/problem/P1858)
求 01 背包占用体积**恰好**为 $W$ 的前 $k$ 优解之和。
$n,k\leq10^2,W\leq10^4$。
---
$f_{i,j,k}$ 表示决策前 $i$ 项物品，恰好体积为 $j$ 的前 $k$ 优解。
注意，$k$ 很小，直接在转移时暴力更新即可。具体地，$f_{i,j}$ 的第 $k$ 优解要么是 $f_{i-1,j}$，要么是 $f_{i-1,j-w_i}+v_i$。
时间复杂度 $O(nkW)$。
```cpp
long long t[K];
long long f[N][K];
for(int j = 0;j <= W;++j){
for(int kth = 1;kth <= k;++kth)f[j][kth] = -inf;
}
f[0][1] = 0;
for(int i = 1;i <= n;++i){
w[i] = in(),v[i] = in();
for(int j = W;j >= w[i];--j){
int len = 0;
int cur = 1,lst = 1;
while(len < k){
if(f[j][cur] > f[j - w[i]][lst] + v[i])t[++len] = f[j][cur++];
else t[++len] = f[j - w[i]][lst++] + v[i];
}
for(int kth = 1;kth <= k;++kth)f[j][kth] = t[kth];
}
}
for(int kth = 1;kth <= k;++kth)ans += f[W][kth];
printf("%lld",ans);
```
---
### [P1860 新魔法药水](https://www.luogu.com.cn/problem/P1860)
$n$ 种药水，每种有售价和回收价。开始使用 $W$ 元随意购买一些药水。可以使用 $k$ 次 $m$ 种魔法中的一种，可以将**一些药水**合成**一种药水**。最大化最后收益，注意后面赚的钱不能再去买药水。
$k\leq30,n\leq60,m\leq240,W\leq10^3$。
---
令 $f_{v,t}$ 为花 $v$ 元使用 $t$ 次魔法的最大收益。
发现我们不知道使用 $t$ 次魔法获得药水 $i$ 的最小花费，故设其为 $g_{i,t}$。
为计算 $g$，对于每个配方，求出将 $t$ 次魔法分配给**配方中**前 $j$ 种原材料的最小花费 $h_{j,t}$。
时间复杂度 $O(nmk^3+nWk^2)$。
---
### [P1987 摇钱树](https://www.luogu.com.cn/problem/P1987)
$n$ 个物品，**依次**选择其中 $k$ 个，第 $j$ 个选择的第 $i$ 个物品物品价值为 $\max\{0,m_i-b_i\times j\}$，最大化价值和。
$n,k\leq10^3$。
---
这题决策顺序有影响，但注意到肯定是 $b_i$ 小的先选，大的后选。
证明如下：
>邻项交换，如果有两个不是 $b_i$ 小的先选，将两者选的顺序调换结果必定更优。
故对 $b$ 排序，然后做标准的01背包。但是注意最后答案不是 $f_{n,k}$，因为前面有些物品不如不选，所以答案应该是 $\max\limits_{i=1}^k f_{n,i}$。
时间复杂度 $O(nk+n\log n)$。
---
### [P2224 [HNOI2001] 产品加工](https://www.luogu.com.cn/problem/P2224)
$n$ 个任务，第 $i$ 个任务可以给 A 机器做，用时 $t_{i,1}$；给 B 机器做，用时 $t_{i,2}$；给 A 机器和 B 机器同时做，用时 $t_{i,3}$；求最小用时。$t=0$ 表示不能给这个机器或这两个机器做。
$n\leq6\times10^3,t\leq5$。
---
设 $f_{i,j,k}$ 为第 $i$ 个任务时，A 机器连续做了 $j$ 时间，B 机器连续做了 $k$ 个时间，是否合法。
由于第一维可以滚掉，空间复杂度为 $O(n^2t^2)$，考虑降维，设 $f_{i,j}$ 为第 $i$ 个任务时，A 机器连续做了 $j$ 时间，B 机器最少连续做了多少时间。如此以来空间复杂为 $O(nt)$。
考虑转移：
* A 机器做：$f_{i-1,j-t_{i,1}}$；
* B 机器做：$f_{i-1,j}+t_{i,2}$；
* AB 一起做：$f_{i-1,j-t_{i,3}}+t_{i,3}$。
初始化 $f_{i,j}=-\inf,f_{0,0}=0$。
但这题还卡时间，只需要将 $j$ 从 $nt$ 枚举到 $0$ 改成 $\sum\limits_{k=1}^i \max\{t_{k,1},t_{k,3}\}$。
答案为 $\min\limits_{j=1}^{\sum\limits_{k=1}^n \max\{t_{k,1},t_{k,3}\}}\max\{j,f_{n,j}\}$。
时间复杂度 $O(n^2t)$。
```cpp
memset(f,0x3f,sizeof(f));
int inf = f[0];
f[0] = 0;
for(int i = 1;i <= n;++i){
int t1 = in(),t2 = in(),t3 = in();
s += max(t1,t3);
for(int j = s;j >= 0;--j){
int a,b,c;
a = b = c = inf;
if(t1 && j >= t1)a = f[j - t1];
if(t2)b = f[j] + t2;
if(t3 && j >= t3)c = f[j - t3] + t3;
f[j] = min(min(a,b),c);
}
}
int ans = inf;
for(int i = 1;i <= s;++i)ans = min(ans,max(i,f[i]));
printf("%lld",ans);
```
---
### [P2851 [USACO06DEC] The Fewest Coins](https://www.luogu.com.cn/problem/P2851)
$n$ 个硬币，第 $i$ 个价值为 $v_i$，买家有 $c_i$ 个，卖家有无限个。求最小的硬币总数，使得买家的金额比卖家的金额多 $T$ 元（支付 $T$ 元）。**无解输出 $-1$**。
$n,v\leq10^2,c,T\leq10^4$。
---
买家是多重背包 $f1$，卖家是完全背包 $f2$。
如果我们找到枚举上界 $T+m$，最终答案为
$$\min\limits_{i=t}^{T+m}f1_i+f2_{i-m}$$
如果嫌麻烦，直接枚举到超时之前也行。不过可以说明最大上界是 $m=v_{max}^2$，即最大面值钞票的平方。
证明如下：
>对一个选取 $i\geq v_{max}^2 + 1$ 的方案中求 $v$ 前缀和，$s_0=0,s_1$ 到 $s_k$ 至少 $v_{max} + 1$ 个数。那么根据抽屉原理，至少有两个 $s$ 模 $v_{max}$ 同余。将该部分替换成 $v_{max}$ 面值硬币硬币数一定减少，说明这种情况的方案不是最优的。
时间复杂度 $O((T+v^2)n\log c)$。
---
### [P3891 [GDOI2014] 采集资源](https://www.luogu.com.cn/problem/P3891)
$n$ 个单位类型，每个单位有价格 $w_i$ 和效率 $p_i$。现在有 $m$ 金额，求达到 $T$ 价值的最少时间。
$n\leq10^2,m,T\leq10^3$。
---
定义 $f_{t,i}$ 为时间 $t$ 时生产的单位效率和为 $i$ 时的最大价值。
则求最小的 $t$ 满足 $f_{t,i}\geq T$。
转移是模拟时间流逝：$f_{t+1,i}=f_{t,i}+i$。
以及购买一种单位：$f_{t,i}=\max\limits_{j=1}^n\{f_{t,i-p_j}-w_j|i\geq p_j\}$。
时间复杂度 $O(nmT)$。
---
### [P4095 [HEOI2013] Eden 的新背包问题](https://www.luogu.com.cn/problem/P4095)
$n$ 个物品，每个物品价值为 $v_i$，体积为 $w_i$，数量为 $c_i$。$q$ 次问询在不使用 $d_t$ 号物品情况下背包体积为 $W_t$ 的最大价值。
$n\leq10^3,q\leq3\times10^5,W\leq10^3$。
---
如果是**只删某一段区间物品**，可以转化为前缀背包数组和后缀背包数组相合并。
时间复杂度 $O(nW\log n + qW)$。
---
### [P5662 [CSP-J 2019] 纪念品](https://www.luogu.com.cn/problem/P5662)
$t$ 天中第 $d$ 天，$n$ 个物品中的第 $i$ 个价值为 $p_{i,d}$，可以在任意时刻买入或卖出任意物品，最后一天结束卖出所有物品。初始有 $m$ 元，最大化最终收益。
保证任意时刻手中至多持有 $W=10^4$ 元。
$n,t\leq10^2,m\leq10^3$。
---
如果要把一个物品买入，留一段时间再买，可以视作第一天买入，每天卖出后再买入，最后一天不再买入。
当天持有钱视作容量，第 $d$ 天物品 $i$ 体积为 $p_{i,d}$，价值为 $p_{i,d+1}-p_{i,d}$。做 $t-1$ 次完全背包即可，每次做完将持有钱 $m$ 加上 $f_m$。
时间复杂度 $O(ntW)$。
```cpp
for(int k = 1;k < t;++k){
for(int j = 0;j <= m;++j)f[j] = 0;
for(int i = 1;i <= n;++i){
for(int j = p[i][k];j <= m;++j)f[j] = max(f[j],f[j - p[i][k]] + p[i][k + 1] - p[i][k]);
}
m += f[m];
}
printf("%d",m);
```
---
### [P7432 [THUPC 2017] 钦妹的玩具商店](https://www.luogu.com.cn/problem/P7432)
区间禁用多重背包，求所有体积的答案，强制在线。
$n,c,W\leq10^3$。
---
求所有体积的答案所以不能合并数组，在线所以猫树分治实现不了，只能使用分块。
设块长为 $B$。
预处理不使用块 $[L,R]$ 的背包数组 $f_{L,R}$，时间复杂度 $O(\frac{n^2W}{B})$。
每次询问时取出 $l,r$ 所在块编号 $idx_l,idx_r$，向 $f_{idx_l-1,idx_r+1}$ 加入散块即可，时间复杂度 $O(qWB)$。
综上，$B$ 取 $\frac{n}{\sqrt q}$ 最优，时间复杂度 $O(nW\sqrt q)$。
发现空间复杂度 $O(\frac{n^2W}{q})$，当 $q$ 较小时会爆内存，所以太大时考虑取 $\sqrt n$，此时时间复杂度 $O(nW\sqrt n+qW\sqrt n)$，使用二进制拆分复杂度再加 $\log c$，空间复杂度 $O(nW)$。
这题实测很奇怪：
>$B$ 取 $\frac{n}{\sqrt q}$ 实测效果一般，4.81s。
>
>$B$ 取 $\sqrt n$ 实测效果不错，4.75s。
>
>使用线性的单调队列却要 5.71s。
---
### [P15649 [省选联考 2026] 找寻者 / recollector](https://www.luogu.com.cn/problem/P15649)
给定一个以 $1$ 为根节点的有根树，节点数为 $n$。
递归自底向上每个点 $u$ 按概率选取子节点 $v\in\mathrm{son}(u)$ 作为“重”儿子，概率与 $v$ 所在“重”链长度 $l_v$（指已经完成递归的 $u$ 子树中，$l_v$ 是随机变量）成正比，即：
$$\frac{l_v}{\sum\limits_{c\in\mathrm{son}(u)}l_c}$$
求每个点到 $1$ 路径上“轻”边（非“重”边）个数之和的期望值，对 $998244353$ 取模。
$n\leq5\times10^3$。
---
首先问题可以转化为求每条边成为“轻”边的概率，记 $v$ 到它父亲 $u$ 这条边是“轻”边的概率。设这条边为“重”的概率为 $p_v$，答案就是：
$$\sum\limits_{u}\sum\limits_{a\in\mathrm{anc}(u)}(1-p_a)$$
接下来我们要计算 $p_v$，设 $dp_{v,i}$ 为节点 $v$ 的“重”链向下延伸长度为 $i$ 的概率，$f_{v,i}$ 为 $u$ 子节点集合去除 $v$ 后向下延伸“重”链**长度和** 为 $i$ 的概率，那么：
$$p_v=\sum_{j,k}dp_{v,j}\times f_{v,k}\times\frac{j}{j+k}$$
当不去除任何子节点时，令其为 $f_{0}$，当加入一个儿子 $v$ 时，这是很简单的背包：
$$f_{0,i+j}\leftarrow f_{0,i+j}+f_{0,i}\times dp_{v,j}$$
现在我们要支持撤销一个儿子 $v$，对于卷积来说就是$f_v$ 和 $dp_v$ 的“卷积”为 $f_0$，故可以用类似多项式除法的方式用 $dp_v$ 和 $f_0$ 去计算 $f_v$：
设 $mn_v$ 是 $dp_v$ 的最小非零下标，那么 $f_0$ 的最小非零下标至少是 $mn_v$，且 $f_{v,0}$ 对应：
$$f_{0,mn_v}=f_{v,0}\times dp_{v,mn_v}$$
$$f_{v,0}=\frac{f_{0,mn_v}}{dp_{v,mn_v}}$$
然后从 $f_0$ 中减去 $f_{v,0}\times dp_v$，得到新的 $f'_0$，再重复上述操作，每次迭代处理 $f_0$ 的位置增加 $1$，从而可以递推求出所有 $f_v$。
对此我们只需要求逆元计算 $f_{v,0}=\frac{f_{0,mn_v}}{dp_{v,mn_v}}$ 就行。
时间复杂度 $O(n^2)$。
---
### 拓展题推荐
~~我才不会告诉你是因为我不会。~~
**[P4495 [HAOI2018] 奇怪的背包](https://www.luogu.com.cn/problem/P4495)**：模意义下背包方案数。
**[P6326 Shopping](https://www.luogu.com.cn/problem/P6326)**：点分治。
**[P8136 [ICPC 2020 WF] Quests](https://www.luogu.com.cn/problem/P8136)**：邻项交换，加 bitset 优化。
**[P9111 [福建省队集训2019] 最大权独立集问题](https://www.luogu.com.cn/problem/solution/P9111)**：题如其名。
**[P13231 [GCJ 2015 #3] Log Set](https://www.luogu.com.cn/problem/P13231)**：思维难度较高的撤销背包。
**[CF1442D Sum](https://www.luogu.com.cn/problem/CF1442D)**：分治。