我们都知道矩阵树求得实际是
[sum_{T}prod_{ein T}w_e
]
现在有一个简单的问题，给定一张带权图，要求所有生成树边权积的和，这个怎么求
很简单我们还是构造两个矩阵(A,B)
对于图中的每一个点(u)，记(d_u)为和这个点相连的边权和，那么(a_{u,u}=d_u)
对于图中的每一条边((u,v,w))，有(b_{u,v}=b_{v,u}=w)
我们设(C=A-B)，之后求出(C)的任意一个余子式的值就好了
现在回到这道题，我们要求的东西是
[sum_{T}prod_{ein T}w_eprod_{e
otin T}1-w_e
]
我们只能对在生成树里的边求积，于是考虑选择一条边后的贡献
显然有一个(w_e)的贡献，同时在(prod_{e=1}^m1-w_e)中有一个消去了一个(1-w_e)，产生了一个(frac{1}{1-w_e})的贡献
于是我们现在可以把柿子化成这样
[prod_{i=1}^m(1-w_i)sum_{T}prod_{ein T}frac{w_e}{1-w_e}
]
这样的话一旦不选择一条边，就能在前面的那个(prod_{i=1}^m(1-w_i)) 里消去(1-w_e)的贡献，最后就只留下了不选的边
还有几个实现的时候需要注意的地方，就是一条边一定会出现的时候，我们得给这个概率减小一点，避免除以(0)的情况
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
const double eps=1e-10;
const int maxn=55;
int n;
double a[maxn][maxn],b[maxn][maxn];
inline int check(double a,double b) {if(a+eps>b&&a-eps<b) return 1;return 0;}
int main() {
scanf("%d",&n);
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n;j++)
scanf("%lf",&b[i][j]);
double ans=1;
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n;j++) {
if(i==j) continue;
if(check(b[i][j],0)) continue;
if(check(b[i][j],1)) b[i][j]-=eps;
if(i<j) ans*=(1-b[i][j]);
a[i][j]-=(b[i][j])/(1-b[i][j]);
a[i][i]+=(b[i][j])/(1-b[i][j]);
}
int o=0;
for(re int i=1;i<n;i++) {
int p;
for(p=i;p<n;++p) if(!check(a[p][i],0)) break;
if(p!=i) std::swap(a[p],a[i]),o^=1;
for(re int j=i+1;j<n;j++) {
double t=a[j][i]/a[i][i];
for(re int k=i;k<n;k++)
a[j][k]-=a[i][k]*t;
}
}
for(re int i=1;i<n;i++) ans*=a[i][i];
if(o) printf("%.10lf
",-1.0*ans);
else printf("%.10lf
",ans);
return 0;
}