Markdown：

~~题解前几个怎么全是火车头。。~~

这道题目的算法是背包 DP ，不难发现，我们亲爱的“题目翻译”把题目给精简化了，所以题目就这几句话：

有 $n$ 个物品，第 $i$ 个物品价值 $A _ {i}$ 元，现在问你 $q$ 次，从 $l$ 到 $r$ 中，最多能组合出多少种价值（**每个物品只能用一次**）？

这一看，这岂不是 01 背包 DP ？

01背包板子： $dp[i][j] = dp[i - 1][j - w[i]]$


仔细思考后发现，这题不能开 DP 数组！应该使用 `std::bitset` 优化！

不难发现， DP 数组的每个元素始终保持着存储 $0$ 或 $1$ ，就和二进制很像！而 `std::bitset` 则就是把他当成一个二进制数，自然空间会小很多。

我们每次就是要从上一个状态中推过来，所以 bitset 一个就够了，这算是滚动优化。

于是乎推出公式： `dp = dp | (dp << a[i]);`

最后，我们给 DP 数组加个前缀和即可！

在原 OJ 上已 AC ！（在洛谷没绑号，可不是没 AC 发题解啊！）

```cpp
#include <bits/stdc++.h>
using namespace std;
int a[100007];
bitset<100007> dp;
int pr[100007]; // 前缀和
int n, q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    cin >> n >> q;
    dp[0] = 1; // 很显然，0是一定拼的出来的。
    pr[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp |= dp << a[i]; // 公式，不再赘述。
    }
    for (int i = 1; i <= 100000; i++)
        pr[i] = pr[i - 1] + dp[i]; // 前缀和
    for (int i = 1; i <= q; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << pr[r] - pr[l - 1] << '\n'; // 前缀和直接O(1)处理。
    }
    return 0;
}

原因：很遗憾，您的《题解：SP30738 ADACOINS - Ada and Coins》不符合推荐标准。原因是：上下标应使用$a _ {b} ^ {c}$（$a _ {b} ^ {c}$）进行表示。。