期望，$dp$，高斯消元。
这题需要一些骚操作。首先要将问题的所有情况全部简化为起点开始向右移动（到头了从$0$再继续开始）。例如$n=4$时，将时间轴扩充为$0$ $1$ $2$ $3$ $4$ $3$ $2$ $1$。这样，$d=0$和$d=-1$的时候，就直接是一直往右走就可以了。$d=1$的时候需要另外找一下起点。
因为有可能$p[1]=0$，所以有一些格子本身就走不到，也就是不存在这个状态，所以需要事先预处理好哪些格子可以走到，哪些格子走不到。
$dp$方程比较好写：$dp[i]=sum(dp[i+j]+j)*p[j]$。
对于目标状态或者无法到达的状态，不需要写$dp$方程。其余状态的方程中，目标状态前面的系数均为$0$。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-10; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } } int T,n,m,y,x,d,len; int L[500]; double p[500]; bool f[500]; int const maxn = 500; double a[maxn][maxn],ans[maxn]; bool free_x[maxn]; int sgn(double x) { return (x>eps)-(x<-eps); } int gauss() { int i, j, k; int max_r; int col; double temp; int free_x_num; int free_index; int equ = len,var = len; col = 0; memset(free_x,true,sizeof(free_x)); memset(ans,0,sizeof ans); for (k = 0; k < equ && col < var; k++, col++) { max_r = k; for (i = k + 1; i < equ; i++) { if (sgn(fabs(a[i][col]) - fabs(a[max_r][col]))>0) max_r = i; } if (max_r != k) { for (j = k; j < var + 1; j++) swap(a[k][j], a[max_r][j]); } if (sgn(a[k][col]) == 0 ) { k--; continue; } for (i = k + 1; i < equ; i++) { if (sgn(a[i][col])!=0) { double t = a[i][col] / a[k][col]; for (j = col; j < var + 1; j++) { a[i][j] = a[i][j] - a[k][j] * t; } } } } for(i=k;i<equ;i++) if(sgn(a[i][col])!=0) {return 0;} if (k < var) { for (i = k - 1; i >= 0; i--) { free_x_num = 0; for (j = 0; j < var; j++) { if ( sgn(a[i][j])!=0 && free_x[j]){ free_x_num++, free_index = j; } } if(free_x_num>1) continue; temp = a[i][var]; for (j = 0; j < var; j++) { if (sgn(a[i][j])!=0 && j != free_index) temp -= a[i][j] * ans[j]; } ans[free_index] = temp / a[i][free_index]; free_x[free_index] = 0; } return var - k; } for (i = var - 1; i >= 0; i--) { temp = a[i][var]; for (j = i + 1; j < var; j++) { if (sgn(a[i][j])!=0) temp -= a[i][j] * ans[j]; } ans[i] = temp / a[i][i]; } return 1; } void bfs() { memset(f,0,sizeof f); queue<int>q; q.push(x); f[x]=1; while(!q.empty()) { int x = q.front(); q.pop(); for(int i=1;i<=m;i++) { if(p[i]<eps) continue; if(f[(x+i)%len]==0) { f[(x+i)%len]=1; q.push((x+i)%len); } } } } int main() { scanf("%d",&T); while(T--) { scanf("%d%d%d%d%d",&n,&m,&y,&x,&d); for(int i=1;i<=m;i++) { int x; scanf("%d",&x); p[i]=1.0*x/100; if(p[i]<eps) p[i]=0; } for(int i=0;i<n;i++) L[i]=i; len=n; int tmp=n-2 ,pos = n; while(tmp>=1) L[pos++]=tmp--; len=pos; if(d==1) { for(int i=n;i<=2*(n-1);i++) if(L[i]==x) { x=i; break; } } bfs(); bool fail=1; for(int i=0;i<len;i++) if(L[i]==y&&f[i]==1) fail=0; if(fail==1) { printf("Impossible ! "); continue; } memset(a,0,sizeof a); for(int i=0;i<len;i++) { if(L[i]==y) continue; if(f[i]==0) continue; a[i][i]=-1; for(int j=1;j<=m;j++) { if(L[(i+j)%len]==y) a[i][(i+j)%len]=0; else a[i][(i+j)%len]+=p[j]; a[i][len]-=p[j]*j; } } gauss(); printf("%.2f ",ans[x]); } return 0; }