This problem is very easy. There's a graph of $N$
nodes. Each edge $u-v$
($u >= v ; u = v$
is possible, i.e. a loop) has some probability $P(u, v)$
of existing. Given these probabilities, you have to find out the expected number of connected components of such a graph created according to the probabilities.
The first line contains an integer $N$
. After that, there are $N$
lines of input. The ith line has i numbers on it. jth number of ith line represents the probability $P(i, j)$
in percentage. All input numbers are integers.
$1 \leq N \leq 17$
$0 \leq P(i, j) \leq 100$
The expected number of connected components can be represented as $P/Q$
, where $P$
and $Q$
are natural numbers. Output $P \times Q^{-1}$
mod $998244353$
.
Input | Output |
---|---|
2 50 50 50 | 499122178 |
When the 1-2 edge exists, there is 1 connected component. Otherwise there are 2 components. So the answer is (1+2)1/2 = 3/2 which is 32-1 = 499122178 in mod 998244353. |
Input | Output |
---|---|
3 50 50 100 50 100 0 | 748683266 |