％模兼容的方式

我想我的优化计划的一部分，在那里我计算二项式系数总和高达K.即％模兼容的方式

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

由于值超出了数据类型（long long）可以支持，我将计算mod M的值，并正在寻找可以执行此操作的过程。

目前，我已经完成了Pascal的三角形，但它似乎需要一些负载。所以，我想知道是否有其他有效的方法来做到这一点。我已经考虑过卢卡斯的定理，虽然我已经拥有了足够大的空间，这样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; 
}

来源

2012-02-20 srbhkmr

我一直使用Pascal的三角形，我认为你很快就会发现四舍五入错误，尤其是32位整数，但它在第20行很好，所以对我的需求很好。 – John 2012-02-21 00:04:12

* N *，* K *和* M *的近似值范围是多少？另外，你可以阅读SML-caml-F＃吗？我在F＃中有代码，如果这对你有用的话。 – kkm 2012-02-21 00:44:04

如果'K'比'N'小得多，你可以通过在'K'处停止内循环来获得相当多的结果，同样如果'K'接近于'N'，则停止在'NK'并且使用事实上所有二项式系数的总和是'2^N'。但是如果你确实需要它的话，部分deux'的建议（用模块反转）会得到O（K * log（min（K，MAX）））步骤中的总和（模MAX'）。（如果'K> = MAX'，需要注意。） – 2012-02-21 01:21:01

执行算术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可以通过extended Euclidean algorithm在对数算术运算中找到。

来源

2012-02-21 00:26:49

是的，谢谢，这应该工作得很整洁。除了Pascal三角形外，其他方面都没什么问题，但是在这种方法中，除了这个方法之外，我还是希望在mod模式中必须有一些东西来解决它。感谢您指出模块化反转和ext euclidean。 – srbhkmr 2012-02-21 03:20:06

％模兼容的方式

回答

相关问题