c++ - 找到第 n 个加泰罗尼亚数 mod m 的最快(已知)算法是什么？

Question

问题是找到第 n-th Catalan 数 mod m，其中 m 是 NOT prime , m = (10^14 + 7)。以下是我尝试过的方法列表:(max N = 10,000)

1. 查表的动态编程，太慢了
2. 使用加泰罗尼亚公式 ncr(2*n, n)/(n + 1)，由于 ncr 函数，它再次不够快，可以t 使用 指数平方 加快速度，因为 m 不是素数。
3. 对预先生成的加泰罗尼亚语表进行硬编码，但由于文件大小限制而失败。
4. 递归关系C(i,k) = C(i-1,k-1) + C(i-1,k)，这太慢了

所以我想知道有没有其他更快的算法来找到我不知道的 n-th Catalan 数字？

使用动态规划

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];
}

Answer 1

根据我写的 this question about computation of nCr 的答案已关闭，最终出现在评论中:

我不确定这是绝对最快的，但它应该足够高效。关键是模乘会分解，但除法不会，所以首先必须减少分数，如下:

• 自 n <= 10000 , 很有可能构建一个大小为 2*n 的数组.

• 使用埃拉托色尼筛法查找和存储直到 20000) 的所有合数的因子对。 .无论要计算多少个加泰罗尼亚数字，这一步只需执行一次。

• 制作另一个大小为 2*n 的表代表每个因子的指数。

• 现在，迭代加泰罗尼亚公式 中的乘积.

• 使用筛表将每个因子分解为素因子，为分子中的每个项增加指数表，为分母中的每个项减少它。

• 任何条目都不会以负数结尾。

• 现在，使用模算术将未取消的因子相乘。

• 在任何时候都不需要除法运算。也没有任何分数。

• 我的方法演示应用于 multi-nCr : http://ideone.com/Weeg6

要将它用于加泰罗尼亚数字，您可以使用它来代替 calc_combinations 中的循环。 :

    for( unsigned k = 2; k <= N; ++k ) {
         factor<+1>(k+N);
         factor<-1>(k);
    }

代码如下所示:http://ideone.com/ZZApk

解决方案

#include <utility>
#include <vector>

std::vector< std::pair<int, int> > factor_table;
void fill_sieve( int n )
{
        factor_table.resize(n+1);
        for( int i = 1; i <= n; ++i )
                factor_table[i] = std::pair<int, int>(i, 1);
        for( int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j) ) {
                if (factor_table[j].second == 1) {
                        int i = j;
                        int ij = j2;
                        while (ij <= n) {
                                factor_table[ij] = std::pair<int, int>(j, i);
                                ++i;
                                ij += j;
                        }
                }
        }
}

std::vector<unsigned> powers;

template<int dir>
void factor( int num )
{
        while (num != 1) {
                powers[factor_table[num].first] += dir;
                num = factor_table[num].second;
        }
}

void calc_catalan(unsigned N)
{
    powers.resize(0);
    powers.resize(2*N+1);
    for( unsigned k = 2; k <= N; ++k ) {
         factor<+1>(k+N);
         factor<-1>(k);
    }
}

测试驱动

#include <iostream>
#include <cmath>
int main(void)
{
    fill_sieve(20000);
    unsigned N = 9913;
    unsigned long long M = 1000000000007LL;
    calc_catalan(N);
    unsigned long long result = 1;
    for( unsigned i = 0; i < powers.size(); ++i ) {
        while (powers[i]--) {
            result *= i;
            result %= M;
        }
    }
    std::cout << "Catalan(" << N << ") modulo " << M << " = " << result << "\n\n";
}

已完成演示:http://ideone.com/FDWfB

这是另一个相关问题，我用代码和演示回答了这个问题:Number of combinations (N choose R) in C++