← 返回题目列表

Codeforces · 16/E

E. 鱼

中文机器翻译题面 查看原题

n条鱼,编号从1到n,生活在湖里。每天都会有一对鱼相遇,并且彼此相遇的概率是相同的。如果两条索引为 i 和 j 的鱼相遇,第一条鱼将以 aij 的概率吃掉第二条鱼,第二条鱼将以 aji = 1 - aij 的概率吃掉第一条鱼。所描述的过程一直持续到湖中至少有两条鱼为止。对于每条鱼,找出它成为湖中最后一条鱼的概率。

输入

第一行包含整数 n (1 ≤ n ≤ 18) — 湖中的鱼量。接下来是 n 行,每行有 n 个实数——矩阵 a。 aij (0 ≤ aij ≤ 1) — 索引为 i 的鱼吃掉索引为 j 的鱼的概率。保证主对角线仅包含零,对于其他元素,以下为真:aij = 1 - aji。所有实数的小数点后不超过 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