[AGC035F] Two Histograms
题意翻译
现在你有一个 $n\times m$ 的网格,你会按顺序进行做如下操作:
+ 把所有格子中的数都赋为 $0$ 。
+ 对每一行选一个 $k_i$ $(0\leq k_i\leq m)$ ,并把这一行最左边的 $k_i$ 个格子 $+1$ 。
+ 对每一列选一个 $l_i$ $(0\leq l_i\leq n)$ , 并把这一列最上面的 $l_i$ 个格子 $+1$ 。
经过这些操作后,你可以得到一个只包含 $0$,$1$ , $2$ 的网格。请你求出,在所有可能的操作下,可以得到多少本质不同的网格。
两个网格被称为本质不同的,当且仅当存在至少一个位置,两个网格对应位置上的数不同。
输出答案对 $998244353$ 取模的结果。
数据范围:$n,m\leq 5\times 10^5$ 。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc035/tasks/agc035_f
$ N $ 行 $ M $ 列のマス目があります。高橋君は、以下のようにして各マスに整数を書き込みます。
- まず、すべてのマスに $ 0 $ を書き込む
- $ i=1,2,...,N $ に対し、整数 $ k_i\ (0\leq\ k_i\leq\ M) $ を選び、上から $ i $ 行目の左から $ k_i $ 個のマスに書かれた整数すべてに $ 1 $ を足す
- $ j=1,2,...,M $ に対し、整数 $ l_j\ (0\leq\ l_j\leq\ N) $ を選び、左から $ j $ 列目の上から $ l_j $ 個のマスに書かれた整数すべてに $ 1 $ を足す
こうして、各マスに $ 0,1,2 $ のいずれかの整数の書かれたマス目が出来上がります。最終的にできる可能性のある相異なるマス目の個数を $ 998244353 $ で割った余りを求めてください。 ただし、$ 2 $ つのマス目が異なるとは、あるマスが存在してそのマスに書かれた整数が異なることを指します。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $
输出格式
最終的にできる可能性のある相異なるマス目の個数を $ 998244353 $ で割った余りを出力せよ。
输入输出样例
输入样例 #1
1 2
输出样例 #1
8
输入样例 #2
2 3
输出样例 #2
234
输入样例 #3
10 7
输出样例 #3
995651918
输入样例 #4
314159 265358
输出样例 #4
70273732
说明
### 制約
- $ 1\ \leq\ N,M\ \leq\ 5\times\ 10^5 $
- $ N,M $ は整数である
### Sample Explanation 1
左のマスに $ a $ が、右のマスに $ b $ が書き込まれたマス目を $ (a,b) $ と表すことにすると、$ (0,0),(0,1),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2) $ の $ 8 $ 通りのマス目ができる可能性があります。