UOJ Logo Universal Online Judge

UOJ

#390. 【UNR #3】百鸽笼

统计

在UOJ管理员群里一共有$N$个管理员,为了容纳这些管理员,vfk准备了$N + 1$个鸽笼。

为了节省空间,vfk把这些鸽笼堆了起来,共有$n$列,第$i$列放了$a_i$个鸽笼,满足 $\sum a_i = N+1$。

每当UR结束,管理员们就会按照编号从小到大的顺序回到鸽笼里,每个管理员回来的时候,会先等概率的在所有还有剩余的鸽笼的列中随机一个列,然后住到这列剩下的鸽笼里编号最小的一个中。

现在$N$个管理员都回笼了之后,还有一列会空出一个鸽笼。你能对于每一列,求出这一列有空鸽笼的概率吗?

百鸽笼

输入格式

第一行一个整数$n$。

第二行$n$个正整数$a_i$。

输出格式

一行$n$个整数表示答案对$998244353$取模的结果。

样例一

input

3
1 1 1

output

332748118 332748118 332748118

explanation

都是$\frac{1}{3}$。

样例二

input

3
1 2 3

output

771790773 824938042 399759892

样例三

见样例数据下载。

限制与约定

对于所有数据,均满足 $1\le a_i \le 30,1 \le n \le 30,\sum a_i \ge 1$。

子任务分值限制
1$10$$1 \leq a_i \leq 3, n \leq 10$
2$10$$1 \leq a_i \leq 5. n \leq 30$
3$20$$1 \leq a_i \leq 30, n \leq 10$
4$20$$1 \leq a_i \leq 30, n \leq 20$
5$40$$1 \leq a_i \leq 30, n \leq 30$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载