No.3255 01 Matrix Counting
タグ : / 解いたユーザー数 72
作問者 :
Iroha_3856
/ テスター :
lif4635
champignon
tikuwa_
Problem Statement
You are given positive integers $H, W$.
Find the number, modulo $998244353$, of matrices $A$ with $H$ rows and $W$ columns, all of whose elements are $0$ or $1$, that satisfy the following condition.
-
For every pair of integers $(i, j)$ satisfying $1 \leq i \leq H-1, 1 \leq j \leq W-1$, the parity of the sum of the rectangular region of $A$ with $(1, 1)$ as its upper-left corner and $(i, j)$ as its lower-right corner differs from the parity of the sum of the rectangular region of $A$ with $(i+1, j+1)$ as its upper-left corner and $(H, W)$ as its lower-right corner.
- More strictly, $\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$
Input
$H\ W$
All input satisfies the following constraints.
- $2 \leq H, W \leq 10^9$
- $H, W$ are integers
Output
Print the number of matrices $A$ satisfying the condition, modulo $998244353$, followed by a newline.
Sample
Sample 1
Input
2 2
Output
8
Only the $8$ matrices $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} $ satisfy the condition.
Sample 2
Input
1000000000 1000000000
Output
545791284
Print the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。