Wesley's Anger Contest Reject 6 - Geology

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 5.0s
Memory limit: 256M

Author:
Problem types

Kesley is studying geology! He is given two maps of different 1 \text{km} by 1 \text{km} regions. The first map is divided into an N \times N grid of equal-sized squares, while the second map is divided into an M \times M grid of equal-sized squares. The grids can be represented as a string of characters with # indicating the square is mostly rocks and . indicating the square is mostly empty.

When Kesley overlays the two maps on top of each other, he wants to know how similar the two 1 \text{km} by 1 \text{km} regions are. A point on the map is considered similar if it is rocky in both regions or empty in both regions. It can be shown that the percentage of points that are similar can be represented as a fraction \frac{P}{Q}. The similarity of the two maps is equal to P \cdot Q^{-1} where Q^{-1} is the multiplicative inverse modulo 998\,244\,353. It may be helpful to know that 998\,244\,353 is prime and 998\,244\,353 = 119 \times 2^{23} + 1.

Can you help Kesley determine the similarity of the two maps?

Constraints

For this problem, you will be required to pass all the samples in order to receive any points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le N, M \le 2\,500

Subtask 1 [36%]

1 \le N, M \le 50

Subtask 2 [64%]

No additional constraints.

Input Specification

The input consists of N + M + 2 lines.

The first line contains a single integer N, the size of the grid for the first map.

The next N lines contain N characters of either # or ., describing the first map. # indicates a rocky square, while . indicates an empty square.

The next line contains a single integer M, the size of the grid for the second map.

The next M lines contain M characters of either # or ., describing the second map.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output a single integer representing the similarity of the two maps.

Sample Input

2
#.
.#
3
#.#
.#.
#.#

Sample Output

499122177

Sample Explanation

\frac{1}{2} of the points in the region are similar.


Comments

There are no comments at the moment.