有一天，夯哥走到了一個大迷宮中，這個迷宮一共有$n$列$m$行個房間其中每組相鄰房間之間都有一扇只能單向往右或往下走的門，現在一開始你在最左上角的房間，而出口在最右下角的房間，由於你並不知道該怎麼走才能到達出口，因此你在每間房間每單位時間可能會做三件事中的一種: 往下走、往右走、停留在原地猶豫。現在告訴你對於每間房間$(i,j)$，夯哥往右走的機率為$x_{ij}\%$，往下走的機率為$y_{ij}\%$，而停留在原地的機率是$1-x_{ij}\%-y_{ij}\%$，請問XX走到終點的期望時間為何(?)
已知每單位時間夯哥的決定皆為獨立事件，且可以證明答案一定為有理數可以用最簡分數$\frac{P}{Q}$表示，請輸出$PQ^{-1}\mod 998244353$，其中$Q^{-1}$代表$Q$的乘法反元素。
第一行輸入兩個正整數$n,m\;(1\le n,m\le 1000)$代表列數與行數。
接下來$n$行每行輸入$m$個整數，其中第$i$列$j$行的整數$x_{ij}\;(0\le x_{ij}\le 100)$，如題目所述。
再接下來$n$行每行輸入$m$個整數，其中第$i$列$j$行的整數$y_{ij}\;(0\le x_{ij}\le 100)$，如題目所述。
保證所有測資滿足$0\lt x_{ij}+y_{ij}\le 100\;,\;\forall 1\le i\le n\;,\;1\le j\le m$，且$x_{im}=0\;,\;y_{nj}=0$，$x_{nm},y_{nm}$不重要不受上述限制。
每筆測資輸出一個數字$PQ^{-1}\mod 998244353$代表夯哥走到終點的期望時間。
範例測資 #1: 1 2 50 0 0 0 範例測資 #2: 2 2 25 0 100 0 25 10 0 0 範例測資 #3: 1 1 0 0 範例測資 #4: 3 3 12 43 0 84 0 0 46 58 0 57 31 10 9 87 64 0 0 0
範例測資 #1: 2 範例測資 #2: 499122184 範例測資 #3: 0 範例測資 #4: 668539087
令從$(i,j)$走到終點$(n,m)$的期望時間為$d(i,j)$，那麼$d(i,j)=...$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||