传送门

题意

给出一张图，LL从一个点等概率走到上下左右位置，询问LL从宿舍走到餐厅的步数期望

分析

该题是一道高斯消元+期望的题目

难点在于构造矩阵，我们发现以下结论

设某点走到餐厅的期望为Ek

1.当该点为餐厅，Ek=0

2.\(Ek=\sum_{i=1}^{cnt}Enexti-1\)

我们先BFS将可达点标号，再构建矩阵，再高斯消元，最后A[vis[sx][sy]][id]为所求解

trick

代码

#include<bits/stdc++.h>

using namespace std;

const int M = 202;

const double eps = 1e-8;

int equ, var;

double a[M][M], x[M];

void Gauss ()

{

    int i, j, k, col, max_r;

    for (k = 0, col = 0; k < equ && col < var; k++, col++)

    {

        max_r = k;

        for (i = k+1; i < equ; i++)if (fabs (a[i][col]) > fabs (a[max_r][col])) max_r = i;

        if (k != max_r)

        {

            for (j = col; j < var; j++)swap (a[k][j], a[max_r][j]);

            swap (x[k], x[max_r]);

        }

        for (j = col+1; j < var; j++) a[k][j] /= a[k][col]; x[k] /= a[k][col];

        a[k][col] = 1;

        for (i = 0; i < equ; i++) if (i != k)

        {

            x[i] -= x[k] * a[i][k];

            for (j = col+1; j < var; j++) a[i][j] -= a[k][j] * a[i][col];

            a[i][col] = 0;

        }

    }

}

//has[x]表示人在x点时的变量号，因为我们只用可达状态建立方程，所以需要编号

int has[M], vis[M], id, e, n, m;

double p[M], sum;

int bfs (int u)

{

    memset (has, -1, sizeof(has));

    memset (a, 0, sizeof(a));           //忘记初始化WA勒，以后得注意

    memset (vis, 0, sizeof(vis));

    int v, i, flag = 0;id=0;

    queue<int> q;

    q.push (u);

    has[u] = id++;

    while (!q.empty ())

    {

        u = q.front ();q.pop ();

        if (vis[u]) continue;

        vis[u] = 1;

        if (u == e || u == n-e)     //终点有两个，你懂的~

        {

            a[has[u]][has[u]] = 1;

            x[has[u]] = 0;

            flag = 1;

            continue;

        }

        //E[x] = sum ((E[x+i]+i) * p[i])

        // ----> E[x] - sum(p[i]*E[x+i]) = sum(i*p[i])

        a[has[u]][has[u]] = 1;x[has[u]] = sum;

        for (i = 1; i <= m; i++)if(fabs(p[i])>eps)

        {

            //非常重要！概率为0，该状态可能无法到达，如果还去访问并建立方程会导致无解

            v = (u + i) % n;

            if (has[v] == -1) has[v] = id++;

            a[has[u]][has[v]] -= p[i];

            q.push (v);

        }

    }

    return flag;

}

int main()

{

    int t, s, d, i;

    for(scanf("%d",&t);t--;)

    {

        scanf ("%d%d%d%d%d", &n, &m, &e, &s, &d);

        n = 2*(n-1);sum = 0;

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

        {

            scanf ("%lf", p+i);

            p[i] = p[i] / 100;

            sum += p[i] * i;

        }

        if (s == e){puts ("0.00");continue;}

        //一开始向左，起点要变

        if (d > 0) s = (n - s) % n;

        if (!bfs (s)){puts ("Impossible !");continue;}

        equ = var = id;

        Gauss ();

        printf ("%.2f\n", x[has[s]]);

    }

    return 0;

}