問題一覧 > 通常問題

No.2151 3 on Torus-Lohkous

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : snukesnuke / テスター : 👑 hos.lyrichos.lyric
5 ProblemId : 8777 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-12 00:23:25

問題文

トーラス状に繋がった $H$ 行 $W$ 列のマス目を白黒で塗り分ける方法であって以下の条件を満たすものは何通りあるでしょう?

  • 黒の連結成分はちょうど $1$ 個
  • 黒の連結成分は全ての場所で幅・高さ共にちょうど $3$

答えは mod $998244353$ で求めてください。

$1$ つの入力につき、$T$ 個のテストケースに答えてください。


厳密な問題文

$H$ 行 $W$ 列のマス目がある。 $i\ (0 \leq i \lt H)$ 行目 $j\ (0 \leq j \lt W)$ 列目のマスをマス $(i,j)$ と呼ぶ。 マス $(i,j)$ はマス $((i+1)\bmod H,\,j)$、マス $((i-1)\bmod H,\,j)$、マス $(i,\,(j+1)\bmod W)$、マス $(i,\,(j-1)\bmod W)$ に隣接している。

以下の条件を満たすようにマスを白黒で塗り分ける場合の数を $998244353$ で割った余りを求めよ。

  • $1$ つ以上のマスを黒く塗る。
  • 任意の黒マスの組 $a,b$ について、隣接する黒マスを辿ることにより $a$ から $b$ まで到達することができる。
  • 任意の黒マスについて、同じ行の隣接する黒マスを $0$ 回以上辿ることによって到達できるマスの個数がちょうど $3$。
  • 任意の黒マスについて、同じ列の隣接する黒マスを $0$ 回以上辿ることによって到達できるマスの個数がちょうど $3$。

$1$ つの入力につき、$T$ 個のテストケースに答えよ。

制約

  • $1 \leq T \leq 256$
  • $4 \leq H,W \leq 10^5$

入力

まず $1$ 行目に、入力に含まれるテストケースの数 $T$ が与えられます。

$T$

その後、$T$ 行にわたって $T$ 個のテストケースが与えられます。各テストケースは次の形式で $1$ 行で与えられます。

$H\ W$

出力

$T$ 行出力してください。 $i$ 行目 $(1 \leq i \leq T)$ には、$i$ 番目のテストケースに対する回答を出力してください。

サンプル

サンプル1
入力
3
4 4
4 5
100000 100000
出力
40
20
604213015

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