← 返回题目列表

Codeforces · 2203/E

E. 概率卡牌游戏

中文机器翻译题面 查看原题

Alice 和 Bob 有一副牌,最初是空的。他们玩一个持续 $$$m$$$ 轮的游戏。在第 $$$i$$$ 轮中,发生以下事件:

  • 一张值为$$$a_i$$$的牌被添加到牌组中(保证牌组中之前没有具有该值的牌);
  • 如果牌组中的牌少于$$$3$$$,则该回合结束;
  • 否则,爱丽丝从牌组中选择一张牌;
  • 然后鲍勃选择一张牌(知道爱丽丝选择了哪张牌;他不能选择同一张牌);
  • 从剩下的$$$i-2$$$牌中统一随机再选择一张牌;
  • 最后,所有三张选定的牌都返回到牌堆中。

令 $$$a$$$ 为 Alice 卡上的值,$$$b$$$ 为 Bob 卡上的值,$$$c$$$ 为随机选择的卡上的值。然后鲍勃收到:

  • $$$0$$$ 点如果 $$$|a - c| \le |b - c|$$$ (其中 $$$|x|$$$ 表示 $$$x$$$ 的绝对值);
  • 如果卡 $$$c$$$ 位于卡 $$$a$$$ 和 $$$b$$$ 之间,则 $$$0$$$ 点(即 $$$a \lt c \lt b$$$ 或 $$$b \lt c \lt a$$$);
  • $$$|b-c|$$$ 点否则。

Alice 每轮的目标是最小化 Bob 的预期分数,而 Bob 的目标是最大化它。如果爱丽丝和鲍勃都发挥最佳,鲍勃每轮的预期得分是多少?打印预期分数模 $$$998\,244\,353$$$。

请注意,玩家最小化或最大化预期分数的实际值,而不是对 $$$998\,244\,353$$$ 取模的结果。

输入

第一行包含一个整数 ($$$3 \le m \le 2 \cdot 10^5$$$) — 轮数。

第二行包含 $$$m$$$ 整数 $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le 10^{12}$$$;所有 $$$a_i$$$ 都是不同的)。

输出

打印 $$$m-2$$$ 整数:第 $$$i$$$ 个数字应等于鲍勃在本轮 $$$i+2$$$ 中的预期得分,且双方玩家的最优玩法以 $$$998\,244\,353$$$ 为模(即,让预期得分为不可约分数 $$$\frac{x}{y}$$$;您需要输出 $$$x \cdot y^{-1} \bmod 998\,244\,353$$$,其中 $$$y^{-1}$$$ 是一个数字 $$$y \cdot y^{-1} \bmod 998\,244\,353 = 1$$$)。

请注意,玩家最小化或最大化预期分数的实际值,而不是对 $$$998\,244\,353$$$ 取模的结果。

示例

输入
复制

5
1 10 3 11 7

输出
复制

0
499122177
665496236

输入
复制

6
23 7 11 24 10 28

输出
复制

0
499122177
1
748683266

输入
复制

9
4 10 7 1 16 5 9 12 2

输出
复制

0
499122178
2
499122178
798595484
831870296
427819010

注意

在第一个示例中,答案是:$$$0、\frac{1}{2}、\frac{2}{3}$$$。

在第二个示例中,答案为:$$$0, \frac{1}{2}, 1, \frac{5}{4}$$$。

在第三个示例中,答案为:$$$0、\frac{3}{2}、2、\frac{3}{2}、\frac{8}{5}、\frac{11}{6}、\frac{11}{7}$$$。