A6195. Fish
编程题
普及+/提高
知识点
题目描述
湖中生活着 $n$ 条鱼，编号从 $1$ 到 $n$。每天，恰好有一对鱼相遇，每一对鱼相遇的概率相同。如果编号为 $i$ 和 $j$ 的两条鱼相遇，编号为 $i$ 的鱼以概率 $a_{ij}$ 吃掉编号为 $j$ 的鱼，编号为 $j$ 的鱼以概率 $a_{ji}=1-a_{ij}$ 吃掉编号为 $i$ 的鱼。上述过程会一直持续，直到湖中只剩下一条鱼。请计算每条鱼成为湖中最后一条鱼的概率。
输入格式
第一行包含一个整数 $n$（$1 \leq n \leq 18$），表示湖中的鱼的数量。接下来有 $n$ 行，每行包含 $n$ 个实数，构成矩阵 $a$。$a_{ij}$（$0 \leq a_{ij} \leq 1$）表示编号为 $i$ 的鱼吃掉编号为 $j$ 的鱼的概率。保证主对角线上的元素全为 $0$，且对于其他元素有 $a_{ij} = 1 - a_{ji}$。所有实数均保留不超过 $6$ 位小数。
输出格式
输出 $n$ 个用空格分隔的实数，每个实数精确到 $6$ 位小数。第 $i$ 个数表示编号为 $i$ 的鱼成为湖中最后一条鱼的概率。
输入输出样例
输入 #1
2 0 0.5 0.5 0
输出 #1
0.500000 0.500000
输入 #2
5 0 1 1 1 1 0 0 0.5 0.5 0.5 0 0.5 0 0.5 0.5 0 0.5 0.5 0 0.5 0 0.5 0.5 0.5 0
输出 #2
1.000000 0.000000 0.000000 0.000000 0.000000