计算Catalan数mod素数

Question

以下是问题描述：

设c[n]是n的加泰罗尼亚数字，p是一个大素数，例如1000000007

我需要计算c[n] % p，其中n的范围是{1,2,3,...,1000}

我遇到的问题是，在32位机器上，当你为如此大的整数计算加泰罗尼亚数时，你会得到溢出。我熟悉模运算。也是

(a.b) % p = ((a % p)(b % p)) % p 

这个公式帮助我单独处理分子中的溢出，但我不知道如何处理分母。

Answer 1

如果您使用动态编程存储结果，并且在填充查找表时，您可以在每一步使用模除法，会怎么样呢？它将处理1000个加泰罗尼亚人的溢出，并且比BigDecimal/BigInteger更快。

我的解决方案是：

public class Catalan {

private static long [] catalan= new long[1001];
private static final int MOD=1000000007;

public static void main(String[] args) {

    precalc();
    for (int i=1;i<=1000;i++){
        System.out.println("Catalan number for "+i+" is: "+catalan[i]);
    }
}

private static void precalc(){

    for (int i=0;i<=1000;i++){
        if (i==0 || i==1){
            catalan[i]=1;
        }
        else{
            long sum =0;long left, right;
            for (int k=1;k<=i;k++){
                left = catalan[k-1] % MOD;
                right= catalan[i-k] % MOD;
                sum =(sum+ (left * right)%MOD)%MOD;
            }
            catalan[i]=sum;
        }
    }

}

}

Answer 2

使用大整数的库怎么样？试着用谷歌搜索一下...

Answer 3

#include <stdio.h>
#include <stdlib.h>

/*
C(n) = (2n)!/(n+1)!n!
     = (2n)(2n-1)(2n-2)..(n+2)/n!
*/
int p = 1000000007;

int gcd(int x, int y){
    while(y!=0){
        int wk = x % y;
        x = y;
        y = wk;
    }
    return x;
}

int catalanMod(n){
    long long c = 1LL;
    int i;
    int *list,*wk;
    //make array [(2n),(2n-1),(2n-2)..(n+2)]
    wk = list = (int*)malloc(sizeof(int)*(n-1));
    for(i=n+2;i<=2*n;++i){
        *wk++ = i;
    }
    wk=list;
    //[(2n),(2n-1),(2n-2)..(n+2)] / [1,2,3,..n]
    //E.g C(10)=[13,17,19,4]
    for(i=2;i<=n;++i){
        int j,k,w;
        for(w=i,j=0;j<n-1;++j){
            while(1!=(k = gcd(wk[j], w))){
                wk[j] /= k;
                w /= k;
            }
            if(w == 1) break;
        }
    }
    wk=list;
    //Multiplication and modulo reduce 
    for(i=0;i<n-1;++i){
        if(wk[i]==1)continue;
        c = c * wk[i] % p;
    }
    free(list);
    return c;
}