求解二项式系数和 $S = \sum_{i=1}^N \sum_{j=1}^M \binom{A_i}{B_j} \pmod{998244353}$：思路、优化与代码实现

我们要求计算： \[ S = \sum_{i=1}^N \sum_{j=1}^M \binom{A_i}{B_j} \pmod{998244353} \] 其中当 \( A_i < B_j \) 时，\(\binom{A_i}{B_j} = 0\)。 --- ## 思路 1. 组合数范围 设 \( \maxA = \max(A_1,\dots,A_N) \)，\(\maxB = \max(B_1,\dots,B_M)\)。 组合数 \(\binom{n}{k}\) 只在 \(n \ge k\) 时非零，且 \(n\) 最大为 \(\maxA\)，\(k\) 最大为 \(\maxB\)。 2. 预计算组合数 可以预计算 \(n = 0,1,\dots,\maxA\) 和 \(k = 0,1,\dots,\maxA\) 的所有组合数 \(C[n][k] \mod 998244353\)。 使用公式： \[ C[n][k] = C[n-1][k-1] + C[n-1][k] \] 边界 \(C[n][0] = 1\)，\(C[n][n] = 1\)，其余 \(C[n][k] = 0\) 当 \(k > n\)。 3. 计算总和 对每个 \(A_i\)，对每个 \(B_j\)，若 \(A_i \ge B_j\)，则加 \(C[A_i][B_j]\) 到答案。 4. 复杂度 预计算 \(O(\maxA^2)\)，求和 \(O(NM)\)。 若 \(N,M\) 很大但 \(\maxA\) 较小可行，否则需要优化。 --- ## 优化 注意到： \[ S = \sum_{j=1}^M \sum_{i=1}^N \binom{A_i}{B_j} \] 固定 \(B_j = k\)，我们需要 \(\sum_{i=1}^N \binom{A_i}{k}\)。 可以预计算： \[ \text{freq}[n] = \text{A 中等于 } n \text{ 的数量} \] 那么： \[ \text{sumC}[k] = \sum_{n \ge k} \text{freq}[n] \cdot \binom{n}{k} \] 于是： \[ S = \sum_{j=1}^M \text{sumC}[B_j] \] 这样复杂度为 \(O(\maxA^2 + N + M)\)。 --- ## 代码实现（C++） ```cpp #include <iostream> #include <vector> using namespace std; const int MOD = 998244353; int main() { int N, M; cin >> N >> M; vector<int> A(N), B(M); int maxA = 0, maxB = 0; for (int i = 0; i < N; i++) { cin >> A[i]; if (A[i] > maxA) maxA = A[i]; } for (int i = 0; i < M; i++) { cin >> B[i]; if (B[i] > maxB) maxB = B[i]; } // 预计算组合数 C[n][k] vector<vector<int>> C(maxA + 1, vector<int>(maxA + 1, 0)); for (int n = 0; n <= maxA; n++) { C[n][0] = C[n][n] = 1; for (int k = 1; k < n; k++) { C[n][k] = (C[n-1][k-1] + C[n-1][k]) % MOD; } } // 频率数组 vector<int> freq(maxA + 1, 0); for (int x : A) freq[x]++; // sumC[k] = sum_{n>=k} freq[n] * C[n][k] vector<int> sumC(maxA + 1, 0); for (int k = 0; k <= maxA; k++) { long long s = 0; for (int n = k; n <= maxA; n++) { s = (s + 1LL * freq[n] * C[n][k]) % MOD; } sumC[k] = s; } // 计算结果 long long ans = 0; for (int j = 0; j < M; j++) { if (B[j] <= maxA) { ans = (ans + sumC[B[j]]) % MOD; } // 否则 B[j] > maxA，组合数为 0，不加 } cout << ans << endl; return 0; } ``` --- 我在以往的开发过程中，碰到过以下几点需要格外小心处理的地方： 1. 组合数预计算时注意数组大小，应设为 maxA+1 避免越界。 2. 当 k > n 时组合数为 0，代码中已通过循环 n>=k 处理。 3. 大数累加时及时取模，防止溢出。 ######[AI写代码神器 | 1147点数解答 | 2025-11-15 20:57:58]