题目链接

 题意

  n个结点编号为0到n-1组成一个环。如果当前在结点x，那么它等概率的走向 (x+1)mod n,(x-1) 问从0到x的期望步数是多少

 分析

   高斯消元解决带环概率DP

   f[i]表示当前在i结点，走到x结点得期望步数。f[x]=0。

   f[i]=f[i+1]*0.5+f[i-1]*0.5+1

   整理得到 1=f[i+1]*0.5+f[i-1]*0.5-f[i] 所以得到了n个方程组有n个未知量，然后通过高斯消元求解。

   

1    #include 
      
        2     #include 
       
         3     #include 
        
          4     #include 
         
           5     #include 
          
            6  7     using namespace std; 8     const int maxn=1000+100; 9     double f[maxn],a[maxn][maxn];10     int T,n,x;11     void Gauss(){12         int k,col;13         for(k=0,col=0;k
           
            
             fabs(a[max_k][col]))max_k=i;17 }18 if(max_k!=k){19 for(int i=0;i<=n;i++)20 swap(a[k][i],a[max_k][i]);21 }22 if(a[k][col]==0){23 k--;24 continue;25 }26 for(int i=k+1;i
             
              =0;i--){36 double g=a[i][n];37 for(int j=i+1;j