LitPanels
TCO13 Round 2B · 2013-02-19 · by rng_58
TCO13 Round 2B · 2013-02-19 · by rng_58 · Math
Problem Statement
Problem Statement
Fox Ciel has a board divided into X times Y square panels.
Initially, all panels are unlit.
Whenever Ciel presses a panel, that panel will turn on and from that moment on the panel will be lit forever.
Ciel is going to perform the following operation twice. The operation starts with Ciel choosing a subrectangle of the board. The dimensions of the subrectangle have to be sx times sy, and the side with length sx has to be parallel to the side of the board with length X. Once the subrectangle is chosen, Ciel presses some of the panels it contains (possibly none at all or all of them).
The following figures show an example of these operations for X = 5, Y = 4, sx = 3, and sy = 2. The picture on the left shows the initial board, the picture in the middle shows the board after the first operation, and the picture on the right shows the board after the second operation.
Compute and return the number of different patterns Ciel can have after finishing the two operations, modulo 1,000,000,007.
Ciel is going to perform the following operation twice. The operation starts with Ciel choosing a subrectangle of the board. The dimensions of the subrectangle have to be sx times sy, and the side with length sx has to be parallel to the side of the board with length X. Once the subrectangle is chosen, Ciel presses some of the panels it contains (possibly none at all or all of them).
The following figures show an example of these operations for X = 5, Y = 4, sx = 3, and sy = 2. The picture on the left shows the initial board, the picture in the middle shows the board after the first operation, and the picture on the right shows the board after the second operation.
Compute and return the number of different patterns Ciel can have after finishing the two operations, modulo 1,000,000,007.
Constraints
- X will be between 1 and 40, inclusive.
- Y will be between 1 and 40, inclusive.
- sx will be between 1 and X, inclusive.
- sy will be between 1 and Y, inclusive.
Examples
0)
2 2 1 1 Returns: 11
All patterns with at most two lit panels are possible. The number of such patterns is C(4, 0) + C(4, 1) + C(4, 2) = 11, where C denotes binomial coefficients.
1)
2 3 1 2 Returns: 40
The following picture shows all 40 possible patterns.
2)
4 4 3 2 Returns: 14096
3)
40 39 5 8 Returns: 877713074
4)
39 30 19 6 Returns: 910646629
Submissions are judged against all 46 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LitPanels with a public method int countPatterns(int X, int Y, int sx, int sy) · 46 test cases · 2 s / 256 MB per case