期望dp+高斯消元+bfs——hdu4418

高斯消元又弄了半天。。

注意只要能建立矩阵，那就必定有解，所以高斯消元里可以直接return 1

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

const double esp = 1e-;

int n,m,x,y,d;

double p[maxn],a[maxn][maxn],b[maxn];

int equ,var;

int Gauss(){

    for(int i=;i<n;i++){

        int maxr=i;

        for(int j=i+;j<n;j++)

            if(fabs(a[j][i])>fabs(a[maxr][i]))

                maxr=j;

        if(fabs(a[maxr][i])<esp)continue;

        if(maxr!=i)

            swap(a[maxr],a[i]);swap(b[maxr],b[i]);

        for(int j=i+;j<n;j++){

            if(fabs(a[j][i])<esp)continue;

            double rate=a[j][i]/a[i][i];

            for(int k=i;k<n;k++)

                a[j][k]-=rate*a[i][k];

            b[j]-=rate*b[i];

        }

    }

    for(int i=n-;i>=;i--){

        if(fabs(a[i][i])<esp)continue;

        for(int j=i+;j<n;j++)

            b[i]-=a[i][j]*b[j];

        b[i]/=a[i][i];

    }

    return ;

}

int id[maxn],cnt;

void bfs(int s){

    memset(id,-,sizeof id);

    cnt=;

    queue<int>q;

    q.push(s);id[s]=cnt++;

    while(q.size()){

        int x=q.front();q.pop();

        for(int i=;i<=m;i++){

            if(fabs(p[i])<esp)continue;

            int y=(x+i)%n;

            if(id[y]==-)

                q.push(y),id[y]=cnt++;

        }

    }

}

int main(){

    int t;cin>>t;

    while(t--){

        scanf("%d%d%d%d%d",&n,&m,&y,&x,&d);

        for(int i=;i<=m;i++)

            scanf("%lf",&p[i]),p[i]/=;

        if(x==y){puts("0.00");continue;}

        n=*(n-);

        if(d==)x=n-x;

        bfs(x);

        if(id[y]==- && id[n-y]==-){

            puts("Impossible !");continue;

        }

        equ=var=cnt;

        memset(a,,sizeof a);

        memset(b,,sizeof b);

        for(int i=;i<n;i++){

            if(id[i]==-)continue;

            a[id[i]][id[i]]=;

            if(i==y || i==n-y)continue;//到了终点y

            for(int j=;j<=m;j++){

                int y=(i+j)%n;

                if(id[y]!=-){

                    a[id[i]][id[y]]-=p[j];

                    b[id[i]]+=j*p[j];

                }

            }

        }

        if(Gauss())

            printf("%.2lf\n",b[id[x]]);

        else printf("Impossible !\n");

    }

}