#P15828. [2025年山东集训第三轮]Kanade的水杯

[2025年山东集训第三轮]Kanade的水杯

Kanade 的水杯(bottle)

题目背景

你是否有认真聆听过,水从杯壁上留下,触碰液面的声音?

Kanade 喜欢聆听这样的声音:杂乱无章中又包含着几段绝妙的旋律。只要能捕捉其中的瞬间,便是创作的极佳灵感。

每当 Kanade 向自己最喜欢的猫猫日清拉面中注入开水,她便会将剩下的水于杯中反复地倾倒。

拿出 nn 个容量各异的杯子,在第一个杯子里注满水,创作的过程就开始了。从左到右,依次拿起每一个,随意地将其中的水向任意一个杯子里倒入,便是一次创意浮现的过程。

当然,不会做家务的 Kanade 会在杯子的水溢出之前停下……她可不想手忙脚乱地拿着抹布拯救自己的电脑!

题目描述

有 nn 个瓶子排成一排,编号为 1,2,…,n1,2,\ldots,n,第 ii 个瓶子的容积为 aia_i。最开始第 11 个瓶子是满的,其余瓶子是空的。

我们按照从左到右的顺序对每个瓶子依次执行以下操作:

  • 在其余的 n−1n-1 个瓶子中等概率选择一个。
  • 将当前瓶子的水倒入选中的瓶子,直到当前瓶子为空或者选中的瓶子已满。

给定序列 aa,你需要输出每个瓶子在所有操作后期望盛有多少水。

因为处理浮点数比较复杂,你只需要输出答案对 998244353998244353 取模后的结果即可。

输入格式

第一行输入一个整数 nn。

第二行输入 nn 个整数 aia_i。

输出格式

输出 nn 行,第 ii 行输出第 ii 个瓶子在所有操作后期望盛有水的体积对 998244353998244353 取模的值。

样例 1 输入

2
1 1

样例 1 输出

1
0

样例 1 解释

水一定从第 11 个瓶子倒向第二个瓶子再倒回去,因此第一个瓶子必定为满,第二个瓶子必定为空。

样例 2 输入

3
3 1 2

样例 2 输出

623902723
623902721
748683265

样例 2 解释

三个瓶子的期望体积为 198\frac{19}{8},38\frac{3}{8} 和 14\frac{1}{4}。

样例 3 输入

9
9 9 8 2 4 4 3 5 3

样例 3 输出

304464287
164086171
361005467
588475930
898938779
983453531
155241138
69810681
467501437

数据范围

本题共 2525 个测试点,全部测试点满足 2≤n≤1052\le n\le 10^5,1≤ai≤n1\le a_i\le n。

测试点 数据范围
11 n≤2n\le 2
22 n≤3n\le 3
3∼43\sim 4 n≤8n\le 8
5∼65\sim 6 n≤16n\le 16
7∼87\sim 8 n≤50n\le 50
9∼119\sim 11 n≤300n\le 300
12∼1412\sim 14 n≤2×103n\le 2\times 10^3
15∼2015\sim 20 n≤5×104n\le 5\times 10^4
2121 ai=1a_i=1
22∼2322\sim 23 ai≥ai+1a_i\ge a_{i+1}
24∼2524\sim 25 无特殊限制