hdu1133 Buy the Ticket

Catalan数总结

所有排列的情况为C(m+n,n)；

设目标为（m+n,n），不合法的情况一定会有某个状态n-m=1即经过y=-1这条线，将后半部分关于y=-1对称，则目标从（m+n,n）变为（m+n,n+1），从而有C(m+n,n+1)；

（C(m+n,n)-C(m+n,n+1)）乘以m!和n!，得到(m+n)!*(m-n+1)/(m+1)；

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int ans[100];
void Multiply(int *a,const int b)
{
    int temp=0;
    for(int i=0; i<100; i++)
    {
        temp+=a[i]*b;
        a[i]=temp%10000;
        temp/=10000;
    }
}
void Divide(int b)
{
    int r=0;
    for(int i=99; i>=0; i--)
    {
        r=r*10000+ans[i];
        ans[i]=r/b;
        r%=b;
    }
}
int f[201][100];
void CreatFactorial(void)
{
    f[0][0]=f[1][0]=1;
    for(int i = 2; i <201; ++i)
    {
        memcpy(f[i],f[i-1],sizeof(int)*100);
        Multiply(f[i],i);
    }
}
void Output(int *a)
{
    int k=99;
    while(!a[k])
        k--;
    printf("%d",a[k--]);
    while(k>=0)
    {
        printf("%04d",a[k--]);
    }
    puts("");
}
int main(void)
{
    int m,n,Test=1;
    CreatFactorial();
    while(scanf("%d%d",&m,&n),m||n)
    {
        printf("Test #%d:n",Test++);
        if(m<n)
        {
            printf("0n");
            continue;
        }
        memcpy(ans,f[m+n],sizeof(int)*100);
        Multiply(ans,m-n+1);
        Divide(m+1);
        Output(ans);
    }
    return 0;
}