F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Random Walk 2

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 391    Accepted Submission(s): 173


Problem Description
Penguin finds an directed complete graph with n vertices.

Notice that the graph has loops and no multiple edges.

Now he is going to walk on the graph randomly:

1.Suppose that he starts on the node $S$(now time $t=1$).

2.Then every time he will go from node $i$ to node $j$ with the probability $\displaystyle P[i][j]=\frac{W[i][j]}{\sum_{k=1}^nW[i][k]}(\sum_{k=1}^nW[i][k]>0)$.

3.If he is on the node $i$ at the time $t$ and also on the node $i$ at the time $t+1$,he will stay on node $i$ forever.

Penguin wants you to help him calculate the probability $A[i][j]$ that he starts on node $i$ and stops on node $j$.

Please compute $A[i][j]$ modulo $998244353$.

 

Input
The first line contains an integer $T(T \le 10)$. Then $T$ test cases follow.

For each test case the first line of input contains integer $n\in[1,300]$.

The $i$th of the following $n$ lines contains $n$ integers $W[i][j]\in[0,10^5]$.

$\sum n \le 2500$.
 

Output
For each test case there are $n$ lines.

The $i$th of $n$ lines contains $n$ integers $A[i][j]$ modulo $998244353$.

[Sample 1 Explanation]

For node $i$ there is a $\frac{1}{2}$ probability to stay on node $i$ and a $\frac{1}{2}$ probability to leave node $i$ .

So we can get

$$
A=\left(
\begin{array}{cc}
\frac{2}{3} & \frac{1}{3} \\
\frac{1}{3} & \frac{2}{3} \\
\end{array}
\right)
$$

Compute $A[i][j]$ modulo $998244353$

$$
A=\left(\begin{array}{cc}665496236 & 332748118 \\332748118 & 665496236 \\\end{array}\right)
$$
 

Sample Input
2 2 1 1 1 1 2 1 1 1 0
 

Sample Output
665496236 332748118 332748118 665496236 1 0 1 0
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 16:42:29, Gzip enabled