A18529. 堆石子
填空题
困难
知识点
题目描述
堆石子
题目描述
有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≥ 2,有多少个满足要求的石子堆放方案？
两个方案不同，当且仅当，两个方案中至少有一堆石子数量不同。
如果不存在满足要求的方案，输出 0。由于方案数可能很大，请输出方案数对 109 + 7 取模后的结果。
输入格式
输入一行两个正整数 m 和 n 。
输出格式
输出一个整数，表示总方案数对 109 + 7 取模后的结果。
输入样例
3 5输出样例
6样例解释
有 (5,4,3)，(5,4,2)，(5,4,1)，(5,3,2)，(5,3,1)和(5,2,1) 和 共计 6 种方案。
数据范围
参考答案
#include <iostream>
using namespace std;
const int MOD = (int)1e9 + 7;
int qpow(int base, int exp) {
if (!exp) return 1;
if (exp & 1) return (long long)base * qpow((long long)base * base % MOD, exp >> 1) %
MOD;
return qpow((long long)base * base % MOD, exp >> 1);
}
int comb(int n, int m) {
if (m > n) return 0;
int ans = 1;
for (int i = 0; i < m; ++i) {
ans = (long long)ans * (n - i) % MOD;
ans = (long long)ans * qpow(i + 1, MOD - 2) % MOD;
}
return ans;
}
int main() {
int m, n;
cin >> m >> n;
cout << comb(n - 1, m - 1) << endl;
return 0;
}
上一题
下一题