問題一覧 > 通常問題

No.2251 Marking Grid

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 54
作問者 : bayashiko / テスター : ei1333333 kumakuma
お気に入りにしたユーザー ProblemId : 9324 / 自分の提出
問題文最終更新日: 2023-03-10 15:50:30
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 381 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。