题解：P10514 考试

Solution

对于第 \(i\) 道题，\(k\) 个随机选中的同学全部答对的概率为：

\[P_i = \frac{\binom{n - a_i}{k}}{\binom{n}{k}} \]

由于题目相互独立，总概率为：

\[P = \prod_{i=1}^{m} P_i = \prod_{i=1}^{m} \frac{\binom{n - a_i}{k}}{\binom{n}{k}} \]

特判：

• 若 \(\exists a_i > n - k\)（即答对该题人数不足 \(k\) 人），则 \(P = 0\)。
• 当 \(k = 0\) 时，\(P = 1\)。

所以总结一下：

1. 预处理阶乘数组 \(jc\) 和阶乘逆元数组 \(inv\_jc\)。
2. 计算分母 \(\binom{n}{k}\) 及其逆元。
3. 遍历每道题：
   • 若 \(n - a_i < k\)，则输出 \(0\) 并退出。
   • 否则计算 \(\binom{n - a_i}{k}\) 并累乘概率。

记得取模！

Code

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const ll MOD = 998244353;
const int MAX_N = 1e5 + 10;
ll n, m, k, a[MAX_N];
ll jc[MAX_N], inv_jc[MAX_N]; ll qpow(ll a, ll b) {ll res = 1;while (b) {if (b & 1) res = res * a % MOD;a = a * a % MOD;b >>= 1;}return res;
}int main() {cin >> n >> m >> k;for (int i = 1; i <= m; ++i) cin >> a[i];// 特判 k=0 的情况if (k == 0) {cout << 1; // 概率为 1return 0;}// 预处理阶乘和阶乘逆元jc[0] = 1;for (int i = 1; i < MAX_N; ++i) jc[i] = jc[i - 1] * i % MOD;inv_jc[MAX_N - 1] = qpow(jc[MAX_N - 1], MOD - 2);for (int i = MAX_N - 2; i >= 0; --i) inv_jc[i] = inv_jc[i + 1] * (i + 1) % MOD;// 计算分母及其逆元ll denom = jc[n] * inv_jc[k] % MOD * inv_jc[n - k] % MOD;ll inv_denom = qpow(denom, MOD - 2);ll ans = 1;for (int i = 1; i <= m; ++i) {if (n - a[i] < k) {ans = 0;break;}ll num = jc[n - a[i]] * inv_jc[k] % MOD * inv_jc[n - a[i] - k] % MOD;ans = ans * (num * inv_denom % MOD) % MOD;}cout << ans;return 0;
}