解决代码WA问题：修改组合数计算及消除重复排列逻辑

### 🐞问题分析 原代码出现“WA”（Wrong Answer）可能是因为在计算组合数和最终结果时存在逻辑错误。具体来说，原代码在消除堆之间的重复排列时，对 `fastPow(fastPow(m, m), MOD - 2)` 的使用可能有误，这里应该是 `inv[m]` 用于消除 `m` 个堆的重复排列。 ### ✅修改后的代码 ```cpp #include <iostream> using namespace std; const int MOD = 1e9 + 7; const int MAXN = 1005; // 假设最大的 n 和 m 不超过 1000 long long fact[MAXN]; // 阶乘数组 long long inv[MAXN]; // 阶乘逆元数组 // 快速幂函数，用于计算 a^b % MOD long long fastPow(long long a, long long b) { long long res = 1; while (b > 0) { if (b & 1) { res = (res * a) % MOD; } a = (a * a) % MOD; b >>= 1; } return res; } // 预处理阶乘和阶乘逆元 void preprocess() { fact[0] = 1; for (int i = 1; i < MAXN; ++i) { fact[i] = (fact[i - 1] * i) % MOD; } inv[MAXN - 1] = fastPow(fact[MAXN - 1], MOD - 2); for (int i = MAXN - 2; i >= 0; --i) { inv[i] = (inv[i + 1] * (i + 1)) % MOD; } } // 计算组合数 C(n, k) % MOD long long combination(int n, int k) { if (k > n) return 0; return (fact[n] * inv[k] % MOD * inv[n - k]) % MOD; } int main() { preprocess(); // 预处理阶乘和阶乘逆元 int n, m; cin >> n >> m; long long ans = 1; int total = n * m; for (int i = 0; i < m; ++i) { ans = (ans * combination(total, n)) % MOD; total -= n; } // 消除堆之间的重复排列 ans = (ans * inv[m]) % MOD; cout << ans << endl; return 0; } ``` ### 📝代码解释 1. **快速幂函数 `fastPow`**：用于计算 `a^b % MOD`，采用二进制快速幂算法，时间复杂度为 $O(log b)$。 2. **预处理函数 `preprocess`**：预处理阶乘和阶乘逆元数组，方便后续计算组合数。 3. **组合数函数 `combination`**：根据组合数公式 $C(n, k)=\frac{n!}{k!(n - k)!}$ 计算组合数 $C(n, k) \% MOD$。 4. **主函数 `main`**：读取输入的 `n` 和 `m`，计算将 `n * m` 个元素分成 `m` 堆，每堆 `n` 个元素的方案数，最后消除堆之间的重复排列。 ######[AI问答 | 821点数解答 | 2026-05-31 15:32:57]