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

Question

我已经尝试了解决这个系列的基本方法，但是对于 n 的较大值需要时间& r .有什么方法可以将这个表达式简化为一个时间复杂度不依赖于 n 值的表达式吗？或者 r .范围 r,n<=10^5

注意:此处 r < n即我必须找到第一个 r+1 的总和本系列的术语。

---

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

Algorithm to find Sum of the first r binomial coefficients for fixed n modulo m

Answer 1

据我所知，没有可以将其简化为的表达方式。但它可以在 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];
}