自动搬运

查看原文

来自洛谷，原作者为

	cjh20090318 求知若饥，虚心若愚。即使我无法如你一般成为照亮云端的雷霆，但也可以做黑夜里的一缕烛火。

搬运于2025-08-24 21:14:36，当前版本为作者最后更新于2023-05-18 15:17:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

大家好，我是 CQ-C2024 蒟蒻 CJH。

最近回来复习一下组合数，于是就看到了这一道题。

题意

给定两个整数 $n,m$，求出 $\dbinom{n}{m}$。

分析

根据组合数的定义可知：

根据数据范围 $1 \leq T \leq 5 \times 10^6$，$0 \leq m \leq n \leq N \leq 5 \times 10^6$，可知单次求组合数时间复杂度为 $O(1)$ 才行。

很容易想到预处理阶乘以及乘法逆元的阶乘。

总体时间复杂度 $O(N+T)$。

代码

//the code is from chenjh
#include<cstdio>
#define MAXN 5000005
typedef long long LL;
const int mod=998244353;
int f[MAXN],inv[MAXN];//阶乘以及乘法逆元。
int main(){
	int T,N;scanf("%d%d",&T,&N);
	f[0]=f[1]=inv[0]=inv[1]=1;//记得赋初始值！
	for(int i=2;i<=N;i++) f[i]=(LL)f[i-1]*i%mod,inv[i]=(LL)(mod-mod/i)*inv[mod%i]%mod;//递推阶乘和逆元，中间运算可能会超过 long long，所以需要临时转换类型。
	for(int i=1;i<=N;i++) inv[i]=(LL)inv[i-1]*inv[i]%mod;//预处理逆元的阶乘。
	int ans=0;
	for(int n,m;T--;)scanf("%d%d",&n,&m),ans^=(LL)f[n]*inv[m]%mod*inv[n-m]%mod;//根据组合数公式求出组合数。
	printf("%d\n",ans);
	return 0;
}

关于此题的题外话

因为此题只有一组数据，所以用以下的代码也可以 AC 此题：

main(){puts("522716868");}

故请求管理员加强数据。