/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 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