TopCoder problem "PerfectRectangles" used in SRM 431 (Division I Level Three)

Problem Statement

You are given a square board of size NxN. Each 1x1 cell will be colored either black or white. A rectangle on the board is called good if it contains only white cells. A good rectangle is called perfect if it doesn't lie completely within any other good rectangle.

Here's how the board will be colored. You are given ints M, X0, Y0, A, B, C and D. Generate lists X and Y, each of length M, using the following recursive definitions:

X[0] = X0 MOD N

X[i] = (X[i-1]*A+B) MOD N

Y[0] = Y0 MOD N

Y[i] = (Y[i-1]*C+D) MOD N

The board is initially entirely white. Then, for each i, the cell in column X[i] of row Y[i] is colored black. Return the number of perfect rectangles on the board.

Definition

Class:	PerfectRectangles
Method:	numberOfRectangles
Parameters:	int, int, int, int, int, int, int, int
Returns:	int
Method signature:	int numberOfRectangles(int N, int M, int X0, int A, int B, int Y0, int C, int D)
(be sure your method is public)

Notes

The same cell can be painted black multiple times.

Constraints

N will be between 1 and 2,000, inclusive.

M will be between 1 and 4,000,000, inclusive.

X0,Y0,A,B,C,D will each be between 0 and 2,000, inclusive.

Examples

5
1
2
0
0
2
0
0

Returns: 4

One black cell in the center.

4
4
0
1
1
0
1
1

Returns: 6

Black cells form the diagonal of the square.

1
1000000
1
2
3
1
4
7

Returns: 0

All cells are black.

10
20
4
76
2
6
2
43

Returns: 12

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10171

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13522&pm=10171

Writer:

Gluk

Testers:

PabloGilberto , Olexiy , ivan_metelsky