3

我想优化我的程序的一部分，我正在计算二项式系数的总和，直到 K。即

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

由于值超出了数据类型（long long）可以支持的范围，我要计算值 modM 并正在寻找执行此操作的程序。

目前，我已经使用 Pascal's Triangle 完成了它，但它似乎需要一些负载。所以，我想知道是否还有其他有效的方法可以做到这一点。我考虑过卢卡斯定理，尽管 MI 已经足够大，以至于 C(N,k) 失控了！

任何关于如何以不同方式执行此操作的指针，也许可以用其他一些简洁的总和表达式来计算整个总和。如果不是，我将把它留给 Pascal 的三角形方法本身。

谢谢，

这是我到目前为止所拥有的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，您可以通过乘以i方程的解来完成很多相同的事情i * (k + 1) = 1 mod p。该值可以通过扩展欧几里得算法i在算术运算的对数中找到。

于 2012-02-21T00:26:49.587 回答