P7105 "C.E.L.U-01" Access Control

Once, abruce went to the computer lab **quite** early, and then... he waited outside for 35 minutes... So he thought of this question: The door of the computer lab is locked. There are $n$ students who all need to get in, and to enter they must have an access card. However, some students may go together. For a group that goes together, as long as at least one person brings an access card, they will not be awkwardly locked outside. Now the teacher is finally going to hand out access cards, but how many cards should be given out?

We simplify the problem in the background. You are given $n$ points, and for any two points $i,j$, there is an undirected edge between them with probability $p_{i,j}$. Find the expected number of connected components in the graph.

The first line contains an integer $n$. Lines $2$ to $n+1$ each contain $n$ real numbers, representing $p_{i,j}$. The testdata guarantees that for any $1\le i \le n$, $p_{i,i}=0$; for any $1\le i,j \le n$, $p_{i,j}=p_{j,i}$; $0\le p_{i,j}\le1$. The input real numbers have at most $3$ digits after the decimal point.

Output one real number in a single line, representing the expected number of connected components. Your answer is considered correct if the **absolute** error from the standard answer does not exceed $10^{-4}$.

Sample Explanation 1: The following eight cases each occur with probability $\dfrac{1}{8}$.  The numbers of connected components are $3,2,2,2,1,1,1,1$. So the expectation is $\dfrac{1}{8}\times3+\dfrac{3}{8}\times2+\dfrac{4}{8}\times1=\dfrac{13}{8}=1.625$ Constraints: | Test ID | $n$ | Special Property | | :-: | :-: | :-: | | $1\sim3$ | $\le4$ | None | | $4$ | $\le8$ | $p_{i,j}=0$ or $p_{i,j}=1$ | | $5\sim6$ | $\le8$ | When $i\not=j$, $p_{i,j}=0.5$ | | $7\sim8$ | $\le8$ | None | | $9\sim10$ | $\le11$ | None | | $11\sim12$ | $\le14$ | None | Translated by ChatGPT 5