给定一个n nn个点的有向完全图,假设有人在t = 1 t=1t=1时刻在节点S SS.接下来每时刻,他都有概率p i j p_{ij}pij从点i ii到点j jj.p i , j = w i , j ∑ k = 1 n w i , k p_{i,j}=\dfrac{w_{i,j}}{\sum_{k=1}^n w_{i,k}}pi,j=∑k=1nwi,kwi,j.
如果他在t tt时刻在点i ii,k + 1 k+1k+1时刻还在点i ii.那么他将一直停留在点i ii.
A i , j A_{i,j}Ai,j表示从i ii点出发,并停留在j jj点的概率.求A i , j m o d 998244353 A_{i,j} \mod 998244353Ai,jmod998244353.并将取模后的矩阵输出.
PS：可以跳转到我的hexo博客上观看。csdn博客目前处于半废弃状态，如果题解有后续修改，未必会第一时间在csdn上进行修改。
[传送门]
首先,我们可以通过分析得到A i , j = ∑ k = 1 n p i , k A k , j A_{i,j}=\sum_{k=1}^n p_{i,k}A_{k,j}Ai,j=∑k=1npi,kAk,j.
A i , j = ∑ k = 1 , k ≠ i n p i , k A k , j 1 A i , i = ∑ k = 1 , k ≠ i n p i , k A k , i + p i , i 2 \begin{aligned} &A_{i,j}=\sum\limits_{k=1,k\not =i}^n p_{i,k}A_{k,j} & 1\\ &A_{i,i}=\sum\limits_{k=1,k\not =i}^n p_{i,k}A_{k,i}+p_{i,i} & 2 \end{aligned}Ai,j=k=1,k=i∑npi,kAk,jAi,i=k=1,k=i∑npi,kAk,i+pi,i12
这里需要注意的是求和号条件那里的k ≠ i k\not = ik=i.当k = i k=ik=i时:
对式1,p i , i A i , j p_{i,i}A_{i,j}pi,iAi,j这一项表示已经停在点i ii了,没法到达点j jj,因此需要去掉.
对式2,后面加的p i , i p_{i,i}pi,i一项就是k = i k=ik=i时的情况.
这个很重要.
观察求和式∑ k = 1 , k ≠ i n p i , k A k , j \sum\limits_{k=1,k\not =i}^n p_{i,k}A_{k,j}k=1,k=i∑npi,kAk,j的形式,其与我们学过的矩阵乘法c i , j = ∑ k a i , k b k , j c_{i,j}=\sum\limits_ka_{i,k}b_{k,j}ci,j=k∑ai,kbk,j十分类似.因此我们可以尝试把这个求和写成两个矩阵相乘.
但是注意我们求和中的k kk和i ii不能取等.这时通常有两个解决办法.
- 容斥,∑ k = 1 , k ≠ i n p i , k A k , j = ∑ k = 1 n p i , k A k , j − p i , i A i , j \sum\limits_{k=1,k\not =i}^n p_{i,k}A_{k,j}=\sum\limits_{k=1}^n p_{i,k}A_{k,j}-p_{i,i}A_{i,j}k=1,k=i∑npi,kAk,j=k=1∑npi,kAk,j−pi,iAi,j.然后把前一项写成矩阵相乘.
- 我们不妨把这个求和看作两个特殊的矩阵相乘.特殊就特殊在相乘后使得p i , i A i , j p_{i,i}A_{i,j}pi,iAi,j自然为0 00,这样∑ k = 1 , k ≠ i n p i , k A k , j = ∑ k = 1 n p i , k A k , j \sum\limits_{k=1,k\not =i}^n p_{i,k}A_{k,j}=\sum\limits_{k=1}^n p_{i,k}A_{k,j}k=1,k=i∑npi,kAk,j=k=1∑npi,kAk,j自然相等.
官方题解中使用的是第二种办法.可能第一种办法也好使?反正我是没试过,不过多少是个思路.
这也就是官方题解中的
构造无自环矩阵W WW,……
无自环指的是去掉有向完全图的自环.这样w i , i w_{i,i}wi,i的值就为0 00,而由p pp的定义,p i , i p_{i,i}pi,i为0 00.这样矩阵P , A P,AP,A(P PP为p i , j p_{i,j}pi,j组成的矩阵)相乘后p i , i A i , j p_{i,i}A_{i,j}pi,iAi,j自然为0 00.
也因此,需要注意下面的W WW表示可能是题目中给出的W WW矩阵,也可能是无自环矩阵W WW.下面用到W WW的地方我都会我会相应地注明.
接下来我们规定一下使用的记号λ i = w i , i , d i = ∑ j = 1 , j ≠ i n w i , j \lambda_i = w_{i,i}, \ \ d_i=\sum\limits_{j=1,j\not=i}^nw_{i,j}λi=wi,i, di=j=1,j=i∑nwi,j.即λ i \lambda_iλi为矩阵W WW的第i ii个对角元.d i d_idi为矩阵W WW第i ii行除对角元以外其他元素的和.这里的W WW是题目中给的W WW而不是我们上面提到的W WW.毕竟我没必要给0起个名
我们使用刚才的记号来重写式子1,2:
A i , j = ∑ k = 1 n w i , k λ i + d i A k , j 3 A i , i = ∑ k = 1 n w i , k λ i + d i A k , i + λ i λ i + d i 4 \begin{aligned} &A_{i,j}=\sum\limits_{k=1}^n \dfrac{w_{i,k}}{\lambda_i+d_i}A_{k,j} & 3\\ &A_{i,i}=\sum\limits_{k=1}^n \dfrac{w_{i,k}}{\lambda_i+d_i}A_{k,i}+\dfrac{\lambda_i}{\lambda_i+d_i} & 4 \end{aligned}Ai,j=k=1∑nλi+diwi,kAk,jAi,i=k=1∑nλi+diwi,kAk,i+λi+diλi34
(这里的W WW是我们之前构造的无自环矩阵W WW,因此这里的求和没有k ≠ i k\not= ik=i的条件)
在刚才,我们已经说明了∑ k = 1 n w i , k λ i + d i A k , j \sum\limits_{k=1}^n \dfrac{w_{i,k}}{\lambda_i+d_i}A_{k,j}k=1∑nλi+diwi,kAk,j可以看成两个矩阵相乘.根据式3,4,我们发现矩阵A AA大概能写成这个样子:
A = M 1 A + M 2 A = M_1A+M_2A=M1A+M2
而从式3,4中可以看出,只有当i = j i=ji=j时M 2 M_2M2的值不为0 00,因此M 2 M_2M2是一个对角阵.
那么M 2 M_2M2这个对角阵具体是什么呢?
令矩阵Λ , D \Lambda, DΛ,D分别为:
Λ = ( λ 1 ⋱ λ n ) , D = ( d 1 ⋱ d n ) \Lambda = \left( \begin{array}{ccc} \lambda_1 & & \\ & \ddots & \\ & & \lambda_n \end{array} \right) ,\ D = \left( \begin{array}{ccc} d_1 & & \\ & \ddots & \\ & & d_n \end{array} \right)Λ=⎝⎛λ1⋱λn⎠⎞, D=⎝⎛d1⋱dn⎠⎞
则
M 2 = ( Λ + D ) − 1 Λ M_2=(\Lambda+D)^{-1}\LambdaM2=(Λ+D)−1Λ
这里需要用到我们的线性代数知识:对对角阵求逆的结果仍是对角阵.对角线上的元素为之前的倒数.并且左乘一个对角阵相当于将其对角线上的元素乘到矩阵的每一行上.
那么,同理,我们也能写出M 1 M_1M1:
M 1 = ( Λ + D ) − 1 W M_1=(\Lambda+D)^{-1}WM1=(Λ+D)−1W
整理一下,就可以得到
A = [ ( Λ + D ) − W ] − 1 Λ A=[(\Lambda+D)-W]^{-1}\LambdaA=[(Λ+D)−W]−1Λ
套一个矩阵求逆板子即可.