自动搬运

查看原文

来自洛谷，原作者为

	听取MLE声一片 如果我当时做的再多一点，结局会不会不同呢？

搬运于2025-08-24 22:58:45，当前版本为作者最后更新于2024-05-19 20:43:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考试题解

不妨先找出选出的 $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;
}