问题是找到模
m = (10^14 + 7) 的第 n个卡特兰数，其中m不是质数。这里是我尝试的方法列表：（最大N = 10,000）
- 使用动态规划进行表查找，速度太慢
- 使用卡特兰公式
ncr(2 * n，n)/(n + 1)，由于ncr函数而不够快，不能使用指数平方加速，因为m不是质数。 - 硬编码预生成的
Catalans表，但由于文件大小限制而失败。 - 递归关系
C(i，k) = C(i-1，k-1)+C(i-1，k)，这太慢了
那么，我想知道是否有其他更快的算法来找到我不知道的第n个卡特兰数？
使用动态规划
void generate_catalan_numbers() {
catalan[1] = 1;
for (int i = 2; i <= MAX_NUMBERS; i++) {
for (int j = 1; j <= i - 1; j++) {
catalan[i] = (catalan[i] + ((catalan[j]) * catalan[i - j]) % MODULO) % MODULO;
}
catalan[i] = catalan[i] % MODULO;
}
}
使用原始公式
ull n_choose_r(ull n, ull r) {
if (n < r)
return 0;
if (r > n/2) {
r = n - r;
}
ull result = 1;
ull common_divisor;
for (int i = 1; i <= r; ++i) {
common_divisor = gcd(result, i);
result /= common_divisor;
result *= (n - i + 1) / (i / common_divisor);
}
return result;
}
使用递归关系
ull n_choose_r_relation(ull n, ull r) {
for (int i = 0; i <= n + 1; ++i) {
for (int k = 0; k <= r && k <= i; ++k) {
if (k == 0 || k == i) {
ncr[i][k] = 1;
}
else {
ncr[i][k] = (ncr[i - 1][k - 1] + ncr[i - 1][k]) % MODULO;
}
}
}
return ncr[n][r];
}
。
m为质数，可以通过fast_pow(n, m - 2, m)来计算。 - roxrookm是质数。它只需要n和m互质(GCD(n,m) == 1，其中n是你要求逆的数字)。 - Mysticialull catalan[MAX] = { xxx，yyy，zzz .... };。感谢提供参考。 - roxrook