修改后的组合数计算代码解决WA问题

### 🐞问题分析 原代码的思路是将 \(n\times m\) 个元素进行分组，每组 \(n\) 个元素，然后计算组合数的乘积，最后消除堆之间的重复排列。但代码存在问题，在消除重复排列时，直接乘以 \(inv[m]\) 是错误的。因为这里的重复排列是由于 \(m\) 个堆的全排列导致的，应该除以 \(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; } // 消除堆之间的重复排列，这里应该乘以 m! 的逆元 ans = (ans * inv[m]) % MOD; cout << ans << endl; return 0; } ``` ### 🔍代码解释 1. **快速幂函数 `fastPow`**：用于计算 \(a^b\bmod MOD\)，通过二进制拆分的方法，将时间复杂度从 \(O(b)\) 降低到 \(O(\log b)\)。 2. **预处理函数 `preprocess`**：计算 \(1\) 到 \(MAXN - 1\) 的阶乘和阶乘的逆元，方便后续计算组合数。 3. **组合数函数 `combination`**：根据组合数公式 \(C(n,k)=\frac{n!}{k!(n - k)!}\)，利用预处理好的阶乘和阶乘逆元计算组合数。 4. **主函数 `main`**： - 首先调用 `preprocess` 函数进行预处理。 - 读取输入的 \(n\) 和 \(m\)。 - 循环 \(m\) 次，每次从剩余元素中选取 \(n\) 个元素，计算组合数并累乘到 `ans` 中。 - 最后乘以 \(m!\) 的逆元，消除堆之间的重复排列。 ### 注意事项 - 代码中假设 \(n\) 和 \(m\) 不超过 \(1000\)，如果 \(n\) 或 \(m\) 更大，需要调整 `MAXN` 的值。 - 代码中使用了取模运算，确保结果不会溢出。 ######[AI问答 | 1016点数解答 | 2026-05-31 15:34:47]