No.2251 Marking Grid
Problem Statement
There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is called cell $(i,j)$.
Each cell of the grid contains an integer, and the integer written in cell $(i,j)$ is $A_{i,j}$.
Choose $1$ or more cells of the grid and put a mark on each chosen cell. The score of a way of marking is defined as the maximum of the integers written in the marked cells.
Also, a way of marking is called a good marking if it satisfies the following condition.
- For every square region of $2$ rows and $2$ columns in the grid, the number of marked cells among the $4$ cells in that region is even.
There are $2^{H×W}-1$ ways of marking in total. Calculate the score for every good marking among them, and find the sum of the scores modulo $998244353$.
Input
$H\ W$
$A_{1,1}\ A_{1,2} \ .. \ A_{1,W}$
$A_{2,1}\ A_{2,2} \ .. \ A_{2,W}$
:
$A_{H,1}\ A_{H,2} \ .. \ A_{H,W}$
- $2\le H,W\le 1000$
- $1\le A_{i,j}\le 998244352$
- All inputs are integers.
Output
Print the sum of the scores of all good markings modulo $998244353$.
Sample
Sample 1
Input
2 2 3 3 1 4
Output
25
The following $7$ ways are the good markings. (The maximum of the integers in the marked cells is shown in bold.)
Thus, the answer is $3+4+4+3+4+3+4=25$.
Sample 2
Input
3 3 1 2 3 4 5 6 7 8 9
Output
251
A way of marking is a good marking if it satisfies all of the following $4$ conditions.
- The number of marked cells among cell $(1,1),$ cell $(1,2),$ cell $(2,1),$ cell $(2,2)$ is even.
- The number of marked cells among cell $(2,1),$ cell $(2,2),$ cell $(3,1),$ cell $(3,2)$ is even.
- The number of marked cells among cell $(1,2),$ cell $(1,3),$ cell $(2,2),$ cell $(2,3)$ is even.
- The number of marked cells among cell $(2,2),$ cell $(2,3),$ cell $(3,2),$ cell $(3,3)$ is even.
An example of a good marking is shown below.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
bayashiko
ei1333333