一、题目回顾

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

1. $len(a)=len(b)=m$
2. $1\le a_i,b_i\le n$
3. $\forall i, a_i\le b_i$
4. $a$ 非递减：$a_1\le a_2\le\dots\le a_m$
5. $b$ 非递增：$b_1\ge b_2\ge\dots\ge b_m$

答案对 $10^9+7$ 取模。

---

二、核心数学推导（关键结论）

1. 条件转化

原约束：

$$\begin{align*} a_1 &\le a_2 \le \dots \le a_m \\ b_1 &\ge b_2 \ge \dots \ge b_m \\ \forall i, a_i &\le b_i \end{align*} $$

可等价变换为一个链式约束：

$$a_1 \le a_2 \le \dots \le a_m \le b_m \le b_{m-1} \le \dots \le b_1 $$

这等价于：从 $1\sim n$ 中可重复地选择 $2m$ 个非递减元素。

2. 组合数公式

可重组合公式（隔板法）： 从 $n$ 个元素中可重复选 $k$ 个的方案数：

$$\binom{n+k-1}{k}$$

本题中 $k=2m$，因此总方案数：

$$\boldsymbol{\binom{n+2m-1}{2m}}$$

---

三、标程代码详解

完整代码

#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;       // 题目要求取模
const int MAX = 3010;          // 足够大：n+2m ≤ 1000+20=1020

long long C[MAX][MAX];          // 组合数表：C[i][j] = C(i,j)

// 预处理杨辉三角，计算所有组合数
void precompute() {
    for (int i = 0; i < MAX; i++) {
        C[i][0] = 1;           // C(i,0)=1
        for (int j = 1; j <= i; j++) {
            // 杨辉三角递推：C(i,j)=C(i-1,j-1)+C(i-1,j)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
}

int main() {
    precompute();              // 先打表
    int n, m;
    cin >> n >> m;
    int total = n + 2*m - 1;   // 公式上标
    int choose = 2*m;          // 公式下标
    cout << C[total][choose] << endl;
    return 0;
}

---

四、代码核心解释

1. 组合数预处理（杨辉三角）

递推公式：

$$C(i,j) = C(i-1,j-1) + C(i-1,j)$$

• 边界：$C(i,0)=1$
• 每一步取模 $\boldsymbol{10^9+7}$

2. 公式计算

$$\text{答案} = C(n+2m-1,\ 2m) \bmod (10^9+7)$$

3. 数据范围

• $n\le 1000,\ m\le 10$
• $2m\le 20$
• $n+2m-1\le 1019$ MAX=3010 完全足够。

---

五、样例验证

样例 1

输入：$2\ 2$

$$C(2+4-1,4)=C(5,4)=5$$

输出：$5$ ✅

样例 2

输入：$10\ 1$

$$C(10+2-1,2)=C(11,2)=55$$

输出：$55$ ✅

---

六、复杂度分析

• 预处理：$O(MAX^2) = 3010^2 \approx 9\times10^6$
• 询问：$O(1)$ ✅ 完美通过时间/空间限制

---

七、总结

1. 题型：组合数学 + 可重组合
2. 核心公式：$\boldsymbol{\dbinom{n+2m-1}{2m}}$
3. 实现：杨辉三角预处理组合数
4. 优点：代码极短、速度最快、数学最优美
5. 匹配：与你提供的 Python 代码完全等价