{"problem":{"name":"【MX-S1-T4】先见之明","description":{"content":"给定 $n$ 个非负整数 $a_1, a_2, \\ldots, a_n$。有 $q$ 次询问，每次询问： - 给定一个非负整数 $k$，你需要从 $2^{a_1}, \\ldots, 2^{a_n}$ 中取出一部分（即一个子集，可以为空），使得它们的和 $\\ge k$。 - 在保证和 $\\ge k$ 的前提下，你需要最小化它们的和。你只需求出这个最小化的和。 - $k$ 以二进制的形式给出，具体地","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10675"},"statements":[{"statement_type":"Markdown","content":"给定 $n$ 个非负整数 $a_1, a_2, \\ldots, a_n$。有 $q$ 次询问，每次询问：\n\n- 给定一个非负整数 $k$，你需要从 $2^{a_1}, \\ldots, 2^{a_n}$ 中取出一部分（即一个子集，可以为空），使得它们的和 $\\ge k$。\n- 在保证和 $\\ge k$ 的前提下，你需要最小化它们的和。你只需求出这个最小化的和。\n- $k$ 以二进制的形式给出，具体地，以 $k = \\sum_{i = 1}^{m} 2^{p_i}$ 的形式给出，保证 $p_i$ 均为非负整数且严格单调递减，即 $p_i > p_{i + 1}$。\n\n由于答案可能很大，你只需要输出对 $998244353$ 取模后的结果。\n\n若无法从 $2^{a_1}, \\ldots, 2^{a_n}$ 中取出一部分使得它们的和 $\\ge k$，该询问输出 $-1$。\n\n## Input\n\n第一行两个正整数 $n,q$。\n\n第二行 $n$ 个非负整数 $a_1,a_2,\\dots,a_n$。\n\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}$。\n\n## Output\n\n共 $q$ 行，每行一个整数，表示答案对 $998244353$ 取模后的结果，或输出 $-1$ 表示无解。\n\n[samples]\n\n## Background\n\n原题链接：<https://oier.team/problems/S1D>。\n\n## Note\n\n__【样例解释 1】__\n\n每个 $2^{a_i}$ 分别为 $1, 1, 2$。三次询问的 $k$ 为：$0,3,8$。具体如下：\n- $k = 0$：取空。\n- $k = 3$：取 $1, 2$ 即可。\n- $k = 8$：无解。\n\n__【样例解释 2】__\n\n此样例满足子任务 $1$ 的限制。\n\n__【数据范围】__\n\n__本题使用子任务捆绑测试。__\n\n对于 $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\n表格留空表示无额外限制。\n\n| 子任务编号 | $n\\le $        | $q\\le $        | $\\sum m\\le $     | $a_i,p_i \\le $ | 特殊性质       | 分值 |\n| ---------- | -------------- | -------------- | ---------------- | -------------- | -------------- | ---- |\n| $1$        | $20$           |                |                  | $60$           |                | $10$ |\n| $2$        | $120$          |                |                  | $60$           |                | $10$ |\n| $3$        | $5\\times 10^3$ | $5\\times 10^3$ | $2.5\\times 10^4$ | $5\\times 10^3$ |                | $20$ |\n| $4$        | $10^5$         | $10^5$         | $5\\times 10^5$   | $10^5$         |                | $20$ |\n| $5$        |                |                |                  |                | $m\\le 2$       | $10$ |\n| $6$        |                |                |                  |                | $a_i$ 互不相同 | $10$ |\n| $7$        | $10^6$         | $10^6$         | $5\\times 10^6$   | $10^6$         |                | $20$ |\n\n由于本题输入量较大，我们在下发文件中提供了 `fast_read.cpp` 可以选择使用（注意在 C++98 标准下可能无法编译通过）。\n\n保证时间限制达到了没有使用特殊的读入优化的 std 的两倍。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10675","tags":["数学","贪心","线段树","O2优化","进制","梦熊比赛"],"sample_group":[["3 3\n0 0 1\n0\n2 1 0\n1 3\n","0\n3\n-1\n"],["见下发文件。","见下发文件。"]],"created_at":"2026-03-03 11:09:25"}}