题解

思路

小目标值：有界背包

对一次询问，依次加入四种硬币。处理面值为 $c$、上限为 $d$ 的硬币时，对每个模 $c$ 的剩余类维护长度为 $d+1$ 的滑动窗口，即可在 $O(4s)$ 时间完成有界背包。所有询问的 $s\le2000$ 时可以直接使用这一算法。

两种硬币的上限为 1

当 $d_3=d_4=1$ 时，枚举第三、四种硬币是否使用，共四种选择。剩余问题为

$$c_1x_1+c_2x_2=S,\qquad 0\le x_1\le d_1,\ 0\le x_2\le d_2.$$

用扩展欧几里得算法求一组解。约去 $g=\gcd(c_1,c_2)$ 后，所有解可写为

$$x_1=x_0+k\frac{c_2}{g},\qquad x_2=y_0-k\frac{c_1}{g}.$$

把两个变量的上下界换成 $k$ 的整数区间并求交即可计数，每次询问为 $O(\log \max c_i)$。

做法

无上限方案数

先用完全背包预处理

$$f[t]=\#\{(x_1,x_2,x_3,x_4)\mid x_i\ge0,\ \sum c_ix_i=t\}$$

对所有 $0\le t\le10^5$ 的值。由于硬币种类只有四种，这一步为 $O(4\cdot10^5)$。

容斥上界

定义坏事件 $A_i$ 为 $x_i\ge d_i+1$。若指定一个集合 $M$ 中的坏事件发生，把每个 $i\in M$ 的 $x_i$ 减去 $d_i+1$，就与总面值

$$s-\sum_{i\in M}(d_i+1)c_i$$

的无上限方案一一对应。因此答案为

$$\sum_{M\subseteq\{1,2,3,4\}}(-1)^{|M|} f\!\left(s-\sum_{i\in M}(d_i+1)c_i\right),$$

其中负下标项视为 $0$。每次询问只枚举 $16$ 个子集。

正确性证明

引理 1

预处理后的 $f[t]$ 等于使用四种硬币、不设数量上限时凑成 $t$ 的方案数。

证明。 完全背包按硬币种类依次更新。处理第 $i$ 种后，每个方案按该种硬币的使用枚数唯一分解，因此既无遗漏也无重复。∎

引理 2

对任意集合 $M$，同时违反其中所有上界的方案数等于 $f(s-\sum_{i\in M}(d_i+1)c_i)$。

证明。 对每个 $i\in M$ 强制取出 $d_i+1$ 枚硬币，剩余使用数均非负；反向补回这些硬币得到唯一原方案，故为双射。∎

定理

容斥公式给出的值恰为每次购物的合法付款方案数。

证明。 无上限方案全集由 $f[s]$ 计数，合法方案正是没有任何坏事件 $A_i$ 发生的方案。由容斥原理和引理 2，公式恰好计数这些方案。∎

复杂度

预处理时间复杂度 $O(4S)$、空间复杂度 $O(S)$，其中 $S=10^5$。每次询问时间复杂度 $O(2^4)=O(1)$。