本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-09-04 23:08:23

本题解尚未提交代码，不一定正确。

做法

先来考虑一下，已知每种砝码是否出现的情况下怎么判定能否凑出 $x$。

很容易写出一个指数级的爆搜：以当前重量 $x$ 为参数，枚举砝码从 $x$ 中减掉递归下去，看能否递归到 $0$。

复杂度：算不出来。预计得分：$0$ 分。

这个爆搜之所以是指数级，是因为重复搜索了很多节点，所以搜完一个节点，就把这个节点的答案记录下来，就优化到 $O(m)$ 了。

每次询问就临时统计一下询问区间每种砝码是否出现，用得到的信息跑记忆化搜索。

复杂度：$O(qn+qm)$。预计得分：$50$ 分。

题目说了，砝码的数值不会超过 $10$ 种。
而能否凑出一个数，只和这个数的数值以及砝码拥有状态决定。

要凑的数最大是 $10^5$，而砝码拥有状态有 $2^{10} = 1024$ 种可能性。

可以把每种可能都枚举一下，进行预处理。

每次查询的时候，线段树维护区间每种砝码是否出现，然后用得到的信息直接查表。

复杂度：$O(1024m+q \log n)$，预计得分：$100$ 分。

Code

正在写。