【MX-S1-T4】先见之明
题目描述
给定 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$。有 $q$ 次询问,每次询问:
- 给定一个非负整数 $k$,你需要从 $2^{a_1}, \ldots, 2^{a_n}$ 中取出一部分(即一个子集,可以为空),使得它们的和 $\ge k$。
- 在保证和 $\ge k$ 的前提下,你需要最小化它们的和。你只需求出这个最小化的和。
- $k$ 以二进制的形式给出,具体地,以 $k = \sum_{i = 1}^{m} 2^{p_i}$ 的形式给出,保证 $p_i$ 均为非负整数且严格单调递减,即 $p_i > p_{i + 1}$。
由于答案可能很大,你只需要输出对 $998244353$ 取模后的结果。
若无法从 $2^{a_1}, \ldots, 2^{a_n}$ 中取出一部分使得它们的和 $\ge k$,该询问输出 $-1$。
输入输出格式
输入格式
第一行两个正整数 $n,q$。
第二行 $n$ 个非负整数 $a_1,a_2,\dots,a_n$。
接下来 $q$ 行,每行第一个非负整数为 $m$,接下来 $m$ 个非负整数为 $p_1,p_2,\dots,p_m$,表示询问的 $k=\sum_{i=1}^m 2^{p_i}$。保证 $p_i$ 严格单调递减,即 $p_i>p_{i+1}$。
输出格式
共 $q$ 行,每行一个整数,表示答案对 $998244353$ 取模后的结果,或输出 $-1$ 表示无解。
输入输出样例
输入样例 #1
3 3
0 0 1
0
2 1 0
1 3
输出样例 #1
0
3
-1
输入样例 #2
见下发文件。
输出样例 #2
见下发文件。
说明
__【样例解释 1】__
每个 $2^{a_i}$ 分别为 $1, 1, 2$。三次询问的 $k$ 为:$0,3,8$。具体如下:
- $k = 0$:取空。
- $k = 3$:取 $1, 2$ 即可。
- $k = 8$:无解。
__【样例解释 2】__
此样例满足子任务 $1$ 的限制。
__【数据范围】__
__本题使用子任务捆绑测试。__
对于 $100\%$ 的数据,$1\le n,q\le 10^6$,$0\le m\le 10^6$,$\sum m\le 5\times 10^6$,$0\le a_i,p_i\le 10^6$,$p_i>p_{i+1}$。
表格留空表示无额外限制。
| 子任务编号 | $n\le $ | $q\le $ | $\sum m\le $ | $a_i,p_i \le $ | 特殊性质 | 分值 |
| ---------- | -------------- | -------------- | ---------------- | -------------- | -------------- | ---- |
| $1$ | $20$ | | | $60$ | | $10$ |
| $2$ | $120$ | | | $60$ | | $10$ |
| $3$ | $5\times 10^3$ | $5\times 10^3$ | $2.5\times 10^4$ | $5\times 10^3$ | | $20$ |
| $4$ | $10^5$ | $10^5$ | $5\times 10^5$ | $10^5$ | | $20$ |
| $5$ | | | | | $m\le 2$ | $10$ |
| $6$ | | | | | $a_i$ 互不相同 | $10$ |
| $7$ | $10^6$ | $10^6$ | $5\times 10^6$ | $10^6$ | | $20$ |
由于本题输入量较大,我们在下发文件中提供了 `fast_read.cpp` 可以选择使用(注意在 C++98 标准下可能无法编译通过)。
保证时间限制达到了没有使用特殊的读入优化的 std 的两倍。