# 剑与暴击 参考时间限制：2 秒；内存限制：256 MiB。正式时限按目标环境标准程序的最慢用例中位数乘以 2，再向上取整至 0.5 秒。参见[评测说明](tests/README.md)。 ## 背景故事 你在游玩《+1 DMG Per Revive》时，获得了许多把剑。每把剑都能独立触发暴击，触发后提供自己的伤害倍率；多把剑同时触发时，这些倍率相乘。 现在，你要挑战死亡之塔。这里的战斗很依赖单次伤害峰值，而暴击倍率是决定峰值的重要因子。面对不同楼层，你列出了若干个目标倍率，想知道同一套剑的一次攻击达到每个目标的概率。 ## 形式化问题描述 你拥有 $n$ 把剑。第 $i$ 把剑对应两个整数 $p_i,m_i$ ：它以 $p_i/10^6$ 的概率触发暴击。触发时贡献倍率 $m_i$ ，未触发时贡献倍率 $1$ .所有剑是否触发的事件相互独立。 一次攻击的总暴击倍率为所有剑贡献倍率的乘积。若没有剑触发，总倍率为 $1$ .所有剑都会参与判定，不需要选择或装备其中一部分。 给定 $q$ 个整数阈值 $K_1,\ldots,K_q$ .对每个阈值，分别求一次攻击的总暴击倍率**大于等于**该阈值的概率。各询问使用同一套剑；它们询问各自的概率，不要求多个事件同时发生，也不改变后续询问的剑或概率。 令 $P=998244353$ .将所求概率写成最简分数 $A/B$ ，输出 $AB^{-1}\bmod P$ 的最小非负余数。由于每把剑的概率分母均为 $10^6$ ，最简分母一定与 $P$ 互质，因此答案总有定义。 **只对概率答案取模。倍率、阈值及它们之间的大小比较都按原整数含义处理。** ## 输入格式 第一行一个整数 $T$ ，表示独立测试组的数量。 每组测试依次包含： - 第一行两个整数 $n,q$ ，表示剑的数量和询问数量。 - 接下来 $n$ 行，每行两个整数 $p_i,m_i$ . - 接下来 $q$ 行，每行一个整数 $K_j$ ，使用普通十进制记法给出。 ## 输出格式 按测试组和询问的输入顺序，对每个询问输出一行模 $P$ 的概率。 ## 样例 1 ### 输入 ```text 1 3 6 500000 2 250000 3 1000000 5 1 5 10 15 30 31 ``` ### 输出 ```text 1 1 374341633 748683265 873463809 0 ``` ## 样例 2 ### 输入 ```text 1 2 3 500000 999999937 500000 999999929 999999866000004472 999999866000004473 999999866000004474 ``` ### 输出 ```text 748683265 748683265 0 ``` ## 样例 3 ### 输入 ```text 2 2 2 0 1000000000 743921 1 1 2 3 2 1000000 1000000000 1000000 1000000000 1000000 1000000000 1 1000000000000000000 ``` ### 输出 ```text 1 0 1 1 ``` ## 样例解释 样例 1 中第三把剑必定触发。总倍率可能为 $5,10,15,30$ .达到 $10$ 倍需要前两把剑至少一把触发，概率为 $5/8$ ；达到 $15$ 倍需要第二把剑触发，概率为 $1/4$ ；达到 $30$ 倍需要前两把剑同时触发，概率为 $1/8$ . 样例 2 中两把剑同时触发的倍率为 $999999866000004473$ ，概率为 $1/4$ .前两个阈值均需要两把剑同时触发；第三个阈值无法达到。 样例 3 的第一组总倍率恒为 $1$ ；第二组三把剑必定触发，数学上的总倍率为 $10^{27}$ ，两个询问的答案均为 $1$ .求解时只需保留与阈值比较所需的信息，无须存储这个完整乘积。 ## 数据范围与保证 对于 100% 的数据： - $1\le T\le8$ ，$1\le n\le2000$ ，$1\le q\le5600$ . - $0\le p_i\le10^6$ ，$1\le m_i\le10^9$ ，$1\le K_j\le10^{18}$ . - 每组测试至少满足以下条件之一：$n\le44$ ，或所有阈值均不超过 $2\cdot10^7$ . - 所有输入数据均为整数，均可用有符号 64 位整数保存。无需计算所有剑倍率的完整乘积；本题可以仅用 64 位整数运算精确求解。 为说明一个输入文件内的总规模，记第 $t$ 组的剑数和询问数为 $n_t,q_t$ .设 $\mathcal A$ 为所有阈值均不超过 $2\cdot10^7$ 的测试组集合，$\mathcal B$ 为其余测试组集合，还保证一个输入文件内的询问总数 $\sum_t q_t\le5600$ ，并保证： $$ \sum_{t\in\mathcal A}n_tq_t\le2000 $$ $$ \sum_{t\in\mathcal B}(q_t+4)\,2^{\lceil n_t/2\rceil}\le7\cdot2^{24} $$ 本题的多询问规格、整数范围、数据分组与性能约束由 Codex（GPT-6）设计。 | 分值比例 | 额外条件 | | --- | --- | | 20% | 每组测试均满足 $n\le18$ | | 30% | 所有阈值均不超过 $2\cdot10^7$ | | 20% | 每组测试均满足 $n\le34$ | | 30% | 无额外条件 | 共 10 个测试点，每点占 10%；完整生成配方见[测试说明](tests/README.md)。