No.2825 Sum of Scores of Sets of Specified Sections
タグ : / 解いたユーザー数 20
作問者 :
![🦠みどりむし](https://pbs.twimg.com/profile_images/1258989583968043008/WWF0Yz3c.jpg)
![FplusFplusF](https://pbs.twimg.com/profile_images/1535630966743371776/RVkOr4C0.jpg)
![AngrySadEight](https://pbs.twimg.com/profile_images/1774819988135927808/f4w6hc33.jpg)
問題文
グリッド $A, B$ があり、いずれも縦 $H$ マス 横 $W$ マスの、計 $HW$ マスからなります。
$A, B$ の上から $i \scriptsize \; (1 \leq i \leq H)$ 行目、左から $j \scriptsize \; (1 \leq j \leq W)$ 行目のマスには、それぞれ整数 $A_{i, j}, B_{i, j}$ が書かれています。
これらのグリッドの $1$ つ以上のマスに色を塗ります。
よい塗り方は、以下をすべて満たします:
- $A, B$ いずれについても、任意の行に対して、その行は高々 $1$ つのマスが塗られている。
- $A, B$ いずれについても、任意の列に対して、その列は高々 $1$ つのマスが塗られている。
- $A$ の「色の塗られたマスが存在する行の番号」の集合と、$B$ の「色の塗られたマスが存在する行の番号」の集合は等しい。
- $A$ の「色の塗られたマスが存在する列の番号」の集合と、$B$ の「色の塗られたマスが存在する列の番号」の集合は等しい。
ここで、色の塗られたグリッド $X$ について、$X$ のスコア $f(X)$ は次のように計算されます:
- 色の塗られたマスすべてについて、自由な順に以下の操作を $1$ 回ずつ行う (結果は順番に依らない):
- そのマスより (真に) 右 かつ (真に) 上 にあるようなすべてのマスについて、そのマスに書かれている数 $x$ を $-x$ で置き換える。
- その後、色の塗られたマスすべてをわたる、そのマスに書かれた数の総積を求め、それを $f(X)$ とする。
よい塗り方すべてをわたる、$f(A) \times f(B)$ の総和を求めてください。
ただし、答えの絶対値は大きくなる場合があるので、$998244353$ で割ったあまりを出力してください。
なお、$A$ の「色の塗られたマス」の集合が異なり、かつ または (2024.07.26 21:41 修正) $B$ の「色の塗られたマス」の集合が異なるとき、またそのときに限り、塗り方は異なります。
入力
入力は、以下の形式で標準入力より与えられる:
$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}$
出力
答えを求め、$998244353$ で割ったあまりを標準出力へ一行に出力せよ。
ただし「$x$ を $998244353$ で割ったあまり」とは、$x = 998244353 \times q + r$ なる整数 $q$ が存在し、かつ $0 \leq r < 998244353$ をみたすような唯一の整数 $r$ である。
制約
- $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)$
- 入力はすべて整数
サンプル
入出力例1
入力
2 3 1 2 3 4 5 6 7 8 9 10 11 12
出力
271
よい塗り方は全部で $18$ 通りあり、それらが与える $f(A) \times f(B)$ の値を絶対値の小さい順に並べると $7, 16, 27, 40, 55, 72, 385, -400, 504, -540, -616, 640, -1008, 1080, 1152, -1188, -1440, 1485$ となります。
これらの総和は $271$ です。
$f(A) \times f(B)$ の計算結果の例をいくつか示します:(左右のグリッドがそれぞれ $A, B$ です。上記サンプルとは必ずしも関係ありません。)
$(-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もしくは右上の雲マークをクリックしてアカウントを作成してください。