高斯消元好题

如果暴力地，令f[i][k]表示到i，有k条命的概率，就没法做了。

转化题意

生命取决于经过陷阱的个数

把这个看成一步

所以考虑从一个陷阱到另一个陷阱，不经过其他陷阱的概率p[i][j]

当然1出发到其他陷阱的概率也要得到。

然后相当于有一个新图，

从1出发，走k-1步恰好到n的概率

 

暴力方法：

枚举一个出发点s，

则$P_x=\sum_{v&&v!=trap}P_v/deg_v+P(x is a start)$

特别地，v是s也可以转移（虽然s可能是陷阱，但是是出发点）

O(n^4)

 

考虑优化

其实所有的系数都是一样的。只是常数项不一样。即$P(x is a start)$不同。

什么，你说对于某些s是trap，但是作为出发点可以转移这里不同的s条件不同？

我们可以枚举s的出点v，直接把v作为出发点，概率是1/deg(s)

 

所以，我们可以把常数项扔到等号后面，堆成长度为陷阱数量的向量。

一起带着消即可。

 

#include
     
      #define numb (ch^'0')#define il inline#define reg register intusing namespace std;typedef long long ll;template
      
       il void rd(T &x){    x=0;char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
       
        il void prt(T a[],int st,int nd){    for(reg i=st;i<=nd;++i) cout<
        
         <<" ";cout<
         
          fabs(f[id][i])) id=j;        }        if(id!=i){            for(reg j=i;j<=n+c;++j){                swap(f[i][j],f[id][j]);            }        }        for(reg j=i+1;j<=n;++j){            if(fabs(f[j][i])>0){                double lp=f[j][i]/f[i][i];                for(reg k=i;k<=n+c;++k){                    f[j][k]-=f[i][k]*lp;                }            }        }    }    if(typ!=1){        for(reg i=n;i>=1;--i){            for(reg j=i+1;j<=n;++j){                if(fabs(f[i][j])>0){                    for(reg k=n+1;k<=n+c;++k){                        f[i][k]-=f[i][j]*p[k-n][j];                    }                }            }            for(reg k=n+1;k<=n+c;++k){                p[k-n][i]=f[i][k]/f[i][i];            }        }    }else{//        for(reg i=1;i<=n;++i){//        for(reg j=1;j<=n+c;++j){//            cout<
          
           <<" ";// }cout<
           
            =1;--i){ for(reg j=i+1;j<=n;++j){ if(fabs(f[i][j])>0){ f[i][n+1]-=f[i][j]*p[0][j]; } } p[0][i]=f[i][n+1]/f[i][i]; } }}struct tr{ double a[105][105]; tr(){memset(a,0,sizeof a);} void init(){ for(reg k=0;k<=num;++k){ a[k][k]=1.00; } } tr friend operator *(const tr &a,const tr &b){ tr c; for(reg k=0;k<=num;++k){ for(reg i=0;i<=num;++i){ for(reg j=0;j<=num;++j){ c.a[i][j]+=a.a[i][k]*b.a[k][j]; } } } return c; }}S,B;tr qm(tr B,int y){ tr ret;ret.init(); while(y){ if(y&1) ret=ret*B; B=B*B; y>>=1; } return ret;}int main(){ rd(n);rd(m);rd(T); for(reg i=1;i<=n;++i){ rd(has[i]); if(has[i]) mem[++num]=i,id[i]=num; } int x,y; for(reg i=1;i<=m;++i){ rd(x);rd(y); ++du[x];++du[y]; ++con[x][y];++con[y][x]; } for(reg i=1;i<=n;++i){ f[i][i]=1.000; for(reg j=1;j<=n;++j){ if(j==i) continue; if(!has[j]&&con[i][j]){ f[i][j]=-(double)con[i][j]/du[j]; } } if(i==1) f[i][n+1]=1.00; } guass(1,1); // for(reg i=1;i<=num;++i){// cout<<" memi "<
            <<" : "<
             
              <<" "<
              
               <
              
             
           
          
         
        
       
      
     

只关心生命值多少

题意转化！变成新图！

系数相同，带着常数一起消除！