SubRectangles
2015 TCO 3A · 2015-04-08 · by rng_58
2015 TCO 3A · 2015-04-08 · by rng_58 · Brute Force, Math
Problem Statement
Problem Statement
This problem has a non-standard time limit: 5 seconds.
There is a rectangular board divided into H times W square cells. The board is currently empty. Cat Snuke is going to put tokens on some cells. He may only put at most one token onto each cell. When he's finished, each possible subrectangle of dimensions H2 times W2 must contain the same number of tokens.
You are given theint s H, W, H2, and W2.
Count valid ways of placing the tokens.
Return the answer modulo 1,000,000,007.
There is a rectangular board divided into H times W square cells. The board is currently empty. Cat Snuke is going to put tokens on some cells. He may only put at most one token onto each cell. When he's finished, each possible subrectangle of dimensions H2 times W2 must contain the same number of tokens.
You are given the
Constraints
- H and W will be between 1 and 1,000,000,000, inclusive.
- H2 and W2 will be between 1 and 4, inclusive.
- H2 will be less than or equal to H.
- W2 will be less than or equal to W.
Examples
0)
2015 666 1 1 Returns: 2
Snuke can choose between two valid ways of placing the tokens: Either he puts one token onto each cell, or he leaves all cells empty.
1)
3 3 3 2 Returns: 160
The following picture shows one possible way to put tokens ('o' is a cell with token, '-' is a cell without token): -oo o-- ooo There are two subrectangles with the dimensions 3 rows by 2 columns. Each of these contains four tokens.
2)
6 3 4 1 Returns: 346
3)
10 20 3 3 Returns: 705820974
4)
123456789 987654321 3 4 Returns: 841175976
Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SubRectangles with a public method int countWays(int H, int W, int H2, int W2) · 55 test cases · 2 s / 256 MB per case