/ 7FOJ / 题库 /

「WC2020」猜数游戏

「WC2020」猜数游戏

背景

  • Idea: CCF
  • Data: CCF
  • Solution: CCF
  • 题面: CCF + LOJ@EntropyIncreaser + oistream(上传)

描述

黑板上写有 nn 个互不相等且都小于 pp 的正整数 a1,a2,,ana_1,a_2,\cdots ,a_n。小 J 想用这些数字和小 M 玩一个猜数游戏。

游戏规则十分简单:游戏开始时,小 J 会从这些数字中随机选择若干个让小 M 来猜,而小 M 则可以通过若干次 询问 来确定小 J 选择了哪些数字。

每一次 询问 的模式如下:小 M 可以任意指定一个数字 aka_k,若它是小 J 所选择的数字之一,则小 J 会告诉小 M 他所选择的数字中所有能表示成 akmmod  p{a_k}^m\mod p的数,其中 mm 是任意正整数,mod\operatorname{mod} 表示求二者做带余除法后的余数。反之,若 aka_k 没有被小 J 选中,则小 J 只会告诉小 M aka_k 没有被选中。

游戏会在小 M 确定小 J 所选中的所有数字后立刻结束。

例如,若 n=4n=4p=7p=7 ,数字 {an}\{a_n\} 按下标顺序依次为 {1,3,4,6}\{1,3,4,6\},小 J 选定的数字为 {1,4,6}\{1,4,6\},一种可能的游戏进行的过程(并非是最优过程)如下:

小 M 的询问 小 J 的反馈
a2=3a_2=3 a2a_2 没有被选中
a4=6a_4=6 6(=61mod  7),1(=43mod  7)6(=6^1\mod 7),1(=4^3\mod 7)
a3=4a_3=4 4(41mod  7),1(=43mod  7)4(4^1\mod 7),1(=4^3\mod 7)

33 次询问后小 J 所选出的所有数都已被小 M 确定,游戏结束。

小 M 还有作业没有写完,因此他需要对游戏进行的时间进行评估。他想知道为了使游戏结束,他所需要做出询问的最小次数的期望 SS 是多少。

为了避免精度误差,你需要输出答案乘 2n12^n-1 后模 998244353998244353 的余数。在本题中,你可以认为小 J 每次在选数时会在集合 {a1,a2,,an}\{a_1,a_2,\cdots ,a_n\}的全部 非空子集 中等概率地选择一个,在这个前提下可以证明 (2n1)×S(2^n-1)\times S一定是一个整数。

输入格式

第一行两个正整数 nnpp

第二行 nn 个正整数,依次表示 a1,a2,×,ana_1,a_2,\times ,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

下表给出了小 J 所选的子集与小 M 最小询问次数的关系。

小 J 所选的子集 最优的询问集合
{1}\{1\} {1}\{1\}
{3},{3,4},{3,6},{3,4,6},{1,3},{1,3,4},{1,3,6},{1,3,4,6}\{3\},\{3,4\},\{3,6\},\{3,4,6\},\{1,3\},\{1,3,4\},\{1,3,6\},\{1,3,4,6\} {3}
{4},{1,4}\{4\},\{1,4\} {4}\{4\}
{6},{1,6}\{6\},\{1,6\} {6}\{6\}
{4,6},{1,4,6}\{4,6\},\{1,4,6\} {4,6}\{4,6\}

因此最小询问次数的期望 S=1715S=\dfrac{17}{15}

数据规模与约定

对于所有测试点: 1n50001\leq n\leq 50003p1083\leq p\leq 10^81aip  (1in)1\leq a_i\leq p~~(1\leq i\leq n)aia_i 两两不同。

对于所有编号为奇数的测试点,保证 pp 是一个素数;对于所有编号为偶数的测试点,保证存在奇素数 qq 和正整数 k>1k>1 使得 p=qkp=q^k

acZlQA.jpg

(上传者注:此图源自 LibreOJ

特殊性质 A:在模 pp 意义下 3i  (1ip1)3^i~~(1\leq i\leq p-1) 两两不同余。

特殊性质 B:对所有的 1in1\leq i\leq n 都有 (ai,p)>1(a_i,p)>1

信息

ID
1112
难度
8
分类
数论 点击显示
标签
递交数
2
已通过
1
通过率
50%
被复制
1
上传者