RectanglesWithMoreBlackCells | Topcoder Archive

Problem Statement

You are given a rectangular field of cells containing m rows and n columns. Each cell is either black or white. Return the number of rectangles on the field that contain more black cells than white ones.

You are given a String[] template and two ints a and b. template contains exactly h elements, each of which contains exactly w characters. Use the following pseudocode to generate the field:

t = 0;
for i from 0 to m - 1 do
  for j from 0 to n - 1 do {
    field[i][j] = template[(i + t) mod h][(j + t) mod w];
    t = (t * a + b) mod 1000003;
  }

Here "x mod y" means the remainder of an integer division of x by y. White cells in the field are represented by 'W' characters, and black cells are represented by 'B' characters.

Definition

Class:: RectanglesWithMoreBlackCells
Method:: count
Parameters:: int, int, String[], int, int
Returns:: long
Method signature:: long count(int m, int n, String[] template, int a, int b)
(be sure your method is public)

Constraints

m will be between 1 and 2000, inclusive.
n will be between 1 and 50, inclusive.
template will contain between 1 and min(50, m) elements, inclusive.
All elements of template will have the same length.
Each element of template will contain between 1 and min(50, n) characters, inclusive.
Each element of template will contain only 'B' and 'W' letters.
a and b will each be between 0 and 1000, inclusive.

Examples

```
2
```
```
2
```
```
{"BB", "BW"}
```
```
0
```
```
0
```
```
Returns: 6
```
There are 9 rectangles. 6 of them have more black cells than white cells.
```
1
```
```
4
```
```
{"BW"}
```
```
0
```
```
1
```
```
Returns: 7
```
The field in this example is: "BBWB".

{"BBBB", "BWWW", "WBBW", "BBWB"}

Returns: 80

```
2000
```
```
50
```
```
{"W"}
```
```
0
```
```
0
```
```
Returns: 0
```
There are no black cells.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.