设出每个点的期望r[i]。
如果i点会瞬移到to[i]，则r[i] = r[to[i]]
否则，r[i] = (Σr[j] + (6-cnt)*r[i])/6 + 1 (j为可以往右走的位置，cnt表示其数目，至多6个)
值得注意的是，这个位置最后可能会发现出界了然后原地呆一轮，这种情况一样有贡献，需要注意。
然后列出方程，高斯消元即可。
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 using namespace std; 5 const int MAXN = 105; 6 const double eps = 1e-9; 7 double a[MAXN][MAXN]; 8 int T,cas,n,equ,var; 9 int to[MAXN]; 10 11 int gauss(int n,int m) 12 { 13 int col,row,mxr; 14 for(row=col=1;row<=n&&col<=m;row++,col++) 15 { 16 mxr=row; 17 for(int i=row+1;i<=n;i++) 18 if(fabs(a[i][col])>fabs(a[row][col])) 19 mxr=i; 20 if(mxr!=row) swap(a[row],a[mxr]); 21 if(fabs(a[row][col])<eps) 22 { 23 row--; 24 continue; 25 } 26 for(int i=1;i<=n;i++) //消成上三角矩阵 27 if(i!=row&&fabs(a[i][col])>eps) 28 for(int j=m;j>=col;j--) 29 a[i][j]-=a[row][j]/a[row][col]*a[i][col]; 30 } 31 row--; 32 for(int i=row;i>=1;i--) //回代成对角矩阵 33 { 34 for(int j=i+1;j<=row;j++) 35 a[i][m]-=a[j][m]*a[i][j]; 36 a[i][m]/=a[i][i]; 37 } 38 return row; 39 } 40 int main() 41 { 42 for (scanf("%d",&T);T != 0;T--) 43 { 44 cas++; 45 for (int i = 1;i <= 100;i++) 46 { 47 for (int j = 1;j <= 101;j++) 48 a[i][j] = 0; 49 to[i] = 0; 50 } 51 scanf("%d",&n); 52 int ta,tb; 53 for (int i = 1;i <= n;i++) 54 { 55 scanf("%d%d",&ta,&tb); 56 to[ta] = tb; 57 } 58 for (int i = 1;i <= 99;i++) 59 { 60 if (to[i] != 0) 61 { 62 a[i][to[i]] = -1.0; 63 a[i][101] = 0.0; 64 a[i][i] = 1.0; 65 } 66 else 67 { 68 int cnt = min(6,100 - i); 69 a[i][i] = 1.0 - (6.0 - cnt) / 6.0; 70 for (int j = i + 1;j <= min(100,i + 6);j++) 71 a[i][j] = -1.0 / 6; 72 a[i][101] = 1.0; 73 } 74 } 75 a[100][100] = 1.0; 76 a[100][101] = 0.0; 77 gauss(100,101); 78 printf("Case %d: %.6lf ",cas,a[1][101]); 79 } 80 return 0; 81 }