Catalan数(数论)

时间:2022-01-14 03:51:33

Catalan数

【参考网址】http://www.cnblogs.com/gongxijun/p/3232682.html

记得当时我们队写过一个,差点超时,现在找到了公式,感觉还是挺简单的。

还要注意,就算开long long 也只能表示到第33个,之后就会溢出。

&代码:

void Solve()
{
f[1]=1;
for(int i=2;i<40;i++){
f[i]=f[i-1]*(4*i-2)/(i+1);
}
PIar(f,40)
}

输出数据在下面,也很显然,33之后就变成了负数,所以33位之后是错的:

0 , 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 , 18367353072152 , 69533550916004 , 263747951750360 , 1002242216651368 , 3814986502092304 , 14544636039226909 , 55534064877048198 , 212336130412243110 , -241155619205100756 , 100389241586533302 , -113283020768157371 , 50195343198909880 , 193059012303499538 , -179060006317004359 ,