Hdu 1023

浅浅的花香味﹌ 2022-08-05 10:30 98阅读 0赞

题意：

输出第n项catalan数。

原理：

令h(0)=1,h(1)=1，catalan数满足递推式:

h(n)= h(0)\*h(n-1)+h(1)\*h(n-2) + ... + h(n-1)h(0) (n>=2)

例如:h(2)=h(0)\*h(1)+h(1)\*h(0)=1\*1+1\*1=2

h(3)=h(0)\*h(2)+h(1)\*h(1)+h(2)\*h(0)=1\*2+1\*1+2\*1=5

另类递推式:

h(n)=h(n-1)\*(4\*n-2)/(n+1);

递推关系的解为:

h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

递推关系的另类解为:

h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

解题思路：

由于n最大是100，不可能用变量存储结果。所以这题考察的是高精度。我选择了**h(n)=h(n-1)\*(4\*n-2)/(n+1)这个公式。没有把效率优化到最高，就比如先做一遍，把所有结果存到数组里，按照询问直接查表。**

代码：

#include <iostream>
    #include <cstring>
    using namespace std ;
    
    int h[100],hh[100],l,i,j,p,q,le,n;
    
    int main() {
        while (cin >> n){
        memset(h,0,sizeof(h));
        memset(hh,0,sizeof(hh));
        //Formal
        h[0] = 1;
        l = 1;
        for (i = 1; i <= n; i++) {
            //乘4n-2
            p = 4 * i - 2 ;
            for (j = 0; j < l; j++){
                h[j] = h[j] * p ;
            }
            for (j = 0; j < l; j++){
                h[j+1] = h[j+1] + h[j] / 10;
                h[j] = h[j] % 10;
            }
            while (h[l] > 0) {
                h[l+1] += h[l] / 10;
                h[l] = h[l] % 10;
                l++;
            }
            //除n+1
            q = i + 1;
            j = l-1;
            le = 0;
            while (j>=0) {
                le = le * 10 + h[j];
                hh[j] = le / q;
                le = le % q;
                j--;
            }
            for (j = 0; j < l; j++){
                h[j] = hh[j];
            }
            while (h[l-1] == 0) {
                l--;
            }
        }
        for (i = l-1; i >= 0; i--) {
            cout << h[i] ;
        }
        cout << endl;
        }
        return 0;
    }