QOJ.ac

QOJ

时间限制: 1 s 内存限制: 512 MB 总分: 100 难度: [显示]

#2142. 尤里克与木工课

统计

今天 Yurik 一大早就兴高采烈地起床了,因为根据课程表,第一节课是木工课。这是 Yurik 最喜欢的课,因为他通常会在课上无视老师,和朋友们在教室后排玩桌游。但当他发现今天有测验时,他感到很失望。

课刚开始,老师给每个学生(包括 Yurik)发了一块 $N \times M$ 的木板。木板上用铅笔画了线,将其分成了 $N$ 行 $M$ 列,即由 $N \cdot M$ 个 $1 \times 1$ 的方格组成。

测验的内容是用线锯从木板上切掉一些方格,使得剩下的部分是“美观的”。

如果满足以下五个条件,则称木板是“美观的”:

  1. 木板左上角的方格没有被切掉。
  2. 木板右下角的方格没有被切掉。
  3. 剩下的木板是一个连通的区域。这意味着从任何一个方格出发,都可以通过若干步移动到达其他任何方格。每一步可以移动到左、右、上或下相邻的方格。
  4. 对于剩下的木板的每一行,满足以下条件:该行中未被切掉的所有方格形成一个连续的水平线段。
  5. 对于剩下的木板的每一列,满足以下条件:该列中未被切掉的所有方格形成一个连续的垂直线段。

任何不满足至少一个条件的木板都被称为“丑陋的”。下图展示了美观木板和丑陋木板的例子。左上角和右下角的方格被涂成了灰色。

尺寸为 $3 \times 4$ 的美观木板示例

尺寸为 $3 \times 4$ 的丑陋木板示例

由于 Yurik 从不听老师讲课且热爱数学,他没有参加测验,而是思考:从原始木板中切掉一些(可能为零)方格,可以得到多少种不同的美观木板?如果切掉的方格集合不同,则认为两块木板不同。

请帮助 Yurik 回答这个问题。

输入格式

输入仅一行,包含两个整数 $N$ 和 $M$ —— 原始木板的尺寸 ($1 \le N, M \le 10^5$)。

输出格式

输出一个整数 —— Yurik 可以通过切掉一些方格得到的不同美观木板的数量。

由于答案可能非常大,请输出其对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

2 2

样例输出 1

3

样例输入 2

2 4

样例输出 2

10

样例输入 3

100 100

样例输出 3

818380736

说明

下图展示了第一个和第二个样例:

所有可以从 $2 \times 2$ 的原始木板中切出的美观木板

所有可以从 $2 \times 4$ 的原始木板中切出的美观木板

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.