8

問題の説明は次のとおりです。

c[n]をカタロニア数としn、大きなp素数にします。1000000007

c[n] % pどこnからの範囲かを計算する必要があります{1,2,3,...,1000}

私が抱えている問題は、32 ビット マシンで、このような大きな整数のカタロニア語数を計算するとオーバーフローが発生することです。私はモジュロ演算に精通しています。また

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

この式は、分子のオーバーフローを個別に回避するのに役立ちますが、分母を処理する方法がわかりません。

4

5 に答える 5

6

モジュラスが 1000000007 の場合、32 ビット整数だけでオーバーフローを回避するのは面倒です。しかし、適切な C 実装は 64 ビット整数を提供するため (適切な C++ 実装も提供します)、その必要はありません。

次に、分母に対処するための 1 つの可能性は、KerrekSB がコメントで述べたように、素数を法とする分母のモジュラー逆数を計算することp = 1000000007です。拡張ユークリッド アルゴリズム、または同等に、 の連分数展開を使用して剰余逆数を計算できますk/p。次に、計算で割る代わりにk、モジュラー逆数を掛けます。

もう 1 つのオプションは、カタロニア語の数値に Segner の再帰関係を使用することです。これにより、除算なしで計算できます。

C(0) = 1
         n
C(n+1) = ∑ C(i)*C(n-i)
         0

のカタロニア語の数値のみが必要なC(k)ためk <= 1000、それらを事前に計算するか、プログラムの起動時にすばやく計算してルックアップ テーブルに格納することができます。

予想に反して、64 ビットの整数型が使用できない場合は、係数を下位 16 ビットと上位 16 ビットに分割することで剰余積を計算できます。

a = a1 + (a2 << 16)    // 0 <= a1, a2 < (1 << 16)
b = b1 + (b2 << 16)    // 0 <= b1, b2 < (1 << 16)
a*b = a1*b1 + (a1*b2 << 16) + (a2*b1 << 16) + (a2*b2 << 32)

で計算a*b (mod m)するにはm <= (1 << 31)、 を法として 4 つの積のそれぞれを減らしますm。

p1 = (a1*b1) % m;
p2 = (a1*b2) % m;
p3 = (a2*b1) % m;
p4 = (a2*b2) % m;

シフトを組み込む最も簡単な方法は

for(i = 0; i < 16; ++i) {
    p2 *= 2;
    if (p2 >= m) p2 -= m;
}

p3の と の32 回の反復で同じですp4。それで

s = p1+p2;
if (s >= m) s -= m;
s += p3;
if (s >= m) s -= m;
s += p4;
if (s >= m) s -= m;
return s;

この方法はそれほど高速ではありませんが、ここで必要な数回の乗算では十分高速です。シフト数を減らすことで、わずかなスピードアップが得られるはずです。最初に計算(p4 << 16) % mし、

for(i = 0; i < 16; ++i) {
    p4 *= 2;
    if (p4 >= m) p4 -= m;
}

次に、 のすべてp2、p3および の現在の値に2 16モジュロをp4掛ける必要があります。m

p4 += p3;
if (p4 >= m) p4 -= m;
p4 += p2;
if (p4 >= m) p4 -= m;
for(i = 0; i < 16; ++i) {
    p4 *= 2;
    if (p4 >= m) p4 -= m;
}
s = p4+p1;
if (s >= m) s -= m;
return s;
于 2012-04-06T18:25:57.230 に答える
3

動的計画法を使用して結果を保存し、ルックアップ テーブルにデータを入力する場合、各ステップで MODULO 除算を使用できます。1000 Catalans のオーバーフローを処理し、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;
        }
    }

}

}
于 2013-03-12T10:02:52.997 に答える
0

大きな整数にライブラリを使用するのはどうですか? グーグルで検索してみてください...

于 2012-04-06T10:27:04.023 に答える
0 
#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;
}
于 2012-04-06T18:39:45.513 に答える
-1

簡単に、プロパティ (a * b) % mod = (a % mod) * (b % mod) を使用します。

于 2017-10-27T13:10:44.843 に答える