Partial Rectangles
Time limit2sMemory limit128 MB
Given an N x M grid doubled into a 2N x 2M grid, count how many times each letter appears summed over every possible subrectangle.
- Level
Medium5 of 10
- Topics
- Combinatorics, Math, Matrix, Implementation
- Solved
- No attempts yet
Problem
Minsik has an N x M rectangular table filled with uppercase letters. He copies the table once horizontally and once vertically, making a larger 2N x 2M table made from four copies of the original. Then he considers every subrectangle of this larger table.
Consider the following 1 x 2 table.
OK
After copying it into a 2 x 2 arrangement of copies, the larger table is:
OKOK
OKOK
This table has 30 subrectangles. They are shown below, where . is used only as a separator.
OKOK .... OKOK OKO. .... OKO. .KOK .... .KOK OK.. .... OK.. .KO. .... .KO.
OKOK OKOK .... OKO. OKO. .... .KOK .KOK .... OK.. OK.. .... .KO. .KO. ....
..OK ..OK .... O... .... O... .K.. .... .K.. ..O. .... ..O. ...K .... ...K
..OK .... ..OK O... O... .... .K.. .K.. .... ..O. ..O. .... ...K ...K ....
Find, over all subrectangles of the larger table, how many times each uppercase letter appears in total. In the case above, K appears 40 times and O appears 40 times.
Input
The first line contains two integers N and M. The next N lines contain the rows of the table. Every character is an uppercase English letter.
Output
Print 26 lines. The first line is the total number of appearances of A, the second line is the total number of appearances of B, and so on through Z.
Constraints
- 1 <= N, M <= 50