← 返回题目列表

AtCoder · tenka1_2016_qualB_c

C. 天下一程序员大赛1999

中文机器翻译题面 查看原题

配点 : 600 点

問題文

在天下第一程序员大赛1999决赛中 N 人类参与者进行了循环赛,根据循环赛的结果和预选赛排名确定了本赛的排名。

在本赛中,根据循环赛中获胜的数量进行排名,如果获胜数相同,则预选赛排名较高者位居前列。

假设没有预选赛排名相同的参与者。

安藤君和桥本君都记录了循环赛的对战情况,对于每场对战,他们分别记录“X击败了Y”和“Y输给了X”。 2 (重复说明记录方式,保持原句结构)

安藤君不会记录错误。

当安藤君记录“预选赛排名 i 位的人击败了预选赛排名 j 位的人”时 A_{i,j} = 1 就是这个情况,否则不是。 A_{i,j} = 0 。

但是,桥本君在某些情况下 1 正确记录比赛结果的概率是 P = p / q ,而有 1-P 的概率会记录错误胜负。

假设每个记录都是独立事件。

例如,对于某场比赛,有 (1-P)^2 的概率会把胜负记反,或者有 P(1-P) 的概率会记录双方都获胜。

从对战记录中求X在循环赛中获胜的次数时,以“X战胜了某人”的记录数量来确定。

请计算安藤君记录的对战结果中得出的排名与桥本君记录的对战结果中得出的排名一致的概率。

制約

  • 2 \leq N \leq 30
  • 0 \leq p \leq q
  • 1 \leq q \leq 10
  • A_{i,j} \in \{ 0, 1 \}
  • A_{i,i} = 0
  • i \neq j 如果 A_{i,j} + A_{j,i} = 1
  • N, p, q 是一个整数

入力

输入是按以下格式从标准输入给出的。

N p/q
A_{1,1} A_{1,2} … A_{1,N}
A_{2,1} A_{2,2} … A_{2,N}
:
A_{N,1} A_{N,2} … A_{N,N}

出力

将排名一致的概率以小数形式输出。输出末尾请换行。

绝对误差或相对误差为 10^{−8} 如果满足以下条件,则答案被视为正确:


入力例 1

2 2/3
0 1
0 0

出力例 1

0.888888888888889

场比赛。 1 只有一场比赛,排名不一致的情况只有在将该场比赛的胜负记录反了的情况下才会发生,排名一致的概率是 8/9 变为。


入力例 2

2 4/6
0 0
1 0

出力例 2

0.444444444444444

入力例 3

5 0/1
0 1 1 1 1
0 0 1 1 1
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0

出力例 3

0.000000000000000

入力例 4

5 4/7
0 1 0 0 1
0 0 1 1 0
1 0 0 0 0
1 0 1 0 0
0 1 1 1 0

出力例 4

0.0130979274004664