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

前言：

谢 lhx 大佬的思路

记录思路区：

可以使用分组背包，将 $a_i,0,-a_i$ 分成一个组 可以遍历 $-\sum a_i \rightarrow \sum a_i$ 的每个数，对其中每个数进行分组背包求解方案数。
由于遍历的过程复杂度是 $O(\sum a_i)$，对每个数分组背包求解方案数的过程是 $3 \cdot n = O(n)$ 的（$3$ 是每个组的大小），所以总复杂度是 $O(n \cdot \sum a_i + q)$

UPD: 实际上上面的复杂度假了，因为分组背包的复杂度不是 $O(n)$，下面写上我的新想法：
和上面一样，仍然将 $a_i,0,-a_i$ 分成一个组，这样就有了 $n$ 个组，然后遍历这 $n$ 个组，对于每个组遍历 $\sum a_i \rightarrow -\sum a_i$（要凑成的数）计算方案数。
这样总复杂度是 $O(n \cdot \sum a_i + q)$
现在的瓶颈是我不会这种计算方案数类型的背包 dp。

做法

还没想好