408221: GYM103059 B Betting Confusion

Priya has placed a series of convoluted bets on the results of the upcoming horse races. Unfortunately, she's placed so many bets that she's now unable to calculate how much money she expects to gain or lose from her bets and is worried that she may be losing too much.

She's figured out for each pair of horses how much she stands to gain or lose if either horse beats the other, but doesn't know how much she can expect to earn overall, where her total reward is the sum of each pairwise reward earned given the ordering of the horses defined by the horses' placement after the race is finished.

Given that each possible ordering of horses in the race is equally probable (it is impossible for any two horses to tie), what is the expected value of Priya's winnings or losses?

The input begins with a single integer $$$n$$$ $$$(1 \leq n \leq 300)$$$ giving the number of horses in the race. The next $$$n$$$ lines each consist of $$$n$$$ integers where the $$$j$$$th integer on the $$$i$$$th line, $$$a_{ij}$$$ $$$(-10^5 \leq a_{ij} \leq 10^5)$$$, gives the reward that Priya earns if horse $$$i$$$ places higher than horse $$$j$$$ in the race. Note that $$$a_{ii} = 0$$$ for all $$$1 \leq i \leq n$$$.

Output a single real number giving the expected value of Priya's winnings given that each ordering of horses is equally likely. Your answer will be judged as correct if it has an absolute or relative error less than $$$10^{-6}$$$.

3
0 1 1
1 0 1
1 1 0

3.0000000000

5
0 -1 -3 4 2
1 0 3 -4 -5
10 -20 0 5 0
8 7 -12 0 -13
1 1 -3 2 0

-8.5000000000

For the first sample, Priya will collect a total reward of $$$3$$$ for any of the $$$6$$$ possible orderings of horses.