%mod兼容生成二项式系数的方法

Question

我想优化我的程序的一部分,我计算二项式系数之和到K.即

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

由于值超出数据类型(long long)可以支持,我将计算值mod M 并且正在寻找执行此操作的过程.

目前,我已经用Pascal的Triangle完成了它,但似乎需要一点负担.所以,我想知道是否有其他有效的方法来做到这一点.我已经考虑过卢卡斯的定理,虽然MI已经足够大,所以C(N,k)失控了!

任何指针,如何以不同的方式做到这一点,也许可以用一些其他整齐的表达来计算总和.如果不是,我将把它与Pascal的Triangle方法本身一起留下.

谢谢,

这是我到目前为止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

执行线性数量的算术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可以通过扩展的欧几里德算法在对数个算术运算中找到.