A5934 | 「WC2020」猜数游戏
时间限制2s
内存限制128MB
通过 / 提交0/0
题目描述
黑板上写有 $n$ 个互不相等且都小于 $p$ 的正整数 $a_1, a_2, \cdots, a_n$。小 J 想用这些数字和小 M 玩一个猜数游戏。
游戏规则十分简单：游戏开始时，小 J 会从这些数字中随机选择若干个让小 M 来猜，而小 M 则可以通过若干次**询问**来确定小 J 选择了哪些数字。
每一次**询问**的模式如下：小 M 可以任意指定一个数字 $a_k$，若它是小 J 所选择的数字之一，则小 J 会告诉小 M 他所选择的数字中所有能表示成 $(a_k)^m \bmod p$ 的数，其中 $m$ 是任意正整数，$\bmod$ 表示求二者做带余除法后的余数。反之，若 $a_k$ 没有被小 J 选中，则小 J 只会告诉小 M $a_k$ 没有被选中。
游戏会在小 M 确定小 J 所选中的所有数字后立刻结束。
例如，若 $n=4$，$p=7$，数字 $\{a_n\}$ 按下标顺序依次为 $\{1, 3, 4, 6\}$，小 J 选定的数字为 $\{1, 4, 6\}$，一种可能的游戏进行的过程（并非是最优过程）如下：
| 小 M 的询问 | 小 J 的反馈 |
| :-----------: | :-------------------------------------: |
| $a_2 = 3$ | $a_2$ 没有被选中 |
| $a_4 = 6$ | $6(= 6^1 \bmod 7)$，$1(=6^2 \bmod 7)$ |
| $a_3 = 4$ | $4(= 4^1 \bmod 7)$，$1(=4^3 \bmod 7)$ |
$3$ 次询问后小 J 所选出的所有数都已被小 M 确定，游戏结束。
小 M 还有作业没有写完，因此他需要对游戏进行的时间进行评估。他想知道为了使游戏结束，他所需要做出询问的最小次数的期望 $S$ 是多少。
为了避免精度误差，你需要输出答案乘 $(2^n - 1)$ 后模 $998244353$ 的余数。在本题中，你可以认为小 J 每次在选数时会在集合 $\{a_1, a_2, \cdots, a_n\}$ 的全部**非空子集**中等概率地选择一个，在这个前提下可以证明 $(2^n - 1) \times S$ 一定是一个整数。
游戏规则十分简单：游戏开始时，小 J 会从这些数字中随机选择若干个让小 M 来猜，而小 M 则可以通过若干次**询问**来确定小 J 选择了哪些数字。
每一次**询问**的模式如下：小 M 可以任意指定一个数字 $a_k$，若它是小 J 所选择的数字之一，则小 J 会告诉小 M 他所选择的数字中所有能表示成 $(a_k)^m \bmod p$ 的数，其中 $m$ 是任意正整数，$\bmod$ 表示求二者做带余除法后的余数。反之，若 $a_k$ 没有被小 J 选中，则小 J 只会告诉小 M $a_k$ 没有被选中。
游戏会在小 M 确定小 J 所选中的所有数字后立刻结束。
例如，若 $n=4$，$p=7$，数字 $\{a_n\}$ 按下标顺序依次为 $\{1, 3, 4, 6\}$，小 J 选定的数字为 $\{1, 4, 6\}$，一种可能的游戏进行的过程（并非是最优过程）如下：
| 小 M 的询问 | 小 J 的反馈 |
| :-----------: | :-------------------------------------: |
| $a_2 = 3$ | $a_2$ 没有被选中 |
| $a_4 = 6$ | $6(= 6^1 \bmod 7)$，$1(=6^2 \bmod 7)$ |
| $a_3 = 4$ | $4(= 4^1 \bmod 7)$，$1(=4^3 \bmod 7)$ |
$3$ 次询问后小 J 所选出的所有数都已被小 M 确定，游戏结束。
小 M 还有作业没有写完，因此他需要对游戏进行的时间进行评估。他想知道为了使游戏结束，他所需要做出询问的最小次数的期望 $S$ 是多少。
为了避免精度误差，你需要输出答案乘 $(2^n - 1)$ 后模 $998244353$ 的余数。在本题中，你可以认为小 J 每次在选数时会在集合 $\{a_1, a_2, \cdots, a_n\}$ 的全部**非空子集**中等概率地选择一个，在这个前提下可以证明 $(2^n - 1) \times S$ 一定是一个整数。
输入格式
第一行两个正整数 $n$ 和 $p$。
第二行 $n$ 个正整数，依次表示 $a_1, a_2, \cdots, a_n$。
第二行 $n$ 个正整数，依次表示 $a_1, a_2, \cdots, a_n$。
输出格式
仅一行一个整数表示答案。
输入输出样例
输入 #1
4 7 1 3 4 6
输出 #1
17
输入 #2
8 9 1 2 3 4 5 6 7 8
输出 #2
532
对于所有测试点：$1 \leq n \leq 5000$，$3 \leq p \leq 10^8$，$1 \leq a_i < p\ (1 \leq i \leq n)$ 且 $a_i$ 两两不同。
对于所有编号为奇数的测试点，保证 $p$ 是一个素数；对于所有编号为偶数的测试点，保证存在奇素数 $q$ 和正整数 $k > 1$ 使得 $p = q^k$。
| 测试点编号 | $n\leq$ | $p\le$ | 特殊性质 | 测试点编号 | $n\leq$ | $q\le$ | 特殊性质 |
| :----------: | :-------: | :------: | :--------: | :----------: | :-------: | :------: | :--------: |
| $1$ | $10$ | $100$ | 无 | $2$ | $10$ | $100$ | 无 |
| $3$ |$10$|$100$|无| $4$|$10$|$100$|无|
| $5$ | $200$ | $5000$| 无 | $6$ | $200$ | $5000$ | 无 |
| $7$ | $300$ | $10^6$ |无| $8$ | $300$ | $10^6$ | 无|
| $9$|$300$ |$10^6$ | A| $10$ | $300$ | $10^6$ |B|
| $11$ | $5000$ | $10^7$ |A| $12$ | $5000$ | $10^7$ | 无 |
| $13$|$5000$|$10^7$ | 无 | $14$ | $5000$|$10^7$| 无|
| $15$|$5000$ | $10^8$ | A | $16$ | $5000$|$10^8$ | B|
| $17$ | $5000$|$10^8$|无 | $18$ |$5000$|$10^8$| 无 |
| $19$ | $5000$|$10^8$|无 | $20$ |$5000$|$10^8$| 无 |
特殊性质 A：在模 $p$ 意义下 $3^i\ (1 \leq i \leq p - 1)$ 两两不同余。
特殊性质 B：对所有的 $1 \leq i \leq n$ 都有 $(a_i, p) > 1$。
对于所有编号为奇数的测试点，保证 $p$ 是一个素数；对于所有编号为偶数的测试点，保证存在奇素数 $q$ 和正整数 $k > 1$ 使得 $p = q^k$。
| 测试点编号 | $n\leq$ | $p\le$ | 特殊性质 | 测试点编号 | $n\leq$ | $q\le$ | 特殊性质 |
| :----------: | :-------: | :------: | :--------: | :----------: | :-------: | :------: | :--------: |
| $1$ | $10$ | $100$ | 无 | $2$ | $10$ | $100$ | 无 |
| $3$ |$10$|$100$|无| $4$|$10$|$100$|无|
| $5$ | $200$ | $5000$| 无 | $6$ | $200$ | $5000$ | 无 |
| $7$ | $300$ | $10^6$ |无| $8$ | $300$ | $10^6$ | 无|
| $9$|$300$ |$10^6$ | A| $10$ | $300$ | $10^6$ |B|
| $11$ | $5000$ | $10^7$ |A| $12$ | $5000$ | $10^7$ | 无 |
| $13$|$5000$|$10^7$ | 无 | $14$ | $5000$|$10^7$| 无|
| $15$|$5000$ | $10^8$ | A | $16$ | $5000$|$10^8$ | B|
| $17$ | $5000$|$10^8$|无 | $18$ |$5000$|$10^8$| 无 |
| $19$ | $5000$|$10^8$|无 | $20$ |$5000$|$10^8$| 无 |
特殊性质 A：在模 $p$ 意义下 $3^i\ (1 \leq i \leq p - 1)$ 两两不同余。
特殊性质 B：对所有的 $1 \leq i \leq n$ 都有 $(a_i, p) > 1$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？