题意

给定一个长度为 $n$ 的数组 $s$。随机选择两个可以相等的位置 $i_a$ 与 $i_b$。设 $a = s_{i_a}, b = s_{i_b}$。

现在有 Alice 和 Bob 在猜 $a$ 与 $b$ 的大小关系。

从 Alice 开始轮流，每次轮到的人可以说“我不知道相对大小”然后轮给另一个人，或者说“我知道了”然后给出结果。

Alice 和 Bob 都是绝顶聪明并且只在有确凿把握时猜测，现在你要输出两人进行的期望轮数（每说一句话即一轮），对 $998244353$ 取模。

$n = 2 \times 10^5, 0 \leq s_i < 2^{30}$

题解

若 $a = b$，例如 $a = b = \left(1101\right)_2$。

1. A 确定 $a \geq b$
2. B 知道了 $a$ 的最高位是 $1$，否则 A 在第一次就知道 $a < b$。但现在 B 也只知道 $a \geq b$。
3. A 知道 $b$ 的前两高位都是 $1$，否则 B 在第二次就知道 $a > b$。而因为 $a | b$ 的第三位是 $0$，所以 $b$ 的第三位是 $0$。但现在 A 也还是只知道 $a \geq b$。
4. B 知道了 $a = b$

于是可以发现，若 $a = b$，则需要 $\operatorname{popcount}\left(a\right) + 1$ 轮。

$a \neq b$ 也可以举例分析，这里直接给出结论：
若 $a < b$，设 $a$ 最高是 $0$ 的位是第 $i$ 高位，会经过 $i + \left[i \bmod 2 = 0\right]$ 轮。
若 $a > b$，设 $b$ 最高是 $0$ 的位是第 $i$ 高位，会经过 $i + \left[i \bmod 2 = 1\right]$ 轮。

于是在 $s$ 中枚举 $a$，再枚举 $a$ 与 $b$ 的 最长公共前缀 长度，并使用字典树计数即可。