首页 > 代码库 > HDU 3240

HDU 3240

2024-07-26 12:56:54   217人阅读

求卡特兰数前N项的和模M。

直接求必定是不可能的，卡特兰数太大了。想了好久，本打算把位数拆成素数相乘，然后记录下各素数的个数计算。可惜，TLE。。。。因为N太大了。

除法必定是要用到逆元的，但分母与M不一定互质。M拆成素数相乘形式，记录下各个素数在数组PRIME。于是，可以把4*i-2和i+1拆成素数相乘，若在PRIME中，则必定是与M不互质的，只能将个数记在NUM中，4*i-2的+1，i+1的-1。那么，把各素数约去后的i-1剩下的必与M互质。于是就可以和M求逆元的。

可以看程序，很容易懂。

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define LL __int64#define NP 30000using namespace std;LL prime[NP];int num[NP],np;void exgcd(__int64 a,__int64 b,__int64 &x,__int64 &y){    if(b==0){        x=1; y=0;        return ;    }    exgcd(b,a%b,x,y);    __int64 t=x;    x=y;    y=t-a/b*y;}void cal1(LL &ans,LL tp,LL &m){	for(int i=0;i<np&&prime[i]<=tp;i++){		if(tp%prime[i]==0){			while(tp%prime[i]==0){				num[i]++;				tp/=prime[i];			}		}	}	ans=(ans*tp)%m;}void cal2(LL &ans,LL tp,LL &m){	LL x,y;	for(int i=0;i<np&&prime[i]<=tp;i++){		if(tp%prime[i]==0){			while(tp%prime[i]==0){				num[i]--;				tp/=prime[i];			}		}	}	exgcd(tp,m,x,y);	ans=(ans*((x%m+m)%m))%m;}int main(){	LL n,m;	while(scanf("%I64d%I64d",&n,&m),n||m){		LL tp=m; np=0;		for(LL i=2;i*i<=tp;i++){			if(tp%i==0){				prime[np++]=i;				while(tp%i==0)				tp/=i;			}		}		if(tp>1)		prime[np++]=tp;		memset(num,0,sizeof(num));		LL ans=1,res=1,tmp;		for(LL i=2;i<=n;i++){			cal1(ans,4*i-2,m);			cal2(ans,i+1,m);			tmp=ans;			for(int k=0;k<np;k++)				if(num[k])				for(int p=0;p<num[k];p++)				tmp=(tmp*prime[k])%m;			res=(res+tmp)%m;		}		printf("%I64d\n",res);	}	return 0;}

　　

HDU 3240


联系
我们