P15870 【MX-X26-T6】「Cfz Round 7」vivi

こんな話など　忘れておくれ　/　这样的话之类的　就请你忘掉吧 言いたいことは　一つもないさ　/　想说出口的事　一件也没有了

商店里有 $n$ 条「鱼鱼」排成一排，第 $i$ 条「鱼鱼」的体积为 $a_i$。 Yuki 有一个体积为 $V$ 的背包，她打算从 $1$ 到 $n$ 依次考虑每条「鱼鱼」：如果当前「鱼鱼」的体积小于等于背包剩余体积，则将该「鱼鱼」装入背包，否则不将该「鱼鱼」装入背包。当一条体积为 $x$ 的「鱼鱼」被装入背包时，背包的剩余体积会减少 $x$。 由于 Yuki 是魔法少女，她可以让背包的 **初始体积 $\boldsymbol{V}$** 为任意非负整数，不过她不会在考虑「鱼鱼」的过程中修改背包的体积。 设 $s_i$ 表示第 $i$ 条「鱼鱼」的选取状态；具体地，若第 $i$ 条「鱼鱼」被装入背包了则 $s_i=1$，否则 $s_i=0$。你需要求出，上述策略可以生成多少种序列 $s$。

第一行包含一个整数 $c$，表示该测试点所属的子任务编号。样例满足 $c=0$。 第二行包含一个整数 $n$。 第三行包含 $n$ 个整数 $a_1,\dots,a_n$。

输出一行，包含一个非负整数，表示可以生成的不同的序列 $s$ 的数量。

### 样例 1 解释 - 当背包的初始体积 $V=0$ 时，$s=\{0,0,0\}$； - 当背包的初始体积 $V=2$ 时，$s=\{1,0,0\}$； - 当背包的初始体积 $V=5$ 时，$s=\{1,1,0\}$； - 当背包的初始体积 $V=23$ 时，$s=\{1,1,1\}$。 容易证明，当背包的初始体积 $V$ 等于其他非负整数时，生成的 $s$ 一定为这 $4$ 种中的 $1$ 种，因此答案为 $4$。 ### 样例 2 解释 - 当背包的初始体积 $V=0$ 时，$s=\{0,0,0,0\}$； - 当背包的初始体积 $V=1$ 时，$s=\{1,0,0,0\}$； - 当背包的初始体积 $V=3$ 时，$s=\{1,0,1,0\}$； - 当背包的初始体积 $V=4$ 时，$s=\{1,1,0,0\}$； - 当背包的初始体积 $V=7$ 时，$s=\{1,1,1,0\}$； - 当背包的初始体积 $V=10$ 时，$s=\{1,1,1,1\}$； 容易证明，当背包的初始体积 $V$ 等于其他非负整数时，生成的 $s$ 一定为这 $6$ 种中的 $1$ 种，因此答案为 $6$。 ### 数据范围 对于所有测试数据，均有： - $1 \le n \le 2\cdot10^5$； - 对于所有 $1 \le i \le n$，均有 $1 \le a_i \le 10^9$。 **本题采用捆绑测试。** - Subtask 1（7 points）：$n \le 18$。 - Subtask 2（11 points）：$n \le 100$；对于所有 $1 \le i \le n$，均有 $a_i \le 100$。 - Subtask 3（8 points）：$n \le 500$；对于所有 $1 \le i \le n$，均有 $a_i \le 500$。 - Subtask 4（5 points）：$n \le 500$。 - Subtask 5（12 points）：$n \le 8\cdot10^3$；对于所有 $1\le i \le n$，均有 $a_i \le 8\cdot10^3$； - Subtask 6（15 points）：$n \le 8\cdot10^3$。 - Subtask 7（13 points）：$n \le 8\cdot 10^4$。 - Subtask 8（12 points）：保证序列 $a$ 单调不增。 - Subtask 9（17 points）：无特殊限制。