Random Walk 2

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$.

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$.

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)
$$

2
2
1 1
1 1
2
1 1
1 0

665496236 332748118
332748118 665496236
1 0
1 0

2021“MINIEYE杯”中国大学生算法设计超级联赛（5）