c - 如何找到固定 n 的前 r 二项式系数的总和？

Question

我已经尝试了解决这个系列的基本方法，但是n&的较大值需要时间r。有没有办法在一个时间复杂度不取决于nOR r.Range r,n<=10^5的值的单个表达式中减少这个表达式

注意：在这里，r < n即我必须找到r+1这个系列的第一项的总和。

我已经阅读了这个问题，但它对我没有帮助：

score 1 · Accepted Answer

AFAIK，没有这样的表达可以减少。但它可以在 O(r) 时间复杂度中完成，如下所示。

考虑一个数组 A，其中 A[i] 存储ⁿ c _i。然后我们可以很容易地验证 A[i] = A[i-1].(n-i+1)/(i)

所以

A[0] = 1;
for(int i=1;i<=r;i++){
    A[i] = A[i-1].(n-i+1)/(i);
}
int ans = 0; //The required answer
for(int i=0;i<=r;i++){
    ans = ans+A[i];
}

score 1 · Accepted Answer

对于较大的 N，二项式系数的行为类似于高斯曲线（至少对于最中心的值）。这可以从斯特林公式推导出来，并得到中心极限定理的支持。

然后可以通过误差函数来近似部分和。

2 回答 2