#P18071. Route Investigation
Route Investigation
Route Investigation
题目描述
一条南北方向的道路由 个路口分成 段,路段从南到北编号为 到 。第 个路口位于第 段与第 段之间。
从南向北通过第 个路口时,遇到红、黄、绿灯的概率分别为 ;反向通过时,概率分别为 。每次通过只会遇到三种颜色之一,各路口的随机等待独立。红灯等待 秒,黄灯等待 秒,绿灯不等待。因此两个方向的三种概率之和均为 。
一次从南端到北端的行程中,到达路段 前的累计等待为 ;一次从北端到南端的行程中,到达路段 前的累计等待为 。这两段路程分别经过路口 与 。
给定每个路段的记录值 。请分别求出 ,对 取模。各路段的询问分别求概率,不要求这些等式同时成立。
保证记录可以由某次行程产生,即存在整数数组 ,满足
$$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.$$输入格式
第一行整数 。接下来 行,第 行给出四个整数 ,分别为 。最后一行给出 个整数 。
;四种百分数均为正整数且不超过 ,满足 、;,并满足上述可实现性保证。
输出格式
输出 个整数,依次表示各路段的概率模 的结果。分数 按 计算模值。
样例 1
输入
2
25 25 25 25
0 1
输出
499122177 748683265
样例中两项概率分别为 和 。