Problem Description

There are 5 distinct binary trees of 3 nodes:

Let T(n) be the number of distinct non-empty binary trees of no more than
n nodes, your task is to calculate T(n) mod
m.

 

Input

The input contains at most 10 test cases. Each case contains two integers n and m (1 <= n <= 100,000, 1 <= m <= 10
⁹) on a single line. The input ends with n = m = 0.

 

Output

For each test case, print T(n) mod m.

 

Sample Input

 

Sample Output

 

Source

2009 “NIT Cup” National Invitational Contest

 

Recommend

zhonglihua

乘法逆元，我们知道，卡特兰数可以由公式，h[i]=h[i-1]*(4*i-2)/(i+1)得出，但是，我们知道，由于，是取过模的，我们如果，不还是直接除的话，是不对的，所以，我们要用乘法逆元就可以了，但是，乘法逆元，要求是互质的数， 这里，我们，把m的质因子保存下来，互素的直接算就可以了 ！

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

__int64 vec[40],num[40],m,index;

__int64 ectgcd(__int64 a,__int64 b,__int64 & x,__int64 & y)

{

    if(b==0){x=1;y=0;return a;}

    __int64 d=ectgcd(b,a%b,x,y);

    __int64 t=x;x=y;y=(t-a/b*y);

    return d;

}

int main()

{

   __int64 i,j,tempm,t,k,l;

   __int64 n;

   while(scanf("%I64d%I64d",&n,&m)!=EOF&&n+m)

   {

       memset(num,0,sizeof(num));

       index=0;

       tempm=m;

       for(i=2;i*i<=m;i++)

       {

          if(m%i==0)

          {

              vec[index++]=i;

              while(m%i==0)

              {

                  m=m/i;

              }

          }

       }

       if(m!=1)

       vec[index++]=m;

       m=tempm;

       __int64 res=1,result=0;

       for(i=1;i<=n;i++)

       {

           k=4*i-2;

            for(j=0;j<index;j++)

            {

                if(k%vec[j]==0)

                {

                    while(k%vec[j]==0)

                    {

                        k=k/vec[j];

                        num[j]++;

                    }

                }

            }

            res=res*k%m;

            k=i+1;

            for(j=0;j<index;j++)

            {

                if(k%vec[j]==0)

                {

                    while(k%vec[j]==0)

                    {

                        k=k/vec[j];

                        num[j]--;

                    }

                }

            }

            if(k!=1)

            {

                __int64 x,y;

               ectgcd(k,m,x,y);

                x=x%m;

                if(x<0)

                x+=m;

                res=res*x%m;

            }

            l=res;

            for(j=0;j<index;j++)

                for(t=0;t<num[j];t++)

                l=l*vec[j]%m;

          result=(result+l)%m;

       }

       printf("%I64d\n",result);

   }

    return 0;

}