题目大意

有一个这样的环：0,1,2…n,n-1,n-2…2,1,0，走 i 步的概率是 p[i], 求终点走到起点的期望。

题目分析

很显然 $$ f[i]= \sum (p[k]*(f[i+k]+k)) $$
高斯消元搞一搞啊。

代码

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int T,tot,n,m,v,u,d;
int g[205],q[205];
double p[205],a[205][205],eps=1e-6;
void bfs(){
    int i,he=1,ta=1,to;
    q[he]=u;g[u]=tot++;
    while(he<=ta){
        for(i=1;i<=m;i++){
            if(fabs(p[i])<eps)continue;
            to=(q[he]+i)%n;
            if(g[to]==-1){g[to]=tot++;q[++ta]=to;}
        }
        he++;
    }
}
bool guss(){
    int i,j,k,bj;double t;
    for(k=0;k<tot;k++){
        bj=k;
        for(i=k+1;i<tot;i++)
            if(fabs(a[i][k])>fabs(a[bj][k]))bj=i;
        if(fabs(a[bj][k])<eps)return 0;
        if(bj!=k)for(j=k;j<=tot;j++)swap(a[k][j],a[bj][j]);
        t=a[k][k];
        for(j=k;j<=tot;j++)a[k][j]/=t;
        for(i=0;i<tot;i++)if(i!=k){
            if(fabs(a[i][k])<eps)continue;
            t=a[i][k];
            for(j=k;j<=tot;j++)a[i][j]-=t*a[k][j];
        }
    }
    return 1;
}
int main()
{
    int i,j;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d%d",&n,&m,&v,&u,&d);
        for(i=1;i<=m;i++){scanf("%lf",&p[i]);p[i]/=100.0;}
        if(u==v){printf("0.00\n");continue;}
        n=n*2-2;if(d==1&&u!=0)u=n-u;
        for(i=0;i<n;i++)g[i]=-1;
        tot=0;bfs();
        if(g[v]==-1&&g[n-v]==-1){printf("Impossible !\n");continue;}
        memset(a,0,sizeof(a));
        for(i=0;i<n;i++){
            if(g[i]==-1)continue;
            a[g[i]][g[i]]=1.0;
            if(i==v||i==n-v)continue;
            for(j=1;j<=m;j++){
                if(fabs(p[j])<eps)continue;
                int to=(i+j)%n;
                if(g[to]==-1)continue;
                a[g[i]][g[to]]-=p[j];a[g[i]][tot]+=p[j]*j;
            }
        }
        if(!guss()){printf("Impossible !\n");continue;}
        printf("%.2lf\n",a[g[u]][tot]);
    }
    return 0;
}