分数: 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