[CF 446D] DZY Loves Games

CodeForces 446D

设$f_{i, j}$ 为从$i$开始游走,走到的第一个陷阱是$j$的概率,则有$$f_{x, i} = \sum \limits_{y\in \text{son}(x)}\frac{f_{y, i}}{deg_{x}}$$

这个显然可以高斯消元,消元的时候将所有的放在一起消,就可以$O(n ^ 3)$得到所有的$f_{i, j}$了

然后设$g_{i, j}$为走到的第$i$个陷阱为$j$的概率,则有

$$g_{1, j} = f_{1, j}$$

$$g_{i, j} = \sum \limits_{k = 1}^a g_{i-1, k} \cdot f_{k, j}$$

矩阵加速即可

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

#define pb push_back
#define MAX_N 510
#define MAX_A 110

struct Matrix{
	int n, m;
	double a[MAX_A][MAX_A];
	Matrix(int n, int m) : n(n), m(m){
		memset(a, 0, sizeof(a));
	}
	double *operator [](int x){
		return a[x];
	}
};

Matrix operator *(Matrix x, Matrix y){
	Matrix z(x.n, y.m);
	for(int i = 1; i <= x.n; i++)
		for(int k = 1; k <= x.m; k++)
			for(int j = 1; j <= y.m; j++)
				z[i][j] += x[i][k] * y[k][j];
	return z;
}

Matrix ksm(Matrix x, int y){
	Matrix z(x.n, x.n);
	for(int i = 1; i <= x.n; i++)
		z[i][i] = 1;
	for(; y; y >>= 1, x = x * x)
		if(y & 1) z = x * z;
	return z;
}

int n, m, K, deg[MAX_N], a[MAX_A], typ[MAX_N];
double A[MAX_N][MAX_N + MAX_A];
std::vector<int> to[MAX_N];

int main(){
	scanf("%d%d%d", &n, &m, &K);
	for(int i = 1; i <= n; i++){
		scanf("%d", &typ[i]);
		if(typ[i]) a[++a[0]] = i;
	}
	for(int i = 1, x, y; i <= m; i++){
		scanf("%d%d", &x, &y);
		deg[x]++, deg[y]++;
		to[x].pb(y), to[y].pb(x);	
	}
	for(int i = 1; i <= n; i++){
		if(!typ[i]){
			for(auto j: to[i])
				A[i][j] += 1.0 / deg[i];
			A[i][i] = -1;
		}else{
			A[i][i] = 1;
			for(int j = 1; j <= a[0]; j++) if(a[j] == i)
				A[i][n+j] = 1;
		}
	}
	int lim = a[0] + n;
	double t;
	for(int i = 1; i <= n; i++){
		t = A[i][i];
		for(int j = 1; j <= lim; j++)
			A[i][j] /= t;
		for(int j = i + 1; j <= n; j++){
			t = A[j][i] / A[i][i];
			for(int k = 1; k <= lim; k++)
				A[j][k] -= A[i][k] * t;
		}
	}
	for(int i = n; i; i--)
		for(int j = i - 1; j; j--)
			for(int k = n + 1; k <= lim; k++)
				A[j][k] -= A[j][i] * A[i][k];
	Matrix x(1, a[0]), y(a[0], a[0]);
	for(int i = 1; i <= a[0]; i++)
		x[1][i] = A[1][n + i];
	for(int i = 1; i <= a[0]; i++)
		for(int j = 1; j <= a[0]; j++){
			for(auto k: to[a[i]])
				y[i][j] += A[k][n + j];
			y[i][j] /= deg[a[i]];
		}
	x = x * ksm(y, K - 2);
	printf("%.6lf\n", x[1][a[0]]);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注