开始的时候了解过卡特兰数，但是不会做题，只会套公式……好吧……略过不提。
题意：给你n和m，叫你求卡特兰数h[n]%m的结果。
首先，公式h[n]=h[n-1]*(4*n-2)/(n+1)【注意这里n从0开始，是式子中的某一项，所以在应用实例中要记得进行区分（此n非彼n）】
由于数据很大，要取模，但是因为取模后分母就不一定整除分子了，所以不能对于结果直接取模，要分别进行。【其实所以结果可能是个小数？那怎么可以取模……】所以对分子取模的时候要求他的乘法逆元，但是乘法逆元必须是两个数要互质才可以，所以还要进行因数分解。【嗯，其实对于整个过程还不是太了解的说，但是大体能懂= =】。将分子和分母都进行分解，分解成与m互质和不与m互质的两部分。对于分母，互质的直接相乘，然后取模，对于分子，消掉和分母相同的部分，剩下的就是和m互质的那一部分了。然后进行扩展欧几里得求逆元。然后估计这里保存的分母的因子是一路计算来的因数的个数（幂数），所以一定会让分子只剩和m互质的部分，，，，，啊，其实因为对于公式，一定算出来是个整数【虽然没有证为什么】，但是由于取模了所以就可能不能整除了，所以在这里对分母进行分解，保留其幂数，然后在对分子的运算过程就可以借此消掉，好让结果还是个整数【虽然依旧没有证为什么……】
写出来主要是因为想了快两个小时才稍稍摸到门道，不想思路就这样没有了，然后……等我继续更新吧……这道题一定要A掉……
【诶，感觉自己蠢爆了= =】
【嗯，然后记得提醒自己，想不通就是想不通，好好想，不要以“可能是哪里没学过”这样的理由东看西看浪费时间，勇于尝试勇于想】
这是第一份代码，答案是对的，但是TLE了，试了一下数据，确实是跑得慢了，怎么优化都没有用。
#include <stdio.h>
#include <string.h>
#define maxn 500100
#define ll __int64
ll num[maxn],prim[maxn];
int fint[maxn];
int top;
int n,m;
/*void fint()
{
int i,j,k;
memset(su,1,sizeof(su));
su[0]=su[1]=0;
for(i=2;i<maxn;i++)
{
if(su[i])
for(j=i+i;j<maxn;j+=i)
su[i]=0;
}
}*/
void exgcd(ll a,ll b,ll &x,ll &y) ///模板
{
if(b==0)
{
x=1;
y=0;
}
else
{
ll t;
exgcd(b,a%b,x,y);
t=x; x=y;
y=t-(a/b)*y;
}
}
void cal1(ll &ans,ll x)
{
ll i,j,k;
j=x;
for(i=0;i<top;i++)
{
while(j%prim[i]==0)
{
j/=prim[i];
num[i]++;
}
}
ans=(ans)*(j);
ans%=m;
}
void cal2(ll &ans,ll x) ///取模可以对
{
int i,j,k;
j=x;
for(i=0;i<top;i++)
{
while((j%prim[i]==0)&&num[i]>0)
{
j/=prim[i];
num[i]--;
}
}
if(j>1)
{
ll xx,yy;
exgcd(j,m,xx,yy);
xx=(xx%m+m)%m; ///这一步很重要，有的时候逆元算出来貌似是负数，加这一步可以避免
ans=(ans*xx)%m;
}
}
ll quickpow(ll m,ll n,ll k)
{
ll b = 1;
while (n > 0)
{
if (n & 1)
b = (b*m)%k;
n = n >> 1 ;
m = (m*m)%k;
}
return b;
}
int main()
{
//int n,m;
freopen("out.txt","w",stdout);
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==1||n==2) {printf("0\n");continue;}
// memset(num,0,sizeof(num));
n-=2;
ll i,j,k;
j=m;
top=0;
for(i=2;i*i<=m;i++)
{
if(j%i==0)
{
prim[top++]=i;
while(j%i==0)
j/=i;
}
}
if(j>1) prim[top++]=j;
for(i=0;i<top;i++)
num[i]=0;
//h[1]=1;//h[2]=2;h[3]=5;
ll ans=1;
ll tmp;
for(i=2;i<=n;i++)
{
cal1(ans,4*i-2);
cal2(ans,i+1);
}
tmp=ans;
for(j=0;j<top;j++)
{
tmp*=quickpow(prim[j],num[j],m); ///这里改成用快速幂
/*for(k=0;k<num[j];k++)
tmp=(tmp*prim[j])%m;*/
}
printf("%I64d\n",tmp);
}
return 0;
}
嗯……学习了一下标程……
没有求逆元，没有递推式。
用的公式是这一种：h[n]=(2n!)/(n!*(n+1)!)
但是不知道为什么对于n的阶乘的因子分解是这样做的……效率高很多。然后素数记得开得大一点。
#include <stdio.h>
#include <string.h>
#define maxn 1000100
int prime[maxn],que[maxn];
int top;
int div(int x,int y) ///我不懂的因子分解……
{
int r=0;
//int tmp=x;
while(x)
{
r+=x/=y;
}
return r;
}
void fint()
{
int i,j,k;
memset(prime,1,sizeof(prime));
prime[0]=prime[1]=0;
for(i=2;i<maxn;i++)
{
if(prime[i])
for(j=i+i;j<maxn;j+=i)
prime[j]=0;
}
for(i=2;i<maxn;i++)
if(prime[i]) que[top++]=i;
}
int ppow(int a,int b,int m){
int r=1,t=a%m;
while(b){
if(b&1)r=(r*t)%m;
t=(t*t)%m;
b>>=1;
}
return r;
}
int solve(int n,int m)
{
int i,j,k;
int nn=n<<1;
//fint();
int r=1;
for(i=0;i<top&&que[i]<=nn&&r;i++)
{
//printf("**%d\n",que[i]);
j=div(nn,que[i]);//printf("%d ",j);
j-=div(n,que[i]);//printf("%d ",j);
j-=div(n+1,que[i]);//printf("%d\n",j);
r=(r*ppow(que[i],j,m))%m;
// printf("%d\n",r);
}
return r;
}
int main()
{
int n,m;
top=0;
fint();
//printf("%d\n",top);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d%d",&n,&m)!=EOF)
{
printf("%d\n",solve(n-2,m));
}
return 0;
}
****************************************
估摸着需要鉴别一下两个公式的使用处。
第一个递推式就适合要求过程和的。
第二个式子就适合要求单个结果的。