bzoj#P3150. [CTSC2013]猴子

[CTSC2013]猴子

tip:SPJ暂未配置

题目描述

小 Q 和小 M 最近发明了一种卡牌游戏,叫猴子大战。

游戏最初小 Q 和小 M 各会取得一部分猴子牌。每局游戏,他们两个需要分别等概率地从自己的猴子牌中抽取一张进行战斗。获胜的一方将获得双方的猴子牌。如果一方获得了所有的猴子牌,则该方获得整场游戏的胜利。否则游戏将一直进行下去。

在进行了若干场比赛以后,小 Q 和小 M 算出了一张胜率表,为每张猴子牌之间进行战斗双方获胜的概率。由于每场战斗一定会决出胜负,而且胜率不受先后顺序的影响,因此对于任意的两张猴子牌 AABBAA 战胜 BB 的概率加 BB 战胜 AA 的概率为 11

由于自己老是输给小 M ,小 Q 开始怀疑自己每次拿到的猴子牌是否能获得胜利。他希望求出自己拿到的每种猴子牌组合的获胜的概率。

由于小 Q 接下来还有在 CD 市体育中心数以万计的运动计划,因此这个问题只能交给你来解决了。

输入格式

输入的第一行包含两个正整数 nnmm ,表示猴子牌的总张数和需要求的猴子牌组合的个数。

接下来有 nn 行,每行包含 nn 个实数,每个实数保留了两位小数。这 nn 行中,其中第 ii 行第 jj 列的数为 Pi,jP_{i,j} ,表示第 ii 张猴子牌战胜第 jj 张猴子牌的概率。保证 Pi,j+Pj,i=1P_{i,j} + P_{j,i} = 1 。特别地, Pi,i=0.5P_{i,i} = 0.5 ,没有特殊意义。

最后有 mm 行。每行包含一个长度为 nn 的无空格分隔的 01串 ,表示一个猴子牌的组合。其中第 ii 个字符如果为 0 ,表示最初第 ii 张牌在小 M 处,否则表示在小 Q 处。

输出格式

输出 mm 行,每行一个实数,四舍五入保留八位小数(请强制输出八位浮点数),依次表示每个给定的猴子牌组合下小 Q 获胜的概率。

样例输入

3 4
0.50 0.60 0.40
0.40 0.50 0.70
0.60 0.30 0.50
110
011
111
000

样例输出

0.71304348
0.66086957
1.00000000

数据规模与约定

对于 100%100\% 的数据,保证 1n100,1mn21 \le n \le 100,1 \le m \le n^20Pi,j10 ≤ P_{i,j} ≤ 1 , Pi,jP_{i,j} 恰好包含 22 位小数,且 Pi,j+Pj,i=1P_{i,j} + P_{j,i} = 1 。表示猴子牌组合的 01串 长度均为 nn ,且不含其他字符。

评分方式

你的答案的每一行如果与我们给定的参考答案的差别均不超过 2×1062 \times 10^{-6} ,则获得该测试点的得分,否则不得分。

参考答案保证与真实值的差别不超过 10810 ^ {-8} ,因此如果你输出的答案保证与真实值差别不超过 2×1061082 \times 10^{-6} \sim 10 ^ {-8} ,才能保证正确。

题目来源

vfleaking提供spj