#1047 : Random Tree（概率+prufer计数+卡精度）

http://hihocoder.com/problemset/problem/1047

题解：

• 考虑枚举一条边((x,y))，看它在((u,v))路径上的概率是多少？

• 当((x,y)=(u,v))，不难算出概率即是((x,y))在生成树上的概率，即(frac{n-1}{n*(n-1)/2}=frac{2}{n})

• 当((x,y))和((u,v))有一个公共点时，假设是(x=u)，发现问题转为(v)在(y)的子树里的概率，显然是(frac{1}{2})，再乘上(frac{2}{n})即可。

• 当((x,y))和((u,v))没有交集时，大胆猜想概率是(frac{1}{2})，可惜它错了。

• 此时把问题转一转，因为所有的这样的边都是一样的，变成求((u,v))的期望长度，再除掉可能的边数即可。

• (P((x,y)在(u,v)上)=frac{sum_{i=4}^{n} ~ P((u,v)路径点数=i)*(i-3)}{n*(n-1)/2-2(n-1)+1})

• (P((u,v)路径点数=i))可以用方案数除以总方案数(n^{n-2})得到。

• 设(F(n,m))等于(n)个点，(m)个森林，(1..m)属于不同森林的方案数，可以视作一开始一个(m)大小的联通块，由生成树计数(sum_{prufer} prod_{联通块x}siz[x]^{x的prufer序列中的出现次数+1})

• 即可得到公式：(F(n,m)=m*n^{n-1-m})

• 方案数(=F(n,i)*P(n-2,i-2))

• 卡精度，拆式子得：(sum_{i=4}^n frac{(n-2)!}{(n-i)!*n^{i-1}}*i*(i-3))，可以倒着枚举(i)，然后每次乘一个数除以一个数。

• 需要用long double精度才够。

Code：

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;

#define db long double

const int N = 1005;

int n;
db a[N][N], b[N];

db calc(int n) {
	if(n <= 3) return 0;
	db ans = 0, s = 1;
	fo(i, 1, n - 2) s = s * i / n;
	s /= n;
	ans += s * n * (n - 3);
	fd(i, n - 1, 4) {
		s *= n;
		s /= (n - i);
		ans += s * i * (i - 3);
	}
	return ans;
}

int main() {
	scanf("%d", &n);
	fo(i, 1, n) fo(j, 1, n) scanf("%Lf", &a[i][j]), b[i] += a[i][j];
	db sum = 0;
	fo(i, 1, n) sum += b[i];
	sum /= 2;
	db v = calc(n);
	if(n > 3) v /= n * (n - 1) / 2 - 2 * (n - 1) + 1;
	fo(i, 1, n) {
		fo(j, 1, n) {
			db v2 = sum - b[i] - b[j] + a[i][j];
			db ans = v2 * v + (b[i] + b[j] - 2 * a[i][j]) / n + a[i][j] * 2 / n;
			if(i == j) ans = 0;
			pp("%.9Lf
", ans);
		}
	}
}