TheFourSquares
TCO13 Wildcard Round · 2013-02-19 · by gojira_tc
TCO13 Wildcard Round · 2013-02-19 · by gojira_tc · Math
Problem Statement
Problem Statement
Manao has a rectangular board of height n and width m. He is trying to put four squares in the corners of the board in such a way that:
Manao is interested in how many ways can he choose the lengths of the sides for his squares. More precisely, he is interested in the number of quadruples (a, b, c, d) such that if the square in the top-left corner of the board has side length a, the square in the bottom-left corner has side length b, the square in the top-right corner has side length c and the square in the bottom-right corner has side length d, they do not intersect.
You are given theint s n and m. Compute and return the number of valid quadruples modulo 1,000,000,009.
- Each square is aligned to the sides of the board and exactly one of its vertices coincides with a vertex of the board.
- The length of the side of each of the squares is a positive integer.
- No pair of squares intersects. Note that some pairs of squares may touch each other.
Manao is interested in how many ways can he choose the lengths of the sides for his squares. More precisely, he is interested in the number of quadruples (a, b, c, d) such that if the square in the top-left corner of the board has side length a, the square in the bottom-left corner has side length b, the square in the top-right corner has side length c and the square in the bottom-right corner has side length d, they do not intersect.
You are given the
Constraints
- n will be between 2 and 1,000,000, inclusive.
- m will be between 2 and 1,000,000, inclusive.
Examples
0)
2 2 Returns: 1
The only valid quadruple is (1, 1, 1, 1).
1)
3 3 Returns: 5
The five valid quadruples are: (1, 1, 1, 1). (1, 1, 1, 2). (1, 1, 2, 1). (1, 2, 1, 1). (2, 1, 1, 1).
2)
3 4 Returns: 9
In addition to the five quadruples from the previous sample, there are four new quadruples here: (1, 2, 1, 2). (1, 2, 2, 1). (2, 1, 1, 2). (2, 1, 2, 1).
3)
10 7 Returns: 421
4)
123456 987654 Returns: 136415012
Submissions are judged against all 44 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheFourSquares with a public method int countPlacements(int n, int m) · 44 test cases · 2 s / 256 MB per case