这题主要有两种做法：1种是用逆矩阵，转移时无须高斯消元。2是将常数项回代。这里主要介绍第一种。

首先题里少个条件：点权非负。设f [ i ][ j ]表示hp为i时，到达j点的期望次数。

那么若点权为正，直接转移：f [ i + w[ j ] ][ i ]对f [ i ][ j ]的贡献为f[ i+w[j] ]/d[ i ]（d[i]表示点i的出度）

若点权为0，则需高斯消元，单次消元复杂度（n^3）显然会炸，我们考虑优化。、

对于高斯消元，有一个结论：系数矩阵*答案矩阵=常数矩阵（用方程组的定义来理解，挺简单的，虽然我想了好久）

将系数矩阵换到右边，就变成了 答案矩阵=常数矩阵×系数矩阵的逆

对于本题而言，系数矩阵是不变的，变化的只有常数矩阵，而常数矩阵O（m）即可处理出，因此我们可以预处理出系数矩阵的逆矩阵,之后每次只需将逆矩阵与常数矩阵相乘，而常数矩阵为一个列向量，每次乘法复杂度O（n^2）,总复杂度O（(n^2+m)hp+n^3）。

对于矩阵求逆只需将原矩阵高斯消元，然后不管什么操作都对一个单位矩阵做同等变换，单位矩阵在消完元后也就变成了原矩阵的逆矩阵。

 

1 #include
      
        2 #define eps 1e-8 3 using namespace std; 4 int n,m,hp,a[155],tot,to[10005],fi[155],ne[10005],du[155]; 5 double c[155][155],b[155][155],d[155][155],f[10005][152],dp[152],ans; 6 inline void add(int x,int y) 7 { 8     ne[++tot]=fi[x]; 9     fi[x]=tot;10     to[tot]=y;11 }12 int main()13 {14     scanf("%d%d%d",&n,&m,&hp);15     for(int i=1;i<=n;i++)16         scanf("%d",&a[i]);17     for(int i=1,x,y;i<=m;i++)18     {19         scanf("%d%d",&x,&y);20         add(x,y),du[x]++;21         if(x!=y)22             add(y,x),du[y]++;23     }24     for(int i=1;i
       
        fabs(c[k][i]))40                   k=j;41           for(int j=1;j<=n;j++)swap(c[i][j],c[k][j]),swap(b[i][j],b[k][j]);42           if(fabs(c[i][i])
        
         a[y])67                     f[i-a[y]][y]-=1.0*dp[j]/du[j];68             }69             dp[j]=0;70         }71         dp[n]=0;72     }73     printf("%.8lf",ans);74     return 0;75 }