UOJ Logo Universal Online Judge

UOJ

#546. 【WC2020】猜数游戏

附件下载 统计

黑板上写有 $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$$a_1=1,a_4=6$
$a_3=4$$a_1=1,a_3=4$

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$。

输出格式

仅一行一个整数表示答案。

样例1

input

4 7
1 3 4 6

output

17

explanation

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

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

因此最小询问次数的期望 $S = \frac{17}{15}$。

样例2

input

8 9
1 2 3 4 5 6 7 8

output

532

样例3

见附加文件。

数据范围

对于所有测试点:$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 \le$$p \le$特殊限制测试点编号$n \le$$p \le$特殊限制
$1$$10$$100$$无$$2$$10$$100$$无$
$3$$4$
$5$$200$$5000$$6$$200$$5000$
$7$$300$$10^6$$8$$300$$10^6$
$9$$A$$10$$B$
$11$$5000$$10^7$$12$$5000$$10^7$$无$
$13$$无$$14$
$15$$10^8$$A$$16$$10^8$$B$
$17$$无$$18$$无$
$19$$20$

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

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

时间限制: $2\texttt{s}$

空间限制: $128\texttt{MB}$

附加文件