問題一覧 > 通常問題

No.2825 Sum of Scores of Sets of Specified Sections

レベル : / AI推定難易度 : 2475 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 19
作問者 : みどりむし🦠 / テスター : achapi viral8 FplusFplusF 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 10559 / 自分の提出
問題文最終更新日: 2024-07-27 10:18:52
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 438 (順位表) の他の問題:

Problem Statement

There are grids $A, B$, each with $H$ rows and $W$ columns, consisting of $HW$ cells in total.
In the cell at the $i \scriptsize \; (1 \leq i \leq H)$-th row from the top and the $j \scriptsize \; (1 \leq j \leq W)$-th column from the left of $A, B$, the integers $A_{i, j}, B_{i, j}$ are written, respectively.

You color $1$ or more cells of these grids.

A good coloring satisfies all of the following:

  • For each of $A, B$ and for any row, at most $1$ cell in that row is colored.
  • For each of $A, B$ and for any column, at most $1$ cell in that column is colored.
  • The set of "numbers of rows containing a colored cell" of $A$ is equal to the set of "numbers of rows containing a colored cell" of $B$.
  • The set of "numbers of columns containing a colored cell" of $A$ is equal to the set of "numbers of columns containing a colored cell" of $B$.
Here, the number of the $i$-th row is $i$, and the number of the $j$-th column is $j$.

For a colored grid $X$, the score $f(X)$ of $X$ is calculated as follows:

  1. For all colored cells, in any order, perform the following operation $1$ time each (the result does not depend on the order):
    • For every cell that is (strictly) to the right of and (strictly) above that cell, replace the number $x$ written in it with $-x$.
  2. After that, compute the product of the numbers written in all colored cells, and let it be $f(X)$.

Find the sum of $f(A) \times f(B)$ over all good colorings.
Since the absolute value of the answer can be large, output the remainder when it is divided by $998244353$.

Two colorings are different if and only if the sets of "colored cells" of $A$ are different and or (corrected 2024.07.26 21:41) the sets of "colored cells" of $B$ are different.

Input

The input is given from standard input in the following format:

$H \enspace W$
$A_{1, 1} \enspace A_{1, 2} \enspace \dots \enspace A_{1, W}$
$A_{2, 1} \enspace A_{2, 2} \enspace \dots \enspace A_{2, W}$
$\vdots$
$A_{H, 1} \enspace A_{H, 2} \enspace \dots \enspace A_{H, W}$
$B_{1, 1} \enspace B_{1, 2} \enspace \dots \enspace B_{1, W}$
$B_{2, 1} \enspace B_{2, 2} \enspace \dots \enspace B_{2, W}$
$\vdots$
$B_{H, 1} \enspace B_{H, 2} \enspace \dots \enspace B_{H, W}$

Output

Find the answer and output the remainder when it is divided by $998244353$ to standard output on a single line.
Here, "the remainder when $x$ is divided by $998244353$" is the unique integer $r$ such that there exists an integer $q$ with $x = 998244353 \times q + r$ and $0 \leq r < 998244353$ holds.

Constraints

  • $1 \leq H \leq 100$
  • $1 \leq W \leq 2000$
  • $0 \leq A_{i, j} < 998244353 \scriptsize \; (1 \leq i \leq H \land 1 \leq j \leq W)$
  • $0 \leq B_{i, j} < 998244353 \scriptsize \; (1 \leq i \leq H \land 1 \leq j \leq W)$
  • All input values are integers.

Sample

Sample Input/Output 1
Input
2 3
1 2 3
4 5 6
7 8 9
10 11 12
Output
271

There are $18$ good colorings in total, and the values of $f(A) \times f(B)$ they give, sorted in ascending order of absolute value, are $7, 16, 27, 40, 55, 72, 385, -400, 504, -540, -616, 640, -1008, 1080, 1152, -1188, -1440, 1485$.
Their sum is $271$.


Here are some examples of calculating $f(A) \times f(B)$: (The left and right grids are $A, B$, respectively. They are not necessarily related to the sample above.)

$(-3 \times 4) \times (7 \times 12) = -1008$

$(2) \times (8) = 16$

$(4 \times -5 \times 2) \times (-7 \times 8 \times 2) = 4480$

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