No.3255 01 Matrix Counting
タグ : / 解いたユーザー数 69
作問者 :
Iroha_3856
/ テスター :
lif4635
champignon
tikuwa_
問題文
正整数 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。