题目描述
有 m 堆石子，编号为 1,2,⋯,m，其石子数量分别记为 a1,a2,⋯,am。
现在要求第 1 堆石子恰有 n 个（即 a1=n），并且此后每堆石子的数量严格小于前一堆，即 ai<ai−1 (2≤i≤m)。此外，每堆至少需要有一个石子，即 ai≥1 (1≤i≤m)。
在总石子数量不设限制的情况下，给定 m≥2,n≥1，有多少个满足要求的石子堆放方案？
两个方案不同，当且仅当，两个方案中至少有一堆石子数量不同。
如果不存在满足要求的方案，输出 0。由于方案数可能很大，请输出方案数对 109+7 取模后的结果。
输入格式
输入一行两个正整数 m 和 n。
输出格式
输出一个整数，表示总方案数对 109+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≤m≤100,1≤n≤100 | 0≤n−m≤5 |
| 3,4,5 | 2≤m≤100,1≤n≤108 | 无 |
| 6,7,8,9,10 | 2≤m≤105,1≤n≤108 |
代码实现：
#include <iostream> using namespace std; typedef long long ll; const int MOD = 1e9 + 7; const int MAXK = 1e5 + 10; ll powmod(ll a, ll b) { ll res = 1; while(b) { if(b&1) res = res * a % MOD; a = a * a % MOD; b >>=1; } return res; } int main() { ll m, n; cin >> m >> n; ll K = m - 1; ll N = n - 1; if(N < K) { cout << 0 << endl; return 0; } ll numer = 1; for(ll i = 0; i < K; i++) { ll term = (N - i) % MOD; numer = numer * term % MOD; } ll fact = 1; for(ll i = 1; i <= K; i++) { fact = fact * i % MOD; } ll inv_fact = powmod(fact, MOD - 2); ll ans = numer * inv_fact % MOD; cout << ans << endl; return 0; }
