hdu_4828_Grids(卡特兰数+逆元)

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=4828

题意:中文,不解释

题解:实际就是一个卡特兰递推: Catalan(n+1)= Catalan(n)*(4*n+2)/(n+2)(mod M),求的时候要用逆元,这里我用筛法求逆元,用空间换时间,快速幂AC要用800+ms,筛法逆元只需要200+ms。

 #include<cstdio>
int maxn=,mod=,i;
long long f[maxn],inv[maxn]={,};
void init(){
for(i=;i<maxn-;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;//筛法求逆元
for(i=,f[]=;i<maxn-;i++)f[i]=(((f[i-]*(*i-))%mod)*inv[i+])%mod;
}
int main(){
init();
int t,n,ic=;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("Case #%d:\n%lld\n",ic++,f[n]);
}
return ;
}
上一篇:JDBC学习笔记(8)——数据库连接池(dbcp&C3P0)


下一篇:如何将python3.6软件的py文件打包成exe程序