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

### 📝问题分析 原代码超时（TLE）的主要原因在于每次调用 `factorial` 函数计算阶乘时，时间复杂度较高，并且每次计算组合数都重复计算阶乘，导致整体时间复杂度增加。可以通过预处理阶乘和阶乘的逆元来优化，避免重复计算。 ### 💻优化后的代码 ```cpp #include <iostream> using namespace std; const int MOD = 1e9 + 7; const int MAXN = 1000005; // 假设最大值不超过1000000 // 预处理阶乘和阶乘的逆元 long long fact[MAXN], inv_fact[MAXN]; // 快速幂计算 a^b % MOD long long fast_pow(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(int n) { fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = (fact[i - 1] * i) % MOD; } inv_fact[n] = fast_pow(fact[n], MOD - 2); for (int i = n - 1; i >= 0; i--) { inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD; } } // 计算组合数 C(n, k) long long combination(long long n, long long k) { if (k > n) return 0; return (fact[n] * inv_fact[k] % MOD * inv_fact[n - k]) % MOD; } int main() { int n, m; cin >> n >> m; long long ans = 1; long long total = n * m; // 预处理阶乘和阶乘的逆元 preprocess(total); for (int i = 0; i < n; i++) { ans = (ans * combination(total, m)) % MOD; total -= m; } cout << ans << endl; return 0; } ``` ### 💡代码解释 1. **预处理阶乘和阶乘的逆元**：通过 `preprocess` 函数，预先计算出从 `0` 到 `total` 的阶乘和阶乘的逆元，避免在计算组合数时重复计算阶乘。 2. **快速幂计算逆元**：使用 `fast_pow` 函数计算阶乘的逆元，时间复杂度为 $O(log MOD)$。 3. **计算组合数**：通过预处理的阶乘和阶乘的逆元，直接计算组合数，时间复杂度为 $O(1)$。 ### ⏱️复杂度分析 - **时间复杂度**：预处理阶乘和阶乘的逆元的时间复杂度为 $O(total)$，计算组合数的时间复杂度为 $O(n)$，因此总的时间复杂度为 $O(total + n)$。 - **空间复杂度**：主要用于存储阶乘和阶乘的逆元，空间复杂度为 $O(total)$。 ######[AI问答 | 810点数解答 | 2026-05-31 15:28:14]