名聚四海

1000ms

262144K

描述：

在著名的四海古城，每天游客都络绎不绝。四海城由 $$$m$$$ 条横向街道和 $$$n$$$ 条纵向街道构成，将城市划分为 $$$ (m + 1) \times (n + 1)$$$ 个街区。城市的参观入口修筑在城市的最西南角的街区，所有游客需要从城市最西南角的起点出发，前往最东北角的出口街区进行游览。游客每一步只能向东或向北移动一个街区的距离。

示意图

现在，四海城的文旅局正在指定旅游手册，他们想要计算出，游客们总共有多少种不同的路径可以到达出口？

输入：

两个整数 $$$m$$$ 和 $$$n$$$，表示横向和纵向的街道数量。题目保证 $$$1 \leq m, n \leq 30$$$，答案不超过 $$$2 \times 10^9$$$。

输出：

一个整数，表示不同的路径数目。

样例输入：

2 6

样例输出：

样例输入：

2 1

样例输出：

样例输入：

6 2

样例输出：

样例输入：

2 2

样例输出：

注释：

在第二组样例中，城市被 $$$2$$$ 条横向街道和 $$$1$$$ 条纵向分割为 $$$6$$$ 个街区，因此游客可以选择以下 $$$3$$$ 种路径：

向东，再向北，再向北；
向北，再向东，再向北；
向北，再向北，再向东。

因此，总共有 $$$3$$$ 种不同的路径。

题目保证，对于 $$$20\%$$$ 的数据，$$$m = 1$$$ 或 $$$n = 1$$$。

题目保证，对于 $$$40\%$$$ 的数据，$$$m \leq 2$$$ 或 $$$n \leq 2$$$。

题目保证，对于 $$$60\%$$$ 的数据，$$$m, n \leq 10$$$。

题目保证，对于 $$$80\%$$$ 的数据，$$$m, n \leq 20$$$。

题目保证，对于 $$$100\%$$$ 的数据，$$$1 \leq m, n \leq 30$$$。

信息

提供者机考平台

代码 PROB1042

标签

提交 1477

通过 500

通过率 33.85%

修改日期 2025-03-27 16:20:27