[BZOJ 3640]JC的小苹果
逆矩阵文明，，，
很显然我们可以定义一个状态\(f[i][j]\)表示当前血量为\(i\)走到\(j\)的概率，然后肥肠爆歉这个东西没法DP（可能会有的点的伤害为0，这样可以凿出来环）。考虑高消，这个东西有个好处是不可能从血量低的到血量高的状态，所以可以从大到小枚举血量，这样各层事独立的，复杂度比直接高消降低了很少。可惜复杂度为\(O(sn^3)\)（设血量为\(s\)），会T掉。
考虑转移的过程，转移时等价于解这样一个方程：
\[
\begin{aligned}
a_{11}x_{1} + a_{12}x_{2} + \ldots + a_{1n}x_{n} &= c_1\\
a_{21}x_{1} + a_{22}x_{2} + \ldots + a_{2n}x_{n} &= c_2\\
&\ldots\\
a_{n1}x_{1} + a_{n2}x_{2} + \ldots + a_{nn}x_{n} &= c_n
\end{aligned}
\]
其中的未知数\(x\)事我们要求的东西，\(c\)表示从高血量状态转移过来的概率（这个可以视作常数）。根据友矩阵那一套理论，这一系列方程等价于以下等式：
\[
\begin{bmatrix}
a_{11} & a_{12} & \ldots & a_{1n}\\
a_{21} & a_{22} & \ldots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \ldots & a_{nn}
\end{bmatrix}
\begin{bmatrix}
x_{1}\\ x_{2} \\ \vdots \\ x_{n}
\end{bmatrix}
=
\begin{bmatrix}
c_1\\ c_2\\ \vdots\\ c_n
\end{bmatrix}
\]
不妨将之简记为\(AB = C\)，其中我们只有\(B\)不知道，要求的也是\(B\)。我们除一下就可以得到\(B = A^{-1}C\)，然后我们还发现每一层的\(A\)都是一样的，所以每一层的\(A^{-1}\)也都是一样的，预处理即可。这样转移部分的复杂度就变成了\(O(sn^2)\)（矩阵乘法在这里事方阵乘列向量）。
至于逆矩阵的求法，我们知道对矩阵做初等变化也就等价于乘上另一个矩阵。因此，我们将一个矩阵\(A\)用类似于高消的手段消为单位阵\(I\)，所做的初等变换也就等价于乘上\(A^{-1}\)。我们对一个单位阵\(I\)作用上一样的操作，也就等于给这个单位阵乘上了\(A^{-1}\)，这样我们就得到了\(A^{-1}\)。
代码：
/**************************************************************
Problem: 3640
User: danihao123
Language: C++
Result: Accepted
Time:8708 ms
Memory:13416 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <map>
int n, m, hp;
const int maxn = 151, maxm = 5005;
const int maxh = 10005;
typedef double R;
typedef R Mat[maxn][maxn];
Mat D, F;
void calc_inv() {
for(int i = 1; i <= n; i ++) {
F[i][i] = 1;
}
for(int i = 1; i <= n; i ++) {
int r = i;
for(int j = i + 1; j <= n; j ++) {
if(fabs(D[j][i]) > fabs(D[r][i])) {
r = j;
}
}
// assert(r > -1);
if(r != i) {
for(int j = 1; j <= n; j ++) {
std::swap(D[r][j], D[i][j]);
std::swap(F[r][j], F[i][j]);
}
}
R bs = D[i][i];
for(int j = 1; j <= n; j ++) {
D[i][j] /= bs; F[i][j] /= bs;
}
for(int k = 1; k <= n; k ++) {
if(k != i) {
R rate = D[k][i];
for(int j = 1; j <= n; j ++) {
D[k][j] -= rate * D[i][j];
F[k][j] -= rate * F[i][j];
}
}
}
}
}
void matrix_mul(const Mat &A, const Mat &B, int a, int b, int c, Mat &res) {
static Mat C;
for(int i = 1; i <= a; i ++) {
for(int j = 1; j <= c; j ++) {
C[i][j] = 0;
}
}
for(int i = 1; i <= a; i ++) {
for(int j = 1; j <= c; j ++) {
for(int k = 1; k <= b; k ++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
for(int i = 1; i <= a; i ++) {
for(int j = 1; j <= c; j ++) {
res[i][j] = C[i][j];
}
}
}
int first[maxn], deg[maxn];
int next[maxm << 1], to[maxm << 1];
int gcnt = 0;
void add_edge(int u, int v) {
gcnt ++;
next[gcnt] = first[u]; first[u] = gcnt;
to[gcnt] = v;
}
void ins_edge(int u, int v) {
deg[u] ++;
add_edge(u, v);
if(u != v) {
deg[v] ++;
add_edge(v, u);
}
}
int atk[maxn];
R f[maxh][maxn];
R solve() {
for(int i = 1; i <= n; i ++) {
D[i][i] = 1.00;
}
for(int i = 1; i < n; i ++) {
for(int j = first[i]; j; j = next[j]) {
int v = to[j];
if(!atk[v]) {
D[v][i] -= 1.00 / (R(deg[i]));
}
}
}
calc_inv();
R ans = 0; static Mat C;
f[hp][1] = 1.00;
for(int i = hp; i >= 1; i --) {
for(int j = 1; j <= n; j ++) {
C[j][1] = f[i][j];
}
matrix_mul(F, C, n, n, 1, C);
for(int j = 1; j < n; j ++) {
for(int e = first[j]; e; e = next[e]) {
int v = to[e];
if(atk[v] > 0 && i - atk[v] > 0) {
f[i - atk[v]][v] += C[j][1] / (R(deg[j]));
}
}
}
ans += C[n][1];
}
return ans;
}
int main() {
scanf("%d%d%d", &n, &m, &hp);
for(int i = 1; i <= n; i ++) {
scanf("%d", &atk[i]);
}
for(int i = 1; i <= m; i ++) {
int u, v; scanf("%d%d", &u, &v);
ins_edge(u, v);
}
printf("%.8lf\n", solve());
return 0;
}
