CF1864E Guess Game

Carol 有一个长度为 $n$ 的非负整数序列 $s$。她想和 Alice 以及 Bob 一起玩“猜数游戏”。 游戏规则如下：Carol 会随机选择两个整数下标 $i_a$ 和 $i_b$，范围为 $[1, n]$，并令 $a=s_{i_a}$，$b=s_{i_b}$。注意 $i_a$ 和 $i_b$ 可以相同。 Carol 会告知： - Alice $a$ 的值； - Bob $b$ 的值； - Alice 和 Bob 都会知道 $a \mid b$ 的值，其中 $|$ 表示[按位或运算](https://en.wikipedia.org/wiki/Bitwise_operation#OR)。 注意，Carol 不会向 Alice 或 Bob 透露关于 $s$ 的任何其他信息。 接下来开始猜数。两位玩家轮流猜测，Alice 先手。两人的目标是判断以下哪种情况成立：$a < b$，$a > b$，或 $a = b$。 每一轮，玩家可以选择以下两种操作之一： - 说“我不知道”，并将回合交给另一位玩家； - 说“我知道”，并给出答案“$ab$”或“$a=b$”；此时游戏结束。 Alice 和 Bob 都能听到对方的发言，并可以利用这些信息进行推理。两人都足够聪明，只有在完全确定时才会说“我知道”。 你需要计算游戏中玩家所用回合数的期望值。输出答案对 $998\,244\,353$ 取模。 形式化地，设 $M=998\,244\,353$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数且 $q \not\equiv 0 \pmod{M}$。输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例数量。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$）。 第二行包含 $n$ 个整数 $s_1,s_2,\ldots, s_n$（$0 \le s_i < 2^{30}$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出一个整数，表示问题答案对 $998\,244\,353$ 取模后的结果。

在第一个测试用例中，共有 $4$ 种可能情况： 1. $i_a=1$，$i_b=1$，$a=2$，$b=2$，所需回合数为 $2$； 2. $i_a=1$，$i_b=2$，$a=2$，$b=3$，所需回合数为 $3$； 3. $i_a=2$，$i_b=1$，$a=3$，$b=2$，所需回合数为 $2$； 4. $i_a=2$，$i_b=2$，$a=3$，$b=3$，所需回合数为 $3$。 期望回合数为 $\frac{2+3+2+3}{4}=\frac{5}{2}=499122179\pmod{998244353}$。 以第一种情况为例，$a=2$，$b=2$。猜测过程如下： 第一轮，Alice 思考：“我知道 $a=2, a\mid b=2$。我可以推断 $b=0$ 或 $b=2$，但无法确定是哪一个。”因此她说“我不知道”。 第二轮，Bob 思考：“我知道 $b=2, a\mid b=2$。我可以推断 $a=0$ 或 $a=2$。但如果 $a=0$，Alice 在第一轮就会说 $a