如何找到固定 n 的前 r 个二项式系数之和？

Question

我已经尝试了解决这个系列的基本方法，但是 n 和 r 的较大值需要时间。有什么方法可以在时间复杂度不依赖于 n 或 r.Range r,n<=10^5

的值的单个表达式中减少此表达式

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

---

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

Answer 1

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];
}

Answer 2

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

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