問題一覧 > 通常問題

No.3255 01 Matrix Counting

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 60
作問者 : Iroha_3856 / テスター : lif4635 champignon tikuwa_
ProblemId : 12660 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-09-05 04:14:35

問題文

正整数 $H, W$ が与えられます。

$H$ 行 $W$ 列で、すべての要素が $0$ または $1$ である行列 $A$ であって、以下の条件を満たすものの数を $998244353$ で割ったあまりを求めてください。

  • すべての $1 \leq i \leq H-1, 1 \leq j \leq W-1$ を満たす整数の組 $(i, j)$ について、$A$ における $(1, 1)$ を左上、$(i, j)$ を右下とする長方形領域の総和と $A$ における $(i+1, j+1)$ を左上、$(H, W)$ を右下とする長方形領域の総和の偶奇は異なる。
    • より厳密には、$\displaystyle \sum_{k = 1}^i \sum_{l = 1}^j A_{k, l} \not\equiv \sum_{k = i+1}^H \sum_{l = j+1}^W A_{k, l} \pmod 2$

入力

$H\ W$

入力はすべて以下の制約を満たす。

  • $2 \leq H, W \leq 10^9$
  • $H, W$ は整数

出力

条件を満たす $A$ の数を $998244353$ で割った余りをを出力し、改行してください。

サンプル

サンプル1
入力
2 2
出力
8

$A = \begin{pmatrix} 0 & 0\\ 0 & 1\\ \end{pmatrix}, \begin{pmatrix} 0 & 0\\ 1 & 1\\ \end{pmatrix}, \begin{pmatrix} 0 & 1\\ 0 & 1\\ \end{pmatrix}, \begin{pmatrix} 0 & 1\\ 1 & 1\\ \end{pmatrix}, \begin{pmatrix} 1 & 0\\ 0 & 0\\ \end{pmatrix}, \begin{pmatrix} 1 & 0\\ 1 & 0\\ \end{pmatrix}, \begin{pmatrix} 1 & 1\\ 0 & 0\\ \end{pmatrix}, \begin{pmatrix} 1 & 1\\ 1 & 0\\ \end{pmatrix} $ の $8$ 個のみが条件を満たします。

サンプル2
入力
1000000000 1000000000
出力
545791284

$998244353$ で割った余りを出力してください。

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