← 返回题目列表

AtCoder · agc056_e

E. 奶酪

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

分数: 1600 点

问题陈述

有一个周长 N。 在这个圆周上,按顺时针方向测量,到某个固定点的距离为 x 有坐标 x.

对于每个整数 i (0 \leq i \leq N-1),坐标处有鼠标 i+0.5.

Snuke会扔一块奶酪 N-1 次。 更具体地说,他重复了以下内容 N-1 次。

  • 选择一个整数 y (0 \leq y \leq N-1)随机,其中 y=i 被概率选择 A_i %。这个选择每次都是独立做出的。
  • 然后,从坐标处扔奶酪 y。奶酪在圆周上沿顺时针方向移动。当奶酪遇到老鼠时,就会发生以下情况。
    • 如果老鼠没有吃奶酪:
      • 它有概率吃掉奶酪 1/2。奶酪消失了。
      • 它与概率无关 1/2.
    • 如果老鼠已经吃掉了奶酪:
      • 它什么也没做。
  • 奶酪沿着圆周不断移动,直到被老鼠吃掉。

之后 N-1 扔奶酪,就会有一只老鼠从未吃过奶酪。 对于每个 k=0,1,\cdots,N-1,求鼠标在坐标处的概率 k+0.5 最终没有吃奶酪,取模 998244353.

如何表示概率模 998244353

我们可以证明所讨论的每个概率始终是有理数。另外,在这个问题的约束下,当该数字表示为不可约分数时 \frac{P}{Q},我们还可以证明 Q \neq 0 \pmod{998244353}。因此,有一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。用这个回答 R.

约束

  • 1 \leq N \leq 40
  • 0 \leq A_i
  • \sum_{0 \leq i \leq N-1} A_i = 100
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_0 A_1 \cdots A_{N-1}

输出

打印以下问题的答案 k=0,1,\cdots,N-1 位于一行,中间有空格。 始终选择


样本输入 1

2
0 100

示例输出 1

665496236 332748118

y=1 。当从这个点扔奶酪时,会发生以下情况。

  • 有概率 1/2,鼠标在坐标处 1.5 吃了它。
  • 有概率 1/4,鼠标在坐标处 0.5 吃了它。
  • 有概率 1/8,鼠标在坐标处 1.5 吃了它。
  • 有概率 1/16,鼠标在坐标处 0.5 吃了它。
  • \vdots

最后,坐标处的老鼠 0.5 和 1.5 有概率吃掉这个奶酪 1/3 和 2/3。

因此,他们最终有可能不吃奶酪 2/3 和 1/3。


示例输入 2

2
50 50

示例输出 2

499122177 499122177

示例输入 3

10
1 2 3 4 5 6 7 8 9 55

示例输出 3

333507001 91405664 419217284 757959653 974851434 806873643 112668439 378659755 979030842 137048051