numbers - 计算以素数为模的大加泰罗尼亚数

Question

有谁知道一种快速算法，用于计算一个大加泰罗尼亚数模素数（即 1.000.000.007），输入值约为 500.000

已经花了相当长的时间，但我无法修改普通公式以处理这么高的数字，并且动态算法花费的时间太长。

我会非常感谢任何帮助:)

Answer 1

使用开源和基于 python 的程序sage在我的旧双核 2.80Ghz 笔记本电脑上需要 11 秒来计算您要求的加泰罗尼亚数的剩余类：

huisman@thom:~$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath Version 6.10, Release Date: 2015-12-18                    │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
sage: time catalan_number(5*10^5).mod(10^9+7)
CPU times: user 11.3 s, sys: 0 ns, total: 11.3 s
Wall time: 11.3 s
213941567

通过检查代码，您可以了解如何如此快速地完成它。