問題一覧 > 通常問題

No.2251 Marking Grid

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 52
作問者 : bayashikobayashiko / テスター : ei1333333ei1333333 kumakumakumakuma
10 ProblemId : 9324 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-10 15:50:30

問題文

$H$ 行 $W$ 列のマス目があります。上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と呼ぶことにします。

マス目の各マスには整数が書かれており、マス $(i,j)$ に書かれている整数は $A_{i,j}$ です。

マス目のマスを $1$ つ以上選び、選んだマスそれぞれに印を付けます。印の付け方のスコアを、印を付けたマスたちに書かれている整数の最大値と定めます。

また、印の付け方が以下の条件を満たす場合、その印の付け方を良い印の付け方と呼ぶことにします。

  • マス目の任意の縦 $2$ 行、横 $2$ 列の正方形領域について、その領域に含まれる $4$ つのマスのうち印が付けられているマスは偶数個である。

印の付け方は全部で $2^{H×W}-1$ 通りあります。そのうち良い印の付け方全てについてスコアを計算し、その総和を $998244353$ で割った余りを求めて下さい。

入力

$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$
  • 入力はすべて整数

出力

全ての良い印の付け方のスコアの総和を $998244353$ で割った余りを出力してください。

サンプル

サンプル1
入力
2 2
3 3
1 4
出力
25

良い印の付け方は以下の $7$ 通りです。(印が付いたマスの整数の最大値を太字にしています)

よって、答えは $3+4+4+3+4+3+4=25$ です。

サンプル2
入力
3 3
1 2 3
4 5 6
7 8 9
出力
251

以下の $4$ つの条件を全て満たす印の付け方が良い印の付け方です。

  • マス $(1,1),$ マス $(1,2),$ マス $(2,1),$ マス $(2,2)$ のうち印が付けられているマスは偶数個である。
  • マス $(2,1),$ マス $(2,2),$ マス $(3,1),$ マス $(3,2)$ のうち印が付けられているマスは偶数個である。
  • マス $(1,2),$ マス $(1,3),$ マス $(2,2),$ マス $(2,3)$ のうち印が付けられているマスは偶数個である。
  • マス $(2,2),$ マス $(2,3),$ マス $(3,2),$ マス $(3,3)$ のうち印が付けられているマスは偶数個である。

以下に良い印の付け方の一例を示します。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。