POJ 2084 Game of Connections

卡特兰数。

#include<stdio.h>

#include<string.h>

const __int64 base=;

const int lenth=;

void mul(__int64 a[],int len,int b)

{

    int i;

    __int64 jw=;

    for(i=len-;i>=;i--)

    {

        jw=jw+a[i]*b;

        a[i]=jw%base;

        jw=jw/base;

    }

}

void div(__int64 a[],int len,int b)

{

    int i;

    __int64 jw=;

    for(i=;i<lenth;i++)

    {

        jw=jw*base+a[i];

        a[i]=jw/b;

        jw=jw%b;

    }

}

int main()

{

      int i,j,n;

      __int64 a[][];

      memset(a[],,sizeof(a[]));

      a[][lenth-]=;

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

      {

          memcpy(a[i],a[i-],sizeof(a[]));

          mul(a[i],lenth,*i-);

          div(a[i],lenth,i+);

      }

      while(scanf("%d",&n)!=EOF)

      {

          if(n==-)  break;

          for(i=;i<lenth&&a[n][i]==;i++);

              printf("%I64d",a[n][i++]);

              for(;i<lenth;i++)

                 printf("%0*I64d",,a[n][i]);

              printf("\n");

      }

      return ;

}