优化代码解决组合数计算WA问题

### 🐞问题分析 原代码出现 `WA`（Wrong Answer）可能是因为在计算组合数和最终结果时，存在一些细节没有处理好。特别是在计算组合数时，原代码中使用的方法在处理较大的 `n` 和 `k` 时可能会出现精度问题。我们可以使用预处理阶乘和阶乘逆元的方法来优化组合数的计算。 ### 💡修改后的代码 ```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 * fastPow(fastPow(m, m), MOD - 2)) % MOD; cout << ans << endl; return 0; } ``` ### 📝代码解释 1. **预处理阶乘和阶乘逆元**： - `fact` 数组用于存储阶乘，`inv` 数组用于存储阶乘的逆元。 - 在 `preprocess` 函数中，先计算阶乘，然后通过快速幂计算最大阶乘的逆元，再通过递推计算其他阶乘的逆元。 2. **组合数计算**： - 使用预处理好的阶乘和阶乘逆元来计算组合数，避免了原代码中重复计算分子和分母的问题。 3. **最终结果计算**： - 原代码的逻辑不变，通过循环计算组合数的乘积，最后消除堆之间的重复排列。 ######[AI问答 | 810点数解答 | 2026-05-31 15:31:34]