P10514 考试 题解

· · 题解

考试题解

不妨先找出选出的 k 名同学，要求这些同学全对也就是做错的同学都在剩余的学生中。第 i 次在剩下的 n-k 名学生中选 a_i 个，概率是 \frac{C_{n-k}^{a_i}}{C_{n}^{a_i}}。所有概率相乘即为答案，注意特殊考虑 n-k < a_i 的无解情况。

std 为费马小定理求逆元，若使用线性求逆元时间复杂度 O(n)。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<ctime>
#include<random>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=1e5+10;
const int mod=998244353;
int n,m,k,ans=1,a[N];
int f[N],g[N];
inline int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
inline int inv(int x){
    return ksm(x,mod-2);
}
inline int C(int n,int m){
    if(n<0||m<0||n<m)return 0;
    return f[n]*g[m]%mod*g[n-m]%mod;
}
signed main()
{
    f[0]=g[0]=1;
    for(int i=1;i<N;i++){
        f[i]=f[i-1]*i%mod;
        g[i]=g[i-1]*inv(i)%mod;
    }
    n=read(),m=read(),k=read();
    for(int i=1;i<=m;i++){
        a[i]=read();
        ans=ans*(C(n-k,a[i])*inv(C(n,a[i]))%mod)%mod;
    }
    cout<<ans;
    return 0;
}