Black and White
Time limit2sMemory limit512 MB
Each cell is black or white with probability 1/2; find the expected product of the number of all-black subrectangles and all-white subrectangles.
- Level
Hard8 of 10
- Topics
- Combinatorics, Probability, Math, Dynamic programming
- Solved
- No attempts yet
Problem
A rectangle is cut into squares of size , so it has rows and columns. Each square is painted black or white. Each color has probability 50%, and the squares are independent.
A subrectangle is built by choosing at least one row and at least one column, then keeping only the squares that lie in a chosen row and in a chosen column. The chosen rows do not have to be adjacent, and neither do the chosen columns. For example, in a rectangle, choosing rows 1 and 3 together with columns 2, 4 and 5 keeps the six squares shown below.

Two subrectangles are different whenever the chosen set of rows differs or the chosen set of columns differs, even if the coloring that remains looks the same. A subrectangle whose squares are all black is a black subrectangle, and one whose squares are all white is a white subrectangle.
Compute the expected value of the number of black subrectangles times the number of white subrectangles.
Input
The first line contains two integers and , the size of the rectangle, separated by one space. ()
Output
Write the expected value as a reduced fraction and print . Here is the multiplicative inverse of modulo . The answer exists for every input that satisfies the constraints.