【算法】Catalan数

【题解】

学了卡特兰数就会啦>_<!

因为奇偶各自递增，所以确定了奇偶各自的数字后排列唯一。

那么就是给2n个数分奇偶了，是不是有点像入栈出栈序呢。

将做偶数标为-1，做奇数标为+1，显然当偶数多于奇数时不合法，因为它压不住后面的奇数。

然后其实这种题目，打表就可知啦……QAQ

然后问题就是求1/(n+1)*C(2n,n)%p了，p不一定是素数。

参考的解法。

看到网上清一色的素数筛+分解质因数解法，思考了好久，感觉写了假的礼物……

后来试了一下发现礼物的做法慢得多，原因应该是礼物解法复杂度O(min(n,P))而且常数大，分解质因数O(n)，但我觉得也带常数呀？

很奇怪……不过反正n太大只能用礼物的做法，不大的话分解质因数应该更快。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long longusing namespace std;/*------------------------------------------------------------*/const int inf=0x3f3f3f3f,maxn=3000010;ll n,P,m,p[200],pc[200],M[200],a[200];ll num,fac[maxn];ll power(ll x,ll k,ll p){    ll ans=1;    while(k>0)    {        if(k&1)ans=ans*x%p;        x=x*x%p;        k>>=1;    }    return ans;}void exgcd(ll a,ll b,ll &x,ll &y){    if(!b){x=1;y=0;return;}    else {exgcd(b,a%b,y,x);y-=x*(a/b);}}ll inv(ll x,ll p){    ll xx,yy;    exgcd(x,p,xx,yy);    return ((xx%p)+p)%p;}ll calc(ll x,ll p,ll pc){    if(x
           
            1;i++) { if(nowP%i==0){p[++m]=i;pc[m]=1;} while(nowP%i==0){pc[m]*=i;nowP/=i;} } if(nowP>1){p[++m]=nowP;pc[m]=nowP;} ll ans=0; for(ll i=1;i<=m;i++) { M[i]=P/pc[i]; a[i]=work(p[i],pc[i]); ans=(ans+a[i]*M[i]%P*inv(M[i],pc[i])%P)%P; } printf("%lld",(ans%P+P)%P);//答案一定要记得取非负 return 0;}