%模兼容的方式
问题描述:
我想我的优化计划的一部分,在那里我计算二项式系数总和高达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;
}
答
执行算术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在对数算术运算中找到。
+0
是的,谢谢,这应该工作得很整洁。除了Pascal三角形外,其他方面都没什么问题,但是在这种方法中,除了这个方法之外,我还是希望在mod模式中必须有一些东西来解决它。感谢您指出模块化反转和ext euclidean。 – srbhkmr 2012-02-21 03:20:06
我一直使用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