C++实现牛排队问题：计算满足条件的排队方法数

以下是解决该问题的C++代码： ```cpp #include <iostream> using namespace std; const int MOD = 1000000007; // 计算组合数 C(n, k) int combination(int n, int k) { if (k > n) return 0; if (k == 0 || k == n) return 1; int result = 1; for (int i = 1; i <= k; ++i) { result = 1LL * result * (n - i + 1) % MOD; result = 1LL * result * pow(i, MOD - 2, MOD) % MOD; } return result; } // 快速幂函数 int pow(int a, int b, int mod) { int res = 1; while (b) { if (b & 1) res = 1LL * res * a % mod; a = 1LL * a * a % mod; b >>= 1; } return res; } int main() { int n, k; cin >> n >> k; // 先放置 k 头公牛，需要 k - 1 头母牛隔开 // 那么剩余的母牛数量为 n - k - (k - 1) = n - 2 * k + 1 // 可以将问题转化为在 n - k + 1 个位置中选 k 个位置放公牛 int ans = combination(n - k + 1, k); cout << ans << endl; return 0; } ``` ### 代码解释： 1. **组合数计算**：`combination` 函数用于计算组合数 $C(n, k)$，使用了费马小定理来计算逆元，以处理取模运算。 2. **快速幂函数**：`pow` 函数用于快速计算 $a^b \bmod mod$。 3. **问题转化**：先放置 `k` 头公牛，需要 `k - 1` 头母牛隔开，那么剩余的母牛数量为 `n - k - (k - 1) = n - 2 * k + 1`。可以将问题转化为在 `n - k + 1` 个位置中选 `k` 个位置放公牛。 ### 复杂度分析： - 时间复杂度：$O(k \log MOD)$，主要是计算组合数和快速幂的时间。 - 空间复杂度：$O(1)$，只使用了常数级的额外空间。 ######[AI问答 | 620点数解答 | 2026-05-31 15:51:49]