403551: GYM101193 B Variety

Bernard saw a square box full of sweets and the variety of choices took him by surprise. The box has n × n cells and each cell has one candy of a specific type. The only thing perplexed Bernard is capable of at the moment is to randomly choose a rectangle of cells and eat all candies in them. However, Bernard never loses composure, so each rectangle has an equal chance to be chosen. We are just curious to know what is the expected number of different candies that are going to be eaten right now.

The first line contains an integer number n, where n is the size of the box. Following that are n lines each containing n integer numbers a_i, j that denote types of candies in the box cells.

You got to know that all tests for this problem were generated randomly, i.e. for given n and k each cell of a box of size n × n contains one of k candy types, which was chosen randomly and uniformly.

Output the expected number of different types of candies that would be eaten by Bernard. Your output should have an absolute or relative error of at most 10^- 9.

3
1 2 3
2 2 3
3 1 1

1.8888888889