非递归实现
查看原帖
非递归实现
180325
HaibaraAi1楼主2022/11/12 22:09

看大多数题解都是递归实现,为数不多的非递归实现也感觉比较复杂

请大家看看如下代码是否能被hack,还有什么可以改进的地方,谢谢!

#include <cctype>
#include <cstdio>
using ll=long long;
constexpr int N=1e5;
char c;
int T,i,n,m,p,ans,fac[N]{1,1},inv[N]{0,1};
inline void qscan(int &x){
	x=0;
	while(!isdigit(c))c=getchar();
	while(isdigit(c))x=x*10+(c&15),c=getchar();
}
inline int C(int n,int m){
	if(n<m)return 0;
	return ll(fac[n])*inv[fac[m]]*inv[fac[n-m]]%p;
}
int main(){
	qscan(T);
	while(T--){
		qscan(n),qscan(m),qscan(p);
		if(p==1){
			putchar(48),putchar(10);
			continue;	
		}
		n+=m;
		for(i=2;i<p;++i)fac[i]=ll(fac[i-1])*i%p,inv[i]=ll(p-p/i)*inv[p%i]%p;
		for(ans=1;m;n/=p,m/=p)ans=ll(ans)*C(n%p,m%p)%p;
		printf("%d\n",ans);
	}
}
2022/11/12 22:09
加载中...