%mod-kompatible Wege zur Erzeugung von Binomialkoeffizienten

Question

Ich möchte einen Teil meines Programms optimieren, in dem ich die Summe der Binomialkoeffizienten bis K berechne, d.h.

C(N,0) + C(N,1) + ... + C(N,K)

Da die Werte über den Datentyp (long long) hinausgehen, muss ich die Werte mod M und suchte nach Verfahren, die dies ermöglichen.

Derzeit habe ich es mit Pascal's Triangle getan, aber es scheint ein bisschen Last zu nehmen. so, ich frage mich, wenn es irgendeine andere effiziente Möglichkeit, dies zu tun ist. Ich habe das Lucas-Theorem in Betracht gezogen, aber M, das ich habe, ist bereits groß genug, so dass C(N,k) außer Kontrolle gerät!

Irgendwelche Hinweise, wie ich das anders machen kann, vielleicht die ganze Summe mit einem anderen ordentlichen Ausdruck der Summe berechnen. Wenn nicht, werde ich es bei der Methode des Pascal'schen Dreiecks selbst belassen.

Ich danke Ihnen,

Hier ist, was ich bis jetzt habe O(N^2) :

#define MAX 1000000007
long long NChooseK_Sum(int N, int K){
    vector<long long> prevV, V;
    prevV.push_back(1);     prevV.push_back(1);
    for(int i=2;i<=N;++i){
            V.clear();
            V.push_back(1);
            for(int j=0;j<(i-1);++j){
                    long long val = prevV[j] + prevV[j+1];
                    if(val >= MAX)
                            val %= MAX;
                    V.push_back(val);
            }
            V.push_back(1);
            prevV = V;
    }
    long long res=0;
    for(int i=0;i<=K;++i){
            res+=V[i];
            if(res >= MAX)
                    res %= MAX;
    }
    return res;
}

Answer 1

Ein Algorithmus, der eine lineare Anzahl von arithmetischen Bignum-Operationen durchführt, ist

def binom(n):
    nck = 1
    for k in range(n + 1):  # 0..n
        yield nck
        nck = (nck * (n - k)) / (k + 1)

Dies geschieht durch Division, aber modulo einer Primzahl p können Sie das Gleiche erreichen, indem Sie mit der Lösung multiplizieren i der Gleichung i * (k + 1) = 1 mod p . Der Wert i lässt sich in einer logarithmischen Anzahl von Rechenoperationen über die erweiterter euklidischer Algorithmus .