双单调数组计数(Two Arrays)

题目描述

给定两个整数 $n$ 和 $m$，计算满足以下条件的数组对 $(a, b)$ 的数量：

• 两个数组的长度均为 $m$；
• 每个数组的每个元素都是 $1$ 到 $n$ 之间的整数（包含 $1$ 和 $n$）；
• 对于任意下标 $i$（$1 \le i \le m$），都有 $a_i \le b_i$；
• 数组 $a$ 是非降序排列的；
• 数组 $b$ 是非升序排列的。

由于答案可能非常大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

一行包含两个整数 $n$ 和 $m$（$1 \le n \le 1000$，$1 \le m \le 10$）。

输出格式

输出一个整数，表示满足条件的数组 $a$ 和 $b$ 的对数，对 $10^9+7$ 取模。

样例输入 #1

2 2

样例输出 #1

5

样例输入 #2

10 1

样例输出 #2

55

样例输入 #3

723 9

样例输出 #3

157557417

数据范围

在第一个测试样例中，共有 $5$ 个符合条件的数组对：

• $a = [1, 1],\ b = [2, 2]$；
• $a = [1, 2],\ b = [2, 2]$；
• $a = [2, 2],\ b = [2, 2]$；
• $a = [1, 1],\ b = [2, 1]$；
• $a = [1, 1],\ b = [1, 1]$。

由 ChatGPT 4.1 翻译

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1400。

测试点分布

出处：原题链接