[Login|Register]
Problems

Status

Rank

Problem 1421
报警了
Time Limit: 1000ms
Memory Limit: 65536kb
Description
某国的大使馆非常傲娇,它的签证需要排很久的队才能上交资料,并且还要等非常非常之久的时间才能拿到签证。然而最傲娇地方在于,当大家想打电话去询问签证进度时,每次接电话的人员都会把责任踢皮球给另一个人,使得事情永远得不到正面回复。
某国大使馆的电话服务的架构如下:一共有 n 个部门,第 i 个部门下面有 ai 个接线员,
当某个部门接到一次电话时,该部门的负责人会把电话按一定概率分给该部门下面的某个接线员,让他接电话,每个接线员在接到电话后都会按自己的喜好把责任踢给某个部门(可以是自己部门,借口为信号不好你再打一个呗)。
大家一开始都会给编号为 1 的那个部门(也就是通联部)打电话,然后就是无止尽的踢皮球过程。无尽的等待闲暇之余,大家很好奇每个接线人员接电话的数学期望概率是多少,希望你能帮大家求一下。

Input
输入包含多组测试数据。
第一行为一个整数,表示测试数据的个数。每组测试数据的第一行为一个整数 n(1 ≤ n ≤ 50),表示某国的部门个数。接下来依次为每个部门的信息。
对于第 i 个部门,第一行包括一个整数 ai(1 ≤ ai ≤ 100),为该部门的接线员个数。接下来一行含有 ai 个小数,第 j 个数表示部门 i 把接电话任务分配给它下面人员 j 的概率,保证概率之和为 1。
接下来 ai 行,每行 n 个小数,第 j 行第 k个数代表了接线员 j 把责任踢给部门 k 的概率,保证概率之和为 1。
Output
对于每组测试数据输出 n 行,第 i 行包含 ai 个数,为该接线员接电话的期望概率,精确到小数点后 6 位。
Sample Input
1
2
1
1
0.5 0.5
1
1
0.5 0.5
Sample Output
0.500000
0.500000
Hint
求的是概率的期望.即很多轮之后,每个人接的电话占总电话的比例.
本题FB奖: 移动电源一个.
Source
zry
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.8ms with 1 query(s).