#P18071. Route Investigation

Route Investigation

Route Investigation

题目描述

一条南北方向的道路由 n−1n-1 个路口分成 nn 段,路段从南到北编号为 11 到 nn。第 ii 个路口位于第 ii 段与第 i+1i+1 段之间。

从南向北通过第 ii 个路口时,遇到红、黄、绿灯的概率分别为 ri,yi,gir_i,y_i,g_i;反向通过时,概率分别为 ri′,yi′,gi′r'_i,y'_i,g'_i。每次通过只会遇到三种颜色之一,各路口的随机等待独立。红灯等待 11 秒,黄灯等待 22 秒,绿灯不等待。因此两个方向的三种概率之和均为 11。

一次从南端到北端的行程中,到达路段 ii 前的累计等待为 aia_i;一次从北端到南端的行程中,到达路段 ii 前的累计等待为 bib_i。这两段路程分别经过路口 1,…,i−11,\ldots,i-1 与 n−1,…,in-1,\ldots,i。

给定每个路段的记录值 cic_i。请分别求出 Pr⁡[ai+bi=ci]\Pr[a_i+b_i=c_i],对 998244353998244353 取模。各路段的询问分别求概率,不要求这些等式同时成立。

保证记录可以由某次行程产生,即存在整数数组 a,ba,b,满足

$$a_1=b_n=0,\qquad a_i\le a_{i+1}\le a_i+2,\qquad b_{i+1}\le b_i\le b_{i+1}+2,\qquad a_i+b_i=c_i.$$

输入格式

第一行整数 nn。接下来 n−1n-1 行,第 ii 行给出四个整数 Ri,Yi,Ri′,Yi′R_i,Y_i,R'_i,Y'_i,分别为 100ri,100yi,100ri′,100yi′100r_i,100y_i,100r'_i,100y'_i。最后一行给出 nn 个整数 c1,…,cnc_1,\ldots,c_n。

2≤n≤2×1052\le n\le2\times10^5;四种百分数均为正整数且不超过 100100,满足 Ri+Yi<100R_i+Y_i<100、Ri′+Yi′<100R'_i+Y'_i<100;0≤ci≤2n0\le c_i\le2n,并满足上述可实现性保证。

输出格式

输出 nn 个整数,依次表示各路段的概率模 998244353998244353 的结果。分数 u/vu/v 按 u⋅v−1u\cdot v^{-1} 计算模值。

样例 1

输入

2
25 25 25 25
0 1

输出

499122177 748683265

样例中两项概率分别为 1/21/2 和 1/41/4。