[PA 2020] Cukierki

Luogu

IDLGP9102

Time3000ms

Memory512MB

DifficultyP4

动态规划 DP2020PA（波兰）

**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Cukierki](https://sio2.mimuw.edu.pl/c/pa-2020-1/cuk/)** Bytie 要去参加 Bitek 的生日聚会。他知道 Bitek 喜欢吃甜食，所以他想送他一些糖果作为礼物。他买了 $n$ 袋糖，其中第 $i$ 袋包含 $a_i$ 个糖果。然而，这些糖相当重，Bytie 想知道他是否需要把它们全都给 Bitek。他决定，他将选择一个非空的袋装糖果子集，把它们拿给 Bitek，并对他说：「我这里总共有 $x$ 颗糖果，你想要多少？」，其中 $x$ 将是带到派对上的包装里的糖果总数。Bitek 听到这个问题后，可能会选择区间 $[1, x]$ 中的任何整数 $y$。无论 Bitek 的回答如何，他都希望能够从带到派对上的糖中选择一部分（其余的留给自己），这样这些袋糖中的糖果总数正好等于 $y$。当然，不可以撕毁包装纸——给散装的糖果是不礼貌的。因此，Bytie 在想，他能给 Bitek 带去多少种非空的袋装糖果子集，以便在不考虑 Bitek 的选择的情况下，能够送给他所需数量的糖果。请帮助他计算一下吧！由于这种子集的数量可能非常大，请输出它对 $10^9+7$ 取模后的结果。 ## Input 第一行一个整数 $n$，表示 Bytie 有的袋装糖果数量。第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每袋糖果中糖果的数量。 ## Output 输出可能的袋装糖果子集种类数对 $10^9+7$ 取模后的值。 [samples] ## Note #### 样例 1 解释 Bytie 可以带去 $8$ 种非空子集：$\{5\}, \{1, 5\}, \{1, 3, 5\}, \{1, 4, 5\}, \{1, 3, 4, 5\}, \{1, 2, 3, 5\}, \{1, 2, 4, 5\}$ 和 $\{1, 2, 3, 4, 5\}$。例如，Bytie 带去的子集是 $\{1,2,4,5\}$，Bitek 想要 $9$ 颗糖果时，Bytie 只能给他第 $1,2$ 包糖。Bytie 不可以带去 $\{1,2,5\}$ 子集，如果 Bitek 想要 $6$ 颗糖的话 Bytie 就犯难了。 ------------ #### 数据范围 **本题采用捆绑测试** 对于 $100\%$ 的数据，保证 $1\le n\le 5\times 10^3$，$1\le a_i\le 5\times 10^3$。

Samples

Input #1

5
2 7 4 4 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[PA 2020] Cukierki",
    "description": {
      "content": "**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Cukierki](https://sio2.mimuw.edu.pl/c/pa-2020-1/cuk/)** Bytie 要去参加 Bitek 的生日聚会。他知道 Bitek 喜欢吃甜食，所以他想送他一些糖果作为礼物。他买了 $n$ 袋糖，其中",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9102"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Cukierki](https://sio2.mimuw.edu.pl/c/pa-2020-1/cuk/)**\n\nBytie 要去参加 Bitek 的生日聚会。他知道 Bitek 喜欢吃甜食，所以他想送他一些糖果作为礼物。他买了 $n$ 袋糖，其中...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments