奇怪的背包（们）
CQ友谊赛 - pack
\(n\leq 100\)。物品体积 \(\leq 100\)，权值很大 \((\leq 10^9)\)。\(m(\leq 100)\) 次询问，求体积恰好为 \(q(\leq 10^9)\) 时的最大物品价值和方案数（相同的物品间没有顺序之分，不同的物品间有顺序之分。）
物品体积 \(\leq 100\) 是突破口。设 \(f_i=(a,b)\) 表示体积恰好为 \(i\) 时最大价值为 \(a\) 方案数为 \(b\)。一个物品设为 \((v_i,1)\) （\(v_i\) 是体积。）有转移 \(f_{i+w_j}=f_{i+w_j}+f_i \times (v_j,1)\)。其中二元组加法就类似线段树维护最小值个数时 pushup 的操作。二元组乘法就是 \(a\) 相加，\(b\) 相乘。发现这个是对的，而且可以放到矩阵上。直接矩阵快速幂优化就做完了。
[THUPC 2023 初赛] 背包
\(10^{11} \leq V \leq 10^{12}\) 是突破口。体积下界大得离谱！显然要选一堆性价比最高的。总而言之地引用一句话，“发现 \(V\) 很大 \(v_i\) 却很小，而且还是完全背包，一般都是同余最短路。”
设我们一开始选择了 \(\lfloor \frac{V}{v_0} \rfloor\) 个最优物品，其中 \(v_0\) 是最优物品的体积。设 \(f_i\) 表示，选择体积 \(\bmod v_0 = i\) 时的最优增量。什么意思呢？假设选了一个其它物品，让 \(i+v_j\) 超过了 \(v_0\)，那么此时就需要少选一些最优物品让总体积不超过 \(V\)，即还要减去 \(\lfloor \frac{i+v_j}{v_0} \rfloor \times w_0\)。这样最后再加上 \(f_{V\bmod v_0}\) 就是答案。求 \(f\) 直接跑最长路就行了。
这显然是对的。我们不可能让最优物品数量变成负。因为最长路不可能经过同一个节点，一旦经过了就说明中间加入的体积 \(\bmod v_0 = 0\)，这样就一定不优。当每一个节点只经过一次，总共只会加入 \(v^2\) 的额外体积，这显然是 \(\leq 10^{10}\) 的，而且小于 \(V\) 的下界 \(10^{11}\)。于是它就是对的了。