堆石子

有 $m$ 堆石子，编号为 $1, 2, \cdots, m$，其石子数量分别记为 $a_1, a_2, \cdots, a_m$。

现在要求第 $1$ 堆石子恰有 $n$ 个（即 $a_1 = n$），并且此后每堆石子的数量严格小于前一堆，即 $a_i < a_{i-1}$ ($2 \le i \le m$)。此外，每堆至少需要有一个石子，即 $a_i \ge 1$ ($1 \le i \le m$)。

在总石子数量不设限制的情况下，给定 $m \ge 2, n \ge 1$，有多少个满足要求的石子堆放方案？

两个方案不同，当且仅当，两个方案中至少有一堆石子数量不同。

如果不存在满足要求的方案，输出 $0$。由于方案数可能很大，请输出方案数对 $10^9 + 7$ 取模后的结果。

输入格式

输入一行两个正整数 $m$ 和 $n$。

输出格式

输出一个整数，表示总方案数对 $10^9 + 7$ 取模后的结果。

输入样例 1

3 5

输出样例 1

6

样例解释 1

有 $(5, 4, 3)$，$(5, 4, 2)$，$(5, 4, 1)$，$(5, 3, 2)$，$(5, 3, 1)$ 和 $(5, 2, 1)$ 共计 $6$ 种方案。

数据范围

数据点编号	数据范围	特殊性质
$1,2$	$2 \le m \le 100, 1 \le n \le 100$	$0 \le n - m \le 5$
$3,4,5$	$2 \le m \le 100, 1 \le n \le 10^8$	无
$6,7,8,9,10$	$2 \le m \le 10^5, 1 \le n \le 10^8$	无

题目要求构造一个长度为 $m$ 的严格递减正整数序列：

$a_1 > a_2 > a_3 > \dots > a_m \ge 1$

其中首项固定为 $a_1 = n$。

我们可以引入差分思想。令每两堆之间的差值为 $d_i$：

• $d_1 = a_1 - a_2$ （因为 $a_1 > a_2$，所以 $d_1 \ge 1$）
• $d_2 = a_2 - a_3$ （$d_2 \ge 1$）
• $\dots$
• $d_{m-1} = a_{m-1} - a_m$ （$d_{m-1} \ge 1$）
• 最后一堆：$d_m = a_m$ （因为 $a_m \ge 1$，所以 $d_m \ge 1$）

根据这些定义，我们可以把每一项反过来用 $d_i$ 表示出来。特别是首项 $a_1$：

$a_1 = d_1 + d_2 + d_3 + \dots + d_m$

题目已知 $a_1 = n$，所以问题等价于：

求满足 $d_1 + d_2 + \dots + d_m = n$，且满足每一个 $d_i \ge 1$ 的正整数解的个数。

隔板法

这是一个非常经典的组合数学模型：将 $n$ 个相同的物品分配给 $m$ 个不同的组（这里是 $d_1$ 到 $d_m$），要求每组至少分到一个。

我们可以使用隔板法来求解：

• 把 $n$ 个石子排成一排，它们之间一共有 $n-1$ 个空隙。
• 我们需要在这些空隙中插入 $m-1$ 个隔板，将石子分成 $m$ 份。
• 每一种插板的方案，都唯一对应了一组满足条件的 $(d_1, d_2, \dots, d_m)$ 序列。

因此，总方案数就是从 $n-1$ 个空隙中选出 $m-1$ 个位置放隔板的组合数：

$\text{方案数} = \binom{n-1}{m-1}$

边界与特殊情况判断

在直接计算组合数之前，需要注意以下几种情况：

1. 无法构造的情况：

   由于每一堆石子都必须比后一堆至少多 $1$ 个，且最后一堆至少为 $1$，那么最小的合法序列是 $(m, m-1, m-2, \dots, 1)$。

   此时首项 $a_1$ 至少要为 $m$。也就是说，如果 $n < m$，方案数直接为 0（此时 $\binom{n-1}{m-1}$ 在数学上也为 0）。

2. $m=1$ 的情况：

   虽然题目中说了 $m \ge 2$，但如果从公式来看，$\binom{n-1}{0} = 1$，也是合理的。

高效计算组合数

由于 $n$ 很大（$10^8$），我们不能预处理阶乘。但注意到组合数的展开式为：

$\binom{n-1}{m-1} = \frac{(n-1) \times (n-2) \times \dots \times (n-m+1)}{(m-1) \times (m-2) \times \dots \times 1}$

分子和分母都只有 $m-1$ 项。因为 $m \le 10^5$，我们完全可以在 $O(m)$ 的时间复杂度内计算出结果：

1. 分子：从 $n-1$ 开始往下乘 $m-1$ 项，边乘边对 $10^9+7$ 取模。
2. 分母：计算 $(m-1)! \pmod{10^9+7}$。
3. 除法变乘法：使用费马小定理求分母的模逆元。因为 $10^9+7$ 是质数，分母 $X$ 的逆元就是 $X^{10^9+5} \pmod{10^9+7}$，可以通过快速幂在 $O(\log(\text{mod}))$ 内求出。

参考代码

#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;

// 快速幂计算逆元
long long quick_pow(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

int main() {
    long long m, n;
    if (!(cin >> m >> n)) return 0;

    // 如果 n < m，无法凑出严格递减且最后一堆 >= 1 的方案
    if (n < m) {
        cout << 0 << endl;
        return 0;
    }

    // 计算组合数 C(n-1, m-1)
    // 分子: (n-1)*(n-2)*...*(n-m+1)
    // 分母: (m-1)!
    long long numerator = 1;
    long long denominator = 1;
    long long k = m - 1; // 需要乘的项数

    for (int i = 0; i < k; i++) {
        numerator = (numerator * ((n - 1 - i) % MOD)) % MOD;
        denominator = (denominator * (i + 1)) % MOD;
    }

    // 结果 = 分子 * 分母的逆元
    long long ans = (numerator * quick_pow(denominator, MOD - 2)) % MOD;

    cout << ans << endl;
    return 0;
}

复杂度分析

• 时间复杂度：$O(m)$，主要消耗在循环计算分子和分母上，快速幂只需要 $\log(10^9) \approx 30$ 次运算，完全能在一秒内跑完 $10^5$ 的数据。
• 空间复杂度：$O(1)$，只需要常数级别的变量空间。