HDU1267_宇春猜想

题目大意： 给你m个H，n个D，要求组成的字符串中，从左往右算，H的数量大于D的数量。 解题思路： 典型的catalan性质，可以算出C(m+n,m)-C(m+n,m+1),化简为 h(n,m) = (m+n)! * (m+1+n) / (m+1)! / n! 代码：

//推导的公式：  h(n,m) = (m+n)! * (m+1+n) / (m+1)! / n!
#include
using namespace std;
const int MAX = 1000005;
__int64 ans[MAX];

void multip(__int64 *cata, __int64 b, int &len)
{
    __int64 carry = 0;
    for(int i = 0; i < len; i++)
    {
        __int64 temp = cata[i] * b + carry;
        cata[i] = temp % 10;
        carry = temp / 10;
    }
    while(carry)
    {
        len++;
        cata[len-1] = carry % 10;
        carry /= 10;
    }
}

void division(__int64 *cata, __int64 b, int &len)
{
    __int64 r = 0;
    for(int i = len - 1; i >= 0; i--)
    {
        __int64 temp = cata[i] + r * 10;
        cata[i] = temp / b;
        r = temp % b;
    }
    while(!cata[len-1])
        len--;

    return ;
}

void output(__int64 *ans, int len)
{
    for(int i = len - 1; i >= 0; i--)
    {
        printf("%I64d", ans[i]);
    }
    printf("\n");
    return ;
}

int main(void)
{
    int m, n;
    while(scanf("%d %d", &m, &n) == 2)
    {
        if(n > m)
        {
            printf("0\n");
            continue;
        }

        __int64 fa_n = 1;
        for(__int64 i = 1; i <= n; i++)
            fa_n *= i;

        memset(ans, 0, sizeof(ans));
        ans[0] = 1;
        int len = 1;
        for(__int64 i = 1; i <= m + n; i++)
        {
            multip(ans, i, len);
        }
        multip(ans, (__int64)(m + 1 - n), len);
        //除以(m+1)!与n!
        for(__int64 i = 1; i <= m + 1; i++)
        {
            division(ans, i, len);
        }
        for(__int64 i = 1; i <= n; i++)
        {
            division(ans, i, len);
        }
        output(ans, len);
    }

    return 0;
}