bzoj#P3150. [CTSC2013]猴子
[CTSC2013]猴子
tip:SPJ暂未配置
题目描述
小 Q 和小 M 最近发明了一种卡牌游戏,叫猴子大战。
游戏最初小 Q 和小 M 各会取得一部分猴子牌。每局游戏,他们两个需要分别等概率地从自己的猴子牌中抽取一张进行战斗。获胜的一方将获得双方的猴子牌。如果一方获得了所有的猴子牌,则该方获得整场游戏的胜利。否则游戏将一直进行下去。
在进行了若干场比赛以后,小 Q 和小 M 算出了一张胜率表,为每张猴子牌之间进行战斗双方获胜的概率。由于每场战斗一定会决出胜负,而且胜率不受先后顺序的影响,因此对于任意的两张猴子牌 和 , 战胜 的概率加 战胜 的概率为 。
由于自己老是输给小 M ,小 Q 开始怀疑自己每次拿到的猴子牌是否能获得胜利。他希望求出自己拿到的每种猴子牌组合的获胜的概率。
由于小 Q 接下来还有在 CD 市体育中心数以万计的运动计划,因此这个问题只能交给你来解决了。
输入格式
输入的第一行包含两个正整数 和 ,表示猴子牌的总张数和需要求的猴子牌组合的个数。
接下来有 行,每行包含 个实数,每个实数保留了两位小数。这 行中,其中第 行第 列的数为 ,表示第 张猴子牌战胜第 张猴子牌的概率。保证 。特别地, ,没有特殊意义。
最后有 行。每行包含一个长度为 的无空格分隔的 01串
,表示一个猴子牌的组合。其中第 个字符如果为 0
,表示最初第 张牌在小 M 处,否则表示在小 Q 处。
输出格式
输出 行,每行一个实数,四舍五入保留八位小数(请强制输出八位浮点数),依次表示每个给定的猴子牌组合下小 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
数据规模与约定
对于 的数据,保证 。 , 恰好包含 位小数,且 。表示猴子牌组合的 01串
长度均为 ,且不含其他字符。
评分方式
你的答案的每一行如果与我们给定的参考答案的差别均不超过 ,则获得该测试点的得分,否则不得分。
参考答案保证与真实值的差别不超过 ,因此如果你输出的答案保证与真实值差别不超过 ,才能保证正确。
题目来源
vfleaking提供spj