2020-08-12 栈

https://www.luogu.com.cn/problem/P1044
公式： f[n] = f[0]f[n-1]+f[1]f[n-2]+...+f[n-1]*f[0] (n>2)
详细解答：https://www.luogu.com.cn/problem/solution/P1044

#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstring>
using namespace std;

long long qmi(int m, int k)
{
    int res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t;
        t = t * t;
        k >>= 1;
    }
    return res;
}

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}


//数论做法 卡特兰数
// f[n] = f[0]*f[n-1]+f[1]*f[n-2]+...+f[n-1]*f[0] (n>2)
//公式1：
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll f[MAX_N];
int main()
{
    f[0] = f[1] = 1;
    n = read();
    for(int i = 2;i <= n; i ++)//从n = 2开始
    {
        for(int j = 0; j < i; j ++)//j + i - 1(恒定) = i - 1；
        {
            f[i] += f[ j ]*f[ i-1-j ];
            //f[2] = f[0] * f[2-1] + f[1]*f[2-2];
//            for(int k = 1;k<=n; k++){
//                f[i] += f[j] * f[i-k];
//            }
        }
    }
    printf("%lld",f[n]);
    return 0;
}
/*
3
 
============
5
*/