AT_agc035_f [AGC035F] Two Histograms
题目描述
有一个 $N$ 行 $M$ 列的网格。高桥君按照如下方式在每个格子中写入整数。
- 首先,在所有格子中写入 $0$。
- 对于 $i=1,2,\ldots,N$,选择一个整数 $k_i\ (0\leq k_i\leq M)$,将第 $i$ 行从左起前 $k_i$ 个格子中的整数全部加 $1$。
- 对于 $j=1,2,\ldots,M$,选择一个整数 $l_j\ (0\leq l_j\leq N)$,将第 $j$ 列从上起前 $l_j$ 个格子中的整数全部加 $1$。
经过上述操作后,每个格子中的数都是 $0,1,2$ 中的一个。请计算最终可能得到的不同网格的个数,并对 $998244353$ 取模输出。若存在某个格子,其数值不同,则认为两个网格不同。
输入格式
输入从标准输入中给出,格式如下:
> $N$ $M$
输出格式
输出最终可能得到的不同网格的个数,对 $998244353$ 取模。
说明/提示
## 限制
- $1\leq N,M\leq 5\times 10^5$
- $N,M$ 为整数
## 样例解释 1
如果用 $(a,b)$ 表示左边格子的数为 $a$,右边格子的数为 $b$,则可能得到 $(0,0),(0,1),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)$ 共 $8$ 种不同的网格。
由 ChatGPT 4.1 翻译