CellScores
SRM 447 · 2009-08-25 · by Gluk
SRM 447 · 2009-08-25 · by Gluk · Math, Search
Problem Statement
Problem Statement
You are given a square board of size NxN, where each 1x1 cell is either black or white. A rectangle on the board is called good if it contains only white cells. The score of each cell is equal to the number of distinct good rectangles that contain that cell.
Use the following instructions to determine the coloring of the board. You are givenint s M, K, X0, Y0, A, B, C and D. Generate two lists, X and Y, each of length M+K, 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
For each i between 0 and M-1, inclusive, the cell at column X[i], row Y[i] is black. The remaining cells are white.
Let's denote the score for the cell at column i, row j as score(i, j). Return the sum of score(X[i], Y[i]) for all i between M and M+K-1, inclusive.
Use the following instructions to determine the coloring of the board. You are given
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
For each i between 0 and M-1, inclusive, the cell at column X[i], row Y[i] is black. The remaining cells are white.
Let's denote the score for the cell at column i, row j as score(i, j). Return the sum of score(X[i], Y[i]) for all i between M and M+K-1, inclusive.
Constraints
- N will be between 1 and 1,500, inclusive.
- M and K will each be between 0 and 1,000,000, inclusive.
- X0,Y0,A,B,C,D will each be between 0 and 1,500, inclusive.
Examples
0)
10 0 1 0 1 1 0 1 1 Returns: 100
The whole board is white. You are interested in cell (0,0). The score for this cell is 100.
1)
10 1 1 5 1 5 5 1 5 Returns: 75
Only the cell (5,5) is black. You are interested in cell (0,0). The score for this cell is 75.
2)
7 4 3 0 1 1 0 1 1 Returns: 194
The first 4 cells on the diagonal are black, and you are interested in the other 3 cells on the diagonal.
3)
23 10 30 26 48 76 231 463 707 Returns: 8088
4)
211 30 12 3 35 82 0 43 15 Returns: 18196443
Submissions are judged against all 162 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CellScores with a public method long long countScores(int N, int M, int K, int X0, int A, int B, int Y0, int C, int D) · 162 test cases · 2 s / 256 MB per case