UOJ Logo Universal Online Judge

UOJ

#823. 【UR #26】铁轨回收

附件下载 统计

在藏蓝铁路的碧水湖大桥落成之际,一群铁路工程蚤聚在一起,庆祝这一伟大的建筑工程。

在修建过程中,有一些多余的铁轨。为了环保(省钱),废弃的铁轨会被存到仓库等待下次利用。

有 $N$ 个路段,每个路段有一个废弃铁轨专属仓库。其中,第 $i$ 个路段余下的铁轨长度为 $A_i$ km,而该路段的专属仓库最多能存 $B_i$ km。

工程蚤们会按照 $i = 1 \sim n - 1$ 的顺序进行操作,来将废弃的铁轨进行集中:

  • 关闭第 $i$ 个路段的仓库;
  • 从 $[i+1,n]$ 中随机选择一个整数 $j$,把第 $i$ 个路段的仓库中的铁轨全部放到第 $j$ 个路段的仓库中;
  • 如果超出容量,则弃置多出的部分(也就是 $A_j \leftarrow \min(A_i+A_j,B_j)$)。

现在,对于每个 $i \in [0,B_n]$,问第 $n$ 个路段的仓库最终有 $i$ km 铁轨的概率。你只需要输出答案模 $998244353$ 后的值即可。

输入格式

第一行一个正整数,表示 $n$。

接下来 $n$ 行,每行两个非负整数,表示 $A_i$ 和 $B_i$。

输出格式

一行 $B_n+1$ 个整数,分别表示 $i=0,i=1,...,i=B_n$ 的答案模 $998244353$ 后的值。可以证明答案一定可以被表示为 $\frac{a}{b}$ 的形式,其中 $\gcd(a,b)=1$,你需要输出整数 $c$ 满足 $bc\equiv a\bmod 998244353$。

样例一

input

3
1 2
1 1
0 3

output

0 499122177 499122177 0

样例二

input

8
1 3
1 2
0 1
0 2
1 6
0 1
3 3
0 10

output

0 0 0 748683265 376718405 301057821 570029216 0 0 0 0

样例三/四/五/六

见下发文件。

限制与约定

对于 $100\%$ 的数据,$1\leq n\leq 50,0 \le A_i \le B_i \le 30$。

子任务编号 $n\leq$ $B_i \le$ 分值
1 $10$ $30$ $10$
2 $50$ $0$ $10$
3 $1$ $10$
4 $4$ $20$
5 $10$ $20$
6 $18$ $10$
7 $30$ $20$

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

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