题目即
$$
\sum_{T}\prod_{e\in T}p_e\prod_{e\notin T}(1-p_e)=\sum_{T}\prod_{e\in T}p_e\frac{\prod_{e}(1-p_e)}{\prod_{e\in T}(1-p_e)}=\prod_{e}(1-p_e)\sum_{T}\prod_{e\in T}\frac{p_e}{1-p_e}
$$
最右边那个可以直接用矩阵树定理求。
$p_e$ 是 $0$ 或者 $1$ 的时候加上一个偏移量调节一下就好了。
因为输出是小数,所以行列式不用辗转相除,很方便。
#include<bits/stdc++.h>
using namespace std;
const int N=55;
const double eps=1e-8;
int n;
double e[N][N],d[N][N];
int main() {
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) {
scanf("%lf",&e[i][j]);
if(e[i][j]<eps) e[i][j]=eps;
else if(e[i][j]>1.-eps) e[i][j]=1.-eps;
}
double ans=1;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j) ans=ans*(1.-e[i][j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) e[i][j]=e[i][j]/(1.-e[i][j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) d[i][i]+=e[i][j];
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) e[i][j]=d[i][j]-e[i][j];
for(int i=1;i<n;++i) {
for(int j=i+1;j<n;++j) {
double div=e[j][i]/e[i][i];
for(int l=i;l<n;++l) e[j][l]=e[j][l]-e[i][l]*div;
}
}
for(int i=1;i<n;++i) ans*=e[i][i];
printf("%.12lf",ans);
}
STO orz
太强了!!!
铸币吧你