「NOIP2020 模拟赛 B 组 Day2」漫步校园

校园有$n$个景点，景点被编号为$1$到$n$。第$i$个景点会被赋予一个$0$到$d-1$的之间的整数权值 ，表示该景点的类型。

校园里阡陌交通，大一新生小$K$第一时刻在景点$1$，然后他开始随意地漫步，假设某时刻他在第$i$个景点，则下一时刻，小$K$会按照$p_{i,j}$的概率随机选择一个$j$，然后移动到景点$j$（保证$sum _{j=1}^n p_{i,j}=1$，也有可能$i=j$ ）。

在漫步$N$个时刻以后，小$K$会把他所经过的景点类型全部下来，这样他会得到一个长度为$N$的数列$S$，$S$中每个数都在$0$到$d-1$之间。

小$K$很想研究，他最后得到的数列的概率分布。假设他所有得到的数列为 $S_1,S_2,cdots,S_m$，那么令$q_i=P(S=S_i)$表示他得到的数列是$S_i$的概率。

他想知道$sum _{i=1}^m q_i^2$的值，请你帮他解决这个问题。

这题重点是将求$q_i^2$转化为同时走两条路径，且类型同为$S_i$的概率

$F[i][u][v]$表示走了$i$步，目前两条路径的结尾景点分别为$u$，$v$，同时限制景点$u$，$v$类型相同

转移即$F[i+1][u][v]+=F[i][x][y] imes p_{x,u} imes p_{y,v}$，当然$x，y$类型相同

复杂度$O(Nn^4)$

优化的话就是矩阵快速幂一下，对于不同的$i$转移相同，计算矩阵$P^{N-1}$

$P[w(x,y)][w(u,v)]=p[x][u]*p[y][v]，w(x,y)=(x-1)*n+y$

复杂度是$O(n^6logN)$

#include <bits/stdc++.h>

using namespace std;


int n, sqrn, N, d, a[16];

double p[16][16], ans;

struct Matrix {
    double s[256][256];
    Matrix operator * (const Matrix &g) const {
        Matrix ret;
        for (int i = 0; i < sqrn; i++)
            for (int j = 0; j < sqrn; j++) ret.s[i][j] = 0;
        for (int i = 0; i < sqrn; i++)
            for (int k = 0; k < sqrn; k++) if (s[i][k] != 0)
                for (int j = 0; j < sqrn; j++) ret.s[i][j] += s[i][k] * g.s[k][j];
        return ret;
    }
} t, res;

void fpow(int y) {
    for (int i = 0; i < sqrn; i++)
        for (int j = 0; j < sqrn; j++) res.s[i][j] = 0;
    for (int i = 0; i < sqrn; i++) res.s[i][i] = 1;
    while (y) {
        if (y & 1) res = res * t;
        t = t * t;
        y >>= 1;
    }
}

int main() {
    freopen("walk.in", "r", stdin);
    freopen("walk.out", "w", stdout);
    scanf("%d%d", &n, &N); sqrn = n * n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) scanf("%lf", &p[i][j]);
    scanf("%d", &d);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) if (a[i] == a[j])
            for (int u = 0; u < n; u++)
                for (int v = 0; v < n; v++) if (a[u] == a[v]) t.s[i * n + j][u * n + v] = p[i][u] * p[j][v];
    fpow(N - 1);
    for (int i = 0; i < sqrn; i++) ans += res.s[0][i];
    printf("%.12lf
", ans);
    return 0;
}