池塘里养了n条鱼,从1到n编号,每天等概率地出现两条鱼相互决斗(一条鱼不会和自己决斗),决斗之后必有一条鱼死掉,一条鱼生存。我们用p[i][j]表示第i条鱼打败第j条鱼的概率。那么n-1天后,池塘里只有一条鱼,现在要你求出这最后一条鱼是第i条鱼的概率。
输入
一个数n,接下来是有n行n列,第i行第j列为p[i][j]。输入保证p[i][j]+p[j][i]=1。
输出
输出n行,每行一个数,表示第i条鱼最后生存的概率。每个数保留5位小数(四舍五入)。
输入样例
3
0.000 0.817 0.584 a b c
0.183 0.000 0.665 d e f
0.416 0.335 0.000 g h i
输出样例
0.56440
0.20897
0.22663
数据范围
30%的数据:n<=3
60%的数据:n<=8
100%的数据:n<=18
可以试试在每条鱼的属性里加一项“还活着的概率”
每天,某鱼活着的概率 = 没鱼找它决斗 + 有决斗但赢了。
第一天有没有决斗的概率每条鱼都是均等的,但是一天后是否被决斗的概率就不均等了,还要算上被决斗2条鱼都活着的概率(就是上一天运行的结果)。
然后循环n-1天
就是简单的古典概型问题,直接把每天决斗的概率2/(n-天数)*获胜概率。