CDOJ 1330 柱爷与远古法阵 概率DP,高斯消元，卡精度，极度恶心
众所周知，柱爷的数学非常好，尤其擅长概率论！
某日柱爷在喵蛤蛤村散步，无意间踏入了远古法阵！
法阵很奇怪，是一个长度为N
的走廊，初始时柱爷在最左边，现在柱爷要到最右边去!
柱爷的行动方式如下:
每个回合柱爷会投一次骰子，根据骰子上的点数X，柱爷会相应的往右边移动X步.
骰子的数值是 1到6，取到每面的概率相同
在某些位置可能有传送门，一旦柱爷在该回合结束后在这个位置上，会被强制传送到传送门的另外一边
传送门是单向的,同时每个位置不会有超过1个传送门,同时不会存在a→b,b→c这种情况
在任意时刻柱爷都必须保证在法阵内，也就说如果在这一回合结束后柱爷的位置在法阵外，那么这回合柱爷将什么都不做
那么请问柱爷到达最右边的期望回合数是多少呢？或者是永远都无法到达？ Input
第一行两个整数N ,M
，分别表示法阵的长度和传送门的数量
接下来M 行，每行两个整数u,v，表示从u到v
有一扇传送门
数据保证:
1≤N≤3000≤M≤[N−22]
1
//CDOJ 1330 Guass消元 #include <bits/stdc++.h> using namespace std; const int maxn = 305; #define eps 1e-14 int n, m, dp[maxn]; long double a[maxn][maxn]; int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++){ int x, y; scanf("%d%d", &x, &y); dp[x] = y; //传送门 } //构造增广矩阵 a[n][n] = 1.0; a[n][n+1] = 0; for(int i = 1; i < n; i++){ a[i][i] = 6.0; if(dp[i]) a[i][dp[i]] = -6.0; else{ a[i][n+1] = 6.0; for(int j = 1; j <= 6; j++){ if(i+j > n) a[i][i] -= 1.0; else a[i][i+j] -= 1.0; } } } //Guass for(int i = 1; i <= n; i++){ int p = i; for(int j = i + 1; j <= n; j++){ if(fabs(a[j][i]) > eps) p = j; } if(fabs(a[p][i]) > eps){ for(int j = i; j <= n + 1; j++) swap(a[i][j], a[p][j]); for(int j = i + 1; j <= n; j++){ if(fabs(a[j][i]) > eps){ long double k = a[j][i] / a[i][i]; for(int t = i; t <= n + 1; t++) a[j][t] -= a[i][t] * k; } } } } //回带 第i个未知数的值就是a[i][n+1] for(int i = n; i >= 1; i--){ for(int j = i + 1; j <= n; j++){ if(fabs(a[i][j]) > eps){ a[i][n+1] -= a[j][n+1]*a[i][j]; } } if(abs(a[i][i]) <= eps && abs(a[i][n+1]) > eps){ puts("-1"); return 0; } a[i][n+1] /= a[i][i]; } PRintf("%.12f\n", (double)a[1][n+1]); return 0; }