3

Kまでの二項係数の合計を計算しているプログラムの一部を最適化したいと思います。

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

値はデータ型 (long long) がサポートできる範囲を超えているため、modM で値を計算する必要があり、そのための手順を探していました。

現在、パスカルの三角形で実行していますが、少し負荷がかかるようです。だから、これを行うための他の効率的な方法があるかどうか疑問に思っていました。ルーカスの定理を検討しましたが、MI は既に十分に大きいため、C(N,k) は手に負えなくなります!

これをどのように別の方法で行うことができるかについての指針は、おそらく、合計の他のきちんとした式を使用して全体の合計を計算することです。そうでない場合は、パスカルの三角形メソッド自体に任せます。

ありがとうございました、

これが私がこれまでに持っているものです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;
}
4

1 に答える 1

5

算術 bignum 演算の線形数を実行するアルゴリズムは次のとおりです。

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

これは除算を使用しますが、素数を法として、方程式pの解を掛けることでほぼ同じことを達成できます。この値は、拡張ユークリッド アルゴリズムを介して算術演算の対数で見つけることができます。ii * (k + 1) = 1 mod pi

于 2012-02-21T00:26:49.587 に答える