High-precision Catalan number

problem link

This is a classic problem of finding the number of stack push ans pop sequences. The only headache is that it requires high precision.

How to determine whether it is a Catalan number

For a more detailed introduction to the Catalan number,see oi-wiki and wikipedia

I think there is another simple way to judge, which is to see whether the first few numbers are consistent with the Catalan number. If they are the same, then it is likely to be a correct guess.

截图来自oi-wiki

Algortithm Implementation

We use catalan[i][j] to represent the j-th digital of the i-th Catalan number.

The formula I use is h(n) = (4n-2)*h(n-1)/(n+1).

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;
const int mxlen = 1005;

int catalan[105][mxlen];
// catalan[i][j] stores the j-th digit of the i-th catalan number
// h(n) = (4n-2)*h(n-1)/(n+1)
void pre_work(){
    catalan[1][0] = 1;
    for(int i=2;i<=100;i++){
        int tmp = 0 ;
        int j = 0;
        for(j=0;j<mxlen;j++){
            tmp+=catalan[i-1][j]*(4*i-2);
            catalan[i][j] = tmp%10;
            tmp/=10;
        }
        // mxlen is big enough, so tmp will be 0 after the loop
        j=mxlen-1;
        while(catalan[i][j]==0) j--;
        while(j>=0){
            tmp = tmp*10+catalan[i][j];
            catalan[i][j--] = tmp/(i+1);  
            if(tmp>=i+1) tmp%=(i+1);
        }
        // Catalan number is a integer, so remain is 0
    }
}
int main(){
    pre_work();
    int n;
    while(scanf("%d",&n)!=EOF){
        int i = mxlen-1;
        while(catalan[n][i]==0) i--;
        while(i>=0) printf("%d",catalan[n][i--]);
        printf("\n");
    }
}