| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem E
报警了
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
|