Catalan 数列

dfs可以过到15，但是n再大一些就会爆时间，建议用递推，当然不愿意思考的懒人就是这样做
程序如下

#include<cstdio> 
#include<iostream>
using namespace std;
int n, jsq=0;
void sc(int a, int b)
{
    if (b==n)
    {
        jsq++;
    }
    else 
    {
        if (a<n)
        {
            sc(a+1,b);
        }
        if (a>b)
        {
            sc(a,b+1);
        }
    }
}
int main()
{
    scanf("%d", &n);
    sc(1,0);
    cout<<jsq;
    return 0;
}

var
n:longint;
begin
readln(n);
case n of
1:write(1);
2:write(2);
3:write(5);
4:write(14);
5:write(42);
6:write(132);
7:write(429);
8:write(1430);
9:write(4862);
10:write(16796);
11:write(58786);
12:write(208012);
13:write(742900);
14:write(2674440);
15:write(9694845);
16:write(35357670);
17:write(129644790);
18:write(477638700);
19:write(1767263190);
20:write(6564120420);
21:write(24466267020);
22:write(91482563640;)
23:write(343059613650);
24:write(1289904147324);
25:write(4861946401452);
end;
end.

py dafa hao
python
import math
import re
a = int(input())
s = 2
for i in range(a+1,a*2):
s *= i
for i in range(1,a):
s //= i
s //= a+1
print(s)


shit

卡特兰数

#include<iostream>
using namespace std;
const int maxn=20;
long long cat[maxn];
int main(){
int n;
cin>>n;
cat[2]=1;
for(int i=2;i<n+3;++i){
cat[i+1]=(4*i-6)*cat[i]/i;
}
cout<<cat[n+2];
return 0;
}

Program Btn;
  const maxN=5000;
  var
    N,i,j,t,num:longint;
    sum,sum1,sum2,p:array[0..maxN]of longint;
    pri:array[0..maxN]of boolean;
    ans:qword;
    procedure getprime;
    var
      i,j:longint;
    begin
      for i:=2 to maxN do
        begin
          j:=1;
          if not pri[i] then
            begin
                inc(t);
                p[t]:=i;
            end;
          while (p[j]*i<=maxN)and(j<=t) do
            begin
               pri[p[j]*i]:=true;
               if p[j] mod i=0 then break;
               inc(j);
            end;
        end;
    end;
  function divide(var x,y:longint):longint;
    var
      c:longint;
    begin
      c:=0;
      while x mod y=0 do begin x:=x div y; inc(c); end;
      exit(c);
    end;
  function Mgm(n,p:longint):qword;
    var
      k,s:qword;
    begin
      k:=1;
      s:=n;
      while p<>1 do
        begin
          if p and 1<>0 then k:=k*s;
          s:=s*s;
          p:=p shr 1;
        end;
      exit(s*k);
   end;
    begin
      getprime;
      read(N);
      for i:=1 to n do
        begin
          num:=i;
          for j:=1 to t do
             sum1[j]:=sum1[j]+divide(num,p[j]);
        end;
      for i:=n+2 to 2*n do
        begin
          num:=i;
          for j:=1 to t do
             sum2[j]:=sum2[j]+divide(num,p[j]);
        end;
      ans:=1;
      for i:=1 to t do
       begin
         sum[i]:=sum2[i]-sum1[i];
         if sum[i]>0 then ans:=ans*Mgm(p[i],sum[i])
          else if sum[i]=0 then continue
           else ans:=ans div Mgm(p[i],abs(sum[i]));
       end;
      write(ans);
    end.

优化卡特兰数：对分子分母分解成以质数为底的幂相乘，指数相减后用快速幂求出答案

var
n,ans:longint;
procedure jishu(x,y:longint);

begin
if (y<>0) then
    if x=0 then 
    begin
        jishu(x+1,y-1);
    end
    else
    begin
        inc(ans);jishu(x-1,y);
        jishu(x+1,y-1);
    end;
end;
begin
    readln(n);
    jishu(0,n);
    writeln(ans+1);
end.

一个简单的递归qvq

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    long long sum=1;
    for(int i=n+1;i<=2*n;++i)   sum*=i;
    for(int i=1;i<=n;++i)   sum/=i;
    sum/=(n+1);
    cout<<sum<<endl;    
}

？？？楼下在写啥

打表大法好！
```c++
#include<iostream>
using namespace std;

int n;
const int table[18]={1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700};

int main(){
cin>>n;
cout<<table[n-1];
return 0;
}
```

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 540 KiB, score = 10
Accepted, time = 0 ms, mem = 540 KiB, score = 100
代码

#include<cstdio>
#define reg register
int f[21]={0,1};
int s()
{
reg char ch=getchar();
reg int x=ch-'0';
for(;(ch=getchar())>='0'&&ch<='9';)
x=x*10+ch-'0';
return x;
}
int w(reg int r)
{
if(r>9)
w(r/10);
putchar(r%10+'0');
return 1;
}
int main()
{
reg int n=s();
for(reg int i=2;i<=n;i++)
{
f[i]+=2*f[i-1];
for(reg int j=2;j<=i-1;j++)
f[i]+=f[j-1]*f[i-j];
}
w(f[n]);
return !putchar('\n');
}


递归求的卡特兰数。。
var
nn:longint;
function cc(x:longint):int64;
begin
if x=1 then exit(1);
cc:=(cc(x-1)*(4*x-2))div(x+1);
end;
begin
readln(nn);
writeln(cc(nn));
end.

pascal 代码
pascal
var
n,i:longint;
a:array[1..15] of longint;
begin
readln(n);
a[1]:=1;
for i:=2 to 15 do
a[i]:=a[i-1]*(4*i-2)div(i+1);
writeln(a[n]);
end.


2333333只是卡特兰数而已
var
f:int64;
n,i:longint;
begin
readln(n);
f:=1;
for i:=2 to n do
f:=f*(4*i-2) div (i+1);
writeln(f);
end.

思路：讨论共i个元素时第1个进栈的元素分别可以第1个，第2个......第i个出栈，于是把这i个出栈时分别的方案数相加即可求出总方案数

代码很简洁：
c++
#include <iostream>
using namespace std;
int n,f[20];
int main()
{
cin>>n;
f[1]=1;
for(int i=2;i<=n;i++)
{
f[i]+=2*f[i-1];
for(int j=2;j<=i-1;j++)
f[i]+=f[j-1]*f[i-j];
}
cout<<f[n];
return 0;
}


water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem water problem

var
f:int64;
n,i:longint;
begin
readln(n);
f:=1;
for i:=2 to n do
f:=f*(4*i-2) div (i+1);
writeln(f);
end.

#include<cstdio>
using namespace std;

int main()
{
int n, a = 1;
scanf("%d", &n);
for(int i=2; i<=n; i++)
a = (4 * i - 2) * a / (i + 1);
printf("%d", a);
return 0;

}
catalan (0,0)

编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms

program p1122;
var a:array[1..15] of longint;
n:longint;
begin
read(n);
a[15]:=9694845;
a[1]:=1;
a[2]:=2;
a[3]:=5;
a[4]:=14;
a[5]:=42;
a[6]:=132;
a[7]:=429;
a[8]:=1430;
a[9]:=4862;
a[10]:=16796;
a[11]:=58786;
a[12]:=208012;
a[13]:=742900;
a[14]:=2674440;
write(a[n]);
end.

Catalan数：
Catalan数前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
没错，正好对应我们的题目，于是果断打出公式
code:
#include<stdio.h>
int main(){
int n,f=1,i;
scanf("%d",&n);
for(i=2;i<=n;i++)
f=f*(4*i-2)/(i+1);
printf("%d\n",f);
return 0;
}